Partition regularity

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

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

## Contents

* 1 Examples
* 2 Diophantine equations
* 3 References
* 4 Sources

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

This generalizes Ramsey's theorem, as each [math]\displaystyle{ [A]^n }[/math] 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 (Folkman–Rado–Sanders, 1968).
* (m, p, c)-sets[clarification needed] (Deuber, 1973)
* IP sets (Hindman, 1974, see also Hindman, Strauss, 1998)
* 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 [math]\displaystyle{ \beta\mathbb{N} }[/math], the Stone–Čech compactification of the integers. (Furstenberg, 1981, see also Hindman, Strauss, 1998)

## Diophantine equations

A Diophantine equation [math]\displaystyle{ P(\mathbf{x}) = 0 }[/math] is called partition regular if the collection of all infinite subsets of [math]\displaystyle{ \N }[/math] containing a solution is partition regular. Rado's theorem characterises exactly which systems of linear Diophantine equations [math]\displaystyle{ \mathbf{A}\mathbf{x} = \mathbf{0} }[/math] 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. doi:10.1016/j.aim.2017.11.003. ISSN 0001-8708. http://dx.doi.org/10.1016/j.aim.2017.11.003.
2. ↑ Barrett, Jordan Mitchell; Lupini, Martino; Moreira, Joel (May 2021). "On Rado conditions for nonlinear Diophantine equations". European Journal of Combinatorics 94: 103277. doi:10.1016/j.ejc.2020.103277. ISSN 0195-6698. http://dx.doi.org/10.1016/j.ejc.2020.103277.

## Sources

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.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Partition regularity. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Partition_regularity&oldid=2879358"