From Wikipedia, the free encyclopedia
(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 , a collection of subsets 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 , and any finite partition , there exists an i ≤ n such that belongs to . Ramsey theory is sometimes characterized as the study of which collections 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 : the upper density of is defined as ( Szemerédi's theorem)
  • For any ultrafilter on a set , is partition regular: for any , if , then exactly one .
  • Sets of recurrence: a set R of integers is called a set of recurrence if for any measure-preserving transformation of the probability space (Ω, β, μ) and of positive measure there is a nonzero so that .
  • 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 be the set of all n-subsets of . Let . For each n, is partition regular. ( Ramsey, 1930).
  • For each infinite cardinal , the collection of stationary sets of is partition regular. More is true: if is stationary and for some , then some is stationary.
  • The collection of -sets: is a -set if contains the set of differences for some sequence .
  • The set of barriers on : call a collection of finite subsets of a barrier if:
    • and
    • for all infinite , there is some such that the elements of X are the smallest elements of I; i.e. and .
This generalizes Ramsey's theorem, as each is a barrier. ( Nash-Williams, 1965) [1]

Diophantine equations

A Diophantine equation is called partition regular if the collection of all infinite subsets of containing a solution is partition regular. Rado's theorem characterises exactly which systems of linear Diophantine equations are partition regular. Much progress has been made recently on classifying nonlinear Diophantine equations. [7] [8]

References

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

From Wikipedia, the free encyclopedia
(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 , a collection of subsets 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 , and any finite partition , there exists an i ≤ n such that belongs to . Ramsey theory is sometimes characterized as the study of which collections 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 : the upper density of is defined as ( Szemerédi's theorem)
  • For any ultrafilter on a set , is partition regular: for any , if , then exactly one .
  • Sets of recurrence: a set R of integers is called a set of recurrence if for any measure-preserving transformation of the probability space (Ω, β, μ) and of positive measure there is a nonzero so that .
  • 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 be the set of all n-subsets of . Let . For each n, is partition regular. ( Ramsey, 1930).
  • For each infinite cardinal , the collection of stationary sets of is partition regular. More is true: if is stationary and for some , then some is stationary.
  • The collection of -sets: is a -set if contains the set of differences for some sequence .
  • The set of barriers on : call a collection of finite subsets of a barrier if:
    • and
    • for all infinite , there is some such that the elements of X are the smallest elements of I; i.e. and .
This generalizes Ramsey's theorem, as each is a barrier. ( Nash-Williams, 1965) [1]

Diophantine equations

A Diophantine equation is called partition regular if the collection of all infinite subsets of containing a solution is partition regular. Rado's theorem characterises exactly which systems of linear Diophantine equations are partition regular. Much progress has been made recently on classifying nonlinear Diophantine equations. [7] [8]

References

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


Videos

Youtube | Vimeo | Bing

Websites

Google | Yahoo | Bing

Encyclopedia

Google | Yahoo | Bing

Facebook