Partition regularity

<h2 id="examples">Examples</h2>
<ul><li>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 <a href="/facts/Pigeonhole_principle/hDks9p4n">pigeonhole principle</a>.)</li>
<li>Sets with positive <a href="/facts/Upper_density/WtMTUmMJ">upper density</a> 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}}.}
 
 (<a href="/facts/Szemer%25C3%25A9di%2527s_theorem/6fjvXcEx">Szemerédi's theorem</a>)</li>
<li>For any <a href="/facts/Ultrafilter_(set_theory)/KUpERdqN">ultrafilter</a> 
 
 
 
 
 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} }
 
.</li>
<li>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 <a href="/facts/Probability_space/dEcv2VrU">probability space</a> (Ω, β, μ) 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}
 
.</li>
<li>Call a subset of natural numbers a.p.-rich if it contains arbitrarily long <a href="/facts/Arithmetic_progression/c4ew9Xoq">arithmetic progressions</a>. Then the collection of a.p.-rich subsets is partition regular (<a href="/facts/Van_der_Waerden%2527s_theorem/XQRIK3aK">Van der Waerden</a>, 1927).</li>
<li>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. (<a href="/facts/Ramsey%2527s_theorem/VS6K8jGk">Ramsey</a>, 1930).</li>
<li>For each infinite <a href="/facts/Cardinal_number/ccoKwU4R">cardinal</a> 
 
 
 
 κ
 
 
 {\displaystyle \kappa }
 
, the collection of <a href="/facts/Stationary_set/3aqqHnsS">stationary sets</a> 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.</li>
<li>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 <a href="/facts/Sequence/gV2S4uqp">sequence</a> 
 
 
 
 ⟨
 
 s
 
 n
 
 
 
 ⟩
 
 n
 =
 1
 
 
 ∞
 
 
 
 
 {\displaystyle \langle s_{n}\rangle _{n=1}^{\infty }}
 
.</li>
<li>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:
<ul><li>
 
 
 
 ∀
 X
 ,
 Y
 ∈
 
 B
 
 ,
 X
 ⊄
 Y
 
 
 {\displaystyle \forall X,Y\in \mathbb {B} ,X\not \subset Y}
 
 and</li>
<li>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
 </ul></li></ul>
This generalizes <a href="/facts/Ramsey%2527s_theorem/VS6K8jGk">Ramsey's theorem</a>, as each 
 
 
 
 [
 A
 
 ]
 
 n
 
 
 
 
 {\displaystyle [A]^{n}}
 
 is a barrier. (<a href="/facts/Crispin_St._J._A._Nash-Williams/YY5uresp">Nash-Williams</a>, 1965)<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>
<ul><li>Finite products of infinite trees (<a href="/facts/Halpern%25E2%2580%2593L%25C3%25A4uchli_theorem/jHv8GUlt">Halpern–Läuchli</a>, 1966)</li>
<li><a href="/facts/Piecewise_syndetic_set/LUc36xuH">Piecewise syndetic sets</a> (Brown, 1968)<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a></li>
<li>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 (<a href="/facts/Jon_Folkman/u7HclS3t">Jon Folkman</a>, <a href="/facts/Richard_Rado/QXBFIwBd">Richard Rado</a>, and J. Sanders, 1968).<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a></li>
<li>(m, p, c)-sets <a class="footnote-ref" id="fnref:4" href="#fn:4">4</a></li>
<li><a href="/facts/IP_set/P9k3d7YU">IP sets</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a></li>
<li><a href="/facts/Milliken%25E2%2580%2593Taylor_theorem/pBt6fWuL">MTk sets</a> for each k, i.e. k-tuples of finite sums (Milliken–Taylor, 1975)</li>
<li>Central sets; i.e. the members of any minimal idempotent in 
 
 
 
 β
 
 N
 
 
 
 {\displaystyle \beta \mathbb {N} }
 
, the <a href="/facts/Stone%25E2%2580%2593%25C4%258Cech_compactification/5smYbEYS">Stone–Čech compactification</a> of the integers. (Furstenberg, 1981, see also Hindman, Strauss, 1998)</li></ul>
<h2 id="diophantine-equations">Diophantine equations</h2>
A <a href="/facts/Diophantine_equation/mYaHp7oX">Diophantine equation</a> 
 
 
 
 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. <a href="/facts/Rado%2527s_theorem_(Ramsey_theory)/66zsMLDV">Rado's theorem</a> 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.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a><a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

<h2 id="further-reading">Further reading</h2>
<ul><li><a href="/facts/Vitaly_Bergelson/SgdgRIyd">Bergelson, Vitaly</a>; Hindman, Neil (2001). <a href="https://doi.org/10.1006%2Fjcta.2000.3061">"Partition regular structures contained in large sets are abundant"</a>. <a href="/facts/Journal_of_Combinatorial_Theory/oYS6G76K">Journal of Combinatorial Theory</a>. Series A. 93 (1): 18–36. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1006%2Fjcta.2000.3061">10.1006/jcta.2000.3061</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn: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. <a href="/wiki/Crispin_St._J._A._Nash-Williams" target="_blank">/wiki/Crispin_St._J._A._Nash-Williams</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn: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. <a href="http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1102971066" target="_blank">http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1102971066</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Sanders, Jon Henry (1968). A Generalization of Schur's Theorem, Doctoral Dissertation (PhD). Yale University. <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Deuber, Walter (1973). "Partitionen und lineare Gleichungssysteme". Mathematische Zeitschrift. 133 (2): 109–123. doi:10.1007/BF01237897. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn: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. <a href="https://doi.org/10.1016%2F0097-3165%2874%2990023-5" target="_blank">https://doi.org/10.1016%2F0097-3165%2874%2990023-5</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Hindman, Neil; Strauss, Dona (1998). Algebra in the Stone–Čech compactification. De Gruyter. doi:10.1515/9783110258356. ISBN 978-3-11-025623-9. <a href="978-3-11-025623-9" target="_blank">978-3-11-025623-9</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn: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. <a href="https://doi.org/10.1016%2Fj.aim.2017.11.003" target="_blank">https://doi.org/10.1016%2Fj.aim.2017.11.003</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn: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. <a href="https://dx.doi.org/10.1016/j.ejc.2020.103277" target="_blank">https://dx.doi.org/10.1016/j.ejc.2020.103277</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
</ol>

Partition regularity open-in-new

Partition regularity