Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Partition regularity
Notion of largeness for collections of sets in combinatorics

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

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

We don't have any images related to Partition regularity yet.
We don't have any YouTube videos related to Partition regularity yet.
We don't have any PDF documents related to Partition regularity yet.
We don't have any Books related to Partition regularity yet.
We don't have any archived web articles related to Partition regularity yet.

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 N {\displaystyle \mathbb {N} } : the upper density d ¯ ( A ) {\displaystyle {\overline {d}}(A)} of A ⊂ N {\displaystyle A\subset \mathbb {N} } is defined as d ¯ ( A ) = lim sup n → ∞ | { 1 , 2 , … , n } ∩ A | n . {\displaystyle {\overline {d}}(A)=\limsup _{n\rightarrow \infty }{\frac {|\{1,2,\ldots ,n\}\cap A|}{n}}.} (Szemerédi's theorem)
  • For any ultrafilter U {\displaystyle \mathbb {U} } on a set X {\displaystyle X} , U {\displaystyle \mathbb {U} } is partition regular: for any A ∈ U {\displaystyle A\in \mathbb {U} } , if A = C 1 ⊔ ⋯ ⊔ C n {\displaystyle A=C_{1}\sqcup \cdots \sqcup C_{n}} , then exactly one C i ∈ U {\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 T {\displaystyle T} of the probability space (Ω, β, μ) and A ∈ β {\displaystyle A\in \beta } of positive measure there is a nonzero n ∈ R {\displaystyle n\in R} so that μ ( A ∩ T n A ) > 0 {\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 [ A ] n {\displaystyle [A]^{n}} be the set of all n-subsets of A ⊂ N {\displaystyle A\subset \mathbb {N} } . Let S n = ⋃ A ⊂ N [ A ] n {\displaystyle \mathbb {S} ^{n}=\bigcup _{A\subset \mathbb {N} }^{}[A]^{n}} . For each n, S 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 S {\displaystyle S} is stationary and S = ⋃ α < λ S α {\displaystyle S=\bigcup _{\alpha <\lambda }S_{\alpha }} for some λ < κ {\displaystyle \lambda <\kappa } , then some S α {\displaystyle S_{\alpha }} is stationary.
  • The collection of Δ {\displaystyle \Delta } -sets: A ⊂ N {\displaystyle A\subset \mathbb {N} } is a Δ {\displaystyle \Delta } -set if A {\displaystyle A} contains the set of differences { s m − s n : m , n ∈ N , n < m } {\displaystyle \{s_{m}-s_{n}:m,n\in \mathbb {N} ,\,n<m\}} for some sequence ⟨ s n ⟩ n = 1 ∞ {\displaystyle \langle s_{n}\rangle _{n=1}^{\infty }} .
  • The set of barriers on N {\displaystyle \mathbb {N} } : call a collection B {\displaystyle \mathbb {B} } of finite subsets of N {\displaystyle \mathbb {N} } a barrier if:
    • ∀ X , Y ∈ B , X ⊄ Y {\displaystyle \forall X,Y\in \mathbb {B} ,X\not \subset Y} and
    • for all infinite I ⊂ ∪ B {\displaystyle I\subset \cup \mathbb {B} } , there is some X ∈ B {\displaystyle X\in \mathbb {B} } such that the elements of X are the smallest elements of I; i.e. X ⊂ I {\displaystyle X\subset I} and ∀ i ∈ I ∖ X , ∀ x ∈ X , x < i {\displaystyle \forall i\in I\setminus X,\forall x\in X,x<i} .
This generalizes Ramsey's theorem, as each [ A ] n {\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 4
  • IP sets56
  • 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 β N {\displaystyle \beta \mathbb {N} } , the Stone–Čech compactification of the integers. (Furstenberg, 1981, see also Hindman, Strauss, 1998)

Diophantine equations

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

Further reading

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. /wiki/Crispin_St._J._A._Nash-Williams ↩

  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. http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1102971066 ↩

  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. /wiki/Doi_(identifier) ↩

  5. Hindman, Neil (1974). "Finite sums from sequences within cells of a partition of N {\displaystyle N} ". Journal of Combinatorial Theory. Series A. 17 (1): 1–11. doi:10.1016/0097-3165(74)90023-5. https://doi.org/10.1016%2F0097-3165%2874%2990023-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. 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. https://doi.org/10.1016%2Fj.aim.2017.11.003 ↩

  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. https://dx.doi.org/10.1016/j.ejc.2020.103277 ↩