# Partition regularity

(Redirected from Partition regular)

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  for some sequence ${\displaystyle \langle s_{n}\rangle _{n=1}^{\omega }}$ .
• 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 .
This generalizes Ramsey's theorem, as each ${\displaystyle [A]^{n}}$  is a barrier. (Nash-Williams, 1965)
• finite products of infinite trees (Halpern–Läuchli, 1966)
• piecewise syndetic sets (Brown, 1968)
• 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 (FolkmanRado–Sanders, 1968).
• (m, p, c)-sets (Deuber, 1973)
• 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 ${\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.[1][2]

## References

1. ^ 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.
2. ^ 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.
1. Vitaly Bergelson, N. Hindman Partition regular structures contained in large sets are abundant J. Comb. Theory A 93 (2001), 18–36.
2. T. Brown, An interesting combinatorial method in the theory of locally finite semigroups, Pacific J. Math. 36, no. 2 (1971), 285–289.
3. W. Deuber, Mathematische Zeitschrift 133, (1973) 109–123
4. N. Hindman, Finite sums from sequences within cells of a partition of N, J. Comb. Theory A 17 (1974) 1–11.
5. C.St.J.A. Nash-Williams, On well-quasi-ordering transfinite sequences, Proc. Camb. Phil. Soc. 61 (1965), 33–39.
6. N. Hindman, D. Strauss, Algebra in the Stone–Čech compactification, De Gruyter, 1998
7. J.Sanders, A Generalization of Schur's Theorem, Doctoral Dissertation, Yale University, 1968.