Partition regularity
This article needs additional citations for verification. (December 2009) |
In combinatorics, a branch of mathematics, partition regularity is one notion of largeness for a collection of sets.
Given a set , a collection of subsets is called partition regular if every set A in the collection has the property that, no matter how A is partitioned into finitely many subsets, at least one of the subsets will also belong to the collection. That is, for any , and any finite partition , there exists an i ≤ n such that belongs to . Ramsey theory is sometimes characterized as the study of which collections are partition regular.
Examples
[edit]- The collection of all infinite subsets of an infinite set X is a prototypical example. In this case partition regularity asserts that every finite partition of an infinite set has an infinite cell (i.e. the infinite pigeonhole principle.)
- Sets with positive upper density in : the upper density of is defined as (Szemerédi's theorem)
- For any ultrafilter on a set , is partition regular: for any , if , then exactly one .
- Sets of recurrence: a set R of integers is called a set of recurrence if for any measure-preserving transformation of the probability space (Ω, β, μ) and of positive measure there is a nonzero so that .
- Call a subset of natural numbers a.p.-rich if it contains arbitrarily long arithmetic progressions. Then the collection of a.p.-rich subsets is partition regular (Van der Waerden, 1927).
- Let be the set of all n-subsets of . Let . For each n, is partition regular. (Ramsey, 1930).
- For each infinite cardinal , the collection of stationary sets of is partition regular. More is true: if is stationary and for some , then some is stationary.
- The collection of -sets: is a -set if contains the set of differences for some sequence .
- The set of barriers on : call a collection of finite subsets of a barrier if:
- and
- for all infinite , there is some such that the elements of X are the smallest elements of I; i.e. and .
- This generalizes Ramsey's theorem, as each is a barrier. (Nash-Williams, 1965)[1]
- Finite products of infinite trees (Halpern–Läuchli, 1966)
- Piecewise syndetic sets (Brown, 1968)[2]
- Call a subset of natural numbers i.p.-rich if it contains arbitrarily large finite sets together with all their finite sums. Then the collection of i.p.-rich subsets is partition regular (Jon Folkman, Richard Rado, and J. Sanders, 1968).[3]
- (m, p, c)-sets [clarification needed][4]
- IP sets[5][6]
- MTk sets for each k, i.e. k-tuples of finite sums (Milliken–Taylor, 1975)
- Central sets; i.e. the members of any minimal idempotent in , the Stone–Čech compactification of the integers. (Furstenberg, 1981, see also Hindman, Strauss, 1998)
Diophantine equations
[edit]A Diophantine equation is called partition regular if the collection of all infinite subsets of containing a solution is partition regular. Rado's theorem characterises exactly which systems of linear Diophantine equations are partition regular. Much progress has been made recently on classifying nonlinear Diophantine equations.[7][8]
References
[edit]- ^ Nash-Williams, C. St. J. A. (1965). "On well-quasi-ordering transfinite sequences". Mathematical Proceedings of the Cambridge Philosophical Society. 61 (1): 33–39. doi:10.1017/S0305004100038603.
- ^ Brown, Thomas Craig (1971). "An interesting combinatorial method in the theory of locally finite semigroups". Pacific Journal of Mathematics. 36 (2): 285–289. doi:10.2140/pjm.1971.36.285.
- ^ Sanders, Jon Henry (1968). A Generalization of Schur's Theorem, Doctoral Dissertation (PhD). Yale University.
- ^ Deuber, Walter (1973). "Partitionen und lineare Gleichungssysteme". Mathematische Zeitschrift. 133 (2): 109–123. doi:10.1007/BF01237897.
- ^ Hindman, Neil (1974). "Finite sums from sequences within cells of a partition of ". Journal of Combinatorial Theory. Series A. 17 (1): 1–11. doi:10.1016/0097-3165(74)90023-5.
- ^ Hindman, Neil; Strauss, Dona (1998). Algebra in the Stone–Čech compactification. De Gruyter. doi:10.1515/9783110258356. ISBN 978-3-11-025623-9.
- ^ Di Nasso, Mauro; Luperi Baglini, Lorenzo (January 2018). "Ramsey properties of nonlinear Diophantine equations". Advances in Mathematics. 324: 84–117. arXiv:1606.02056. doi:10.1016/j.aim.2017.11.003. ISSN 0001-8708.
- ^ Barrett, Jordan Mitchell; Lupini, Martino; Moreira, Joel (May 2021). "On Rado conditions for nonlinear Diophantine equations". European Journal of Combinatorics. 94 103277. arXiv:1907.06163. doi:10.1016/j.ejc.2020.103277. ISSN 0195-6698.
Further reading
[edit]- Bergelson, Vitaly; Hindman, Neil (2001). "Partition regular structures contained in large sets are abundant". Journal of Combinatorial Theory. Series A. 93 (1): 18–36. doi:10.1006/jcta.2000.3061.