Partition regularity

In combinatorics, a branch of mathematics, partition regularity is one notion of largeness for a collection of sets.

Given a set ${\displaystyle X}$, a collection of subsets ${\displaystyle \mathbb {S} \subset {\mathcal {P}}(X)}$ 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 ${\displaystyle A\in \mathbb {S} }$, and any finite partition ${\displaystyle A=C_{1}\cup C_{2}\cup \cdots \cup C_{n}}$, there exists an i ≤ n such that ${\displaystyle C_{i}}$ belongs to ${\displaystyle \mathbb {S} }$. Ramsey theory is sometimes characterized as the study of which collections ${\displaystyle \mathbb {S} }$ are partition regular.

Examples

• 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 ${\displaystyle \mathbb {N} }$: the upper density ${\displaystyle {\overline {d}}(A)}$ of ${\displaystyle A\subset \mathbb {N} }$ is defined as ${\displaystyle {\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {|\{1,2,\ldots ,n\}\cap A|}{n}}.}$ (Szemerédi's theorem)
• For any ultrafilter ${\displaystyle \mathbb {U} }$ on a set ${\displaystyle X}$, ${\displaystyle \mathbb {U} }$ is partition regular: for any ${\displaystyle A\in \mathbb {U} }$, if ${\displaystyle A=C_{1}\sqcup \cdots \sqcup C_{n}}$, then exactly one ${\displaystyle C_{i}\in \mathbb {U} }$.
• Sets of recurrence: a set R of integers is called a set of recurrence if for any measure-preserving transformation ${\displaystyle T}$ of the probability space (Ω, β, μ) and ${\displaystyle A\in \beta }$ of positive measure there is a nonzero ${\displaystyle n\in R}$ so that ${\displaystyle \mu (A\cap T^{n}A)>0}$.
• 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 ${\displaystyle [A]^{n}}$ be the set of all n-subsets of ${\displaystyle A\subset \mathbb {N} }$. Let ${\displaystyle \mathbb {S} ^{n}=\bigcup _{A\subset \mathbb {N} }^{}[A]^{n}}$. For each n, ${\displaystyle \mathbb {S} ^{n}}$ is partition regular. (Ramsey, 1930).
• For each infinite cardinal ${\displaystyle \kappa }$, the collection of stationary sets of ${\displaystyle \kappa }$ is partition regular. More is true: if ${\displaystyle S}$ is stationary and ${\displaystyle S=\bigcup _{\alpha <\lambda }S_{\alpha }}$ for some ${\displaystyle \lambda <\kappa }$, then some ${\displaystyle S_{\alpha }}$ is stationary.
• The collection of ${\displaystyle \Delta }$-sets: ${\displaystyle A\subset \mathbb {N} }$ is a ${\displaystyle \Delta }$-set if ${\displaystyle A}$ contains the set of differences ${\displaystyle \{s_{m}-s_{n}:m,n\in \mathbb {N} ,\,n<m\}}$ for some sequence ${\displaystyle \langle s_{n}\rangle _{n=1}^{\infty }}$.
• The set of barriers on ${\displaystyle \mathbb {N} }$: call a collection ${\displaystyle \mathbb {B} }$ of finite subsets of ${\displaystyle \mathbb {N} }$ a barrier if:
  • ${\displaystyle \forall X,Y\in \mathbb {B} ,X\not \subset Y}$ and
  • for all infinite ${\displaystyle I\subset \cup \mathbb {B} }$, there is some ${\displaystyle X\in \mathbb {B} }$ such that the elements of X are the smallest elements of I; i.e. ${\displaystyle X\subset I}$ and ${\displaystyle \forall i\in I\setminus X,\forall x\in X,x<i}$.

This generalizes Ramsey's theorem, as each ${\displaystyle [A]^{n}}$ 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]
• MT^k 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 ${\displaystyle \beta \mathbb {N} }$, the Stone–Čech compactification of the integers. (Furstenberg, 1981, see also Hindman, Strauss, 1998)

Diophantine equations

A Diophantine equation ${\displaystyle P(\mathbf {x} )=0}$ is called partition regular if the collection of all infinite subsets of ${\displaystyle \mathbb {N} }$ containing a solution is partition regular. Rado's theorem characterises exactly which systems of linear Diophantine equations ${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {0} }$ are partition regular. Much progress has been made recently on classifying nonlinear Diophantine equations.^[7][8]

References

1. Nash-Williams, C. St. J. A. (1965). "On well-quasi-ordering transfinite sequences". Mathematical Proceedings of the Cambridge Philosophical Society. 61 (1): 33–39. Bibcode:1965PCPS...61...33N. doi:10.1017/S0305004100038603.
2. 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.
3. Sanders, Jon Henry (1968). A Generalization of Schur's Theorem, Doctoral Dissertation (PhD). Yale University.
4. Deuber, Walter (1973). "Partitionen und lineare Gleichungssysteme". Mathematische Zeitschrift. 133 (2): 109–123. doi:10.1007/BF01237897.
5. Hindman, Neil (1974). "Finite sums from sequences within cells of a partition of ${\displaystyle N}$". Journal of Combinatorial Theory. Series A. 17 (1): 1–11. doi:10.1016/0097-3165(74)90023-5.
6. Hindman, Neil; Strauss, Dona (1998). Algebra in the Stone–Čech compactification. De Gruyter. doi:10.1515/9783110258356. ISBN 978-3-11-025623-9.
7. 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.
8. 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

• 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.