Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-13T00:34:40.361Z Has data issue: false hasContentIssue false
  • English
  • Français

Comparisons of Polychromatic and Monochromatic Ramsey Theory

Published online by Cambridge University Press:  12 March 2014

Justin Palumbo
Justin Palumbo*
Affiliation:
Department of Mathematics, University of California at Los Angeles, Los Angeles, California, 90095, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We compare the strength of polychromatic and monochromatic Ramsey theory in several set-theoretic domains. We show that the rainbow Ramsey theorem does not follow from ZF, nor does the rainbow Ramsey theorem imply Ramsey's theorem over ZF. Extending the classical result of Erdős and Rado we show that the axiom of choice precludes the natural infinite exponent partition relations for polychromatic Ramsey theory. We introduce rainbow Ramsey ultrafilters, a polychromatic analogue of the usual Ramsey ultrafilters. We investigate the relationship of rainbow Ramsey ultrafilters with various special classes of ultrafilters, showing for example that every rainbow Ramsey ultrafilter is nowhere dense but rainbow Ramsey ultrafilters need not be rapid. This entails comparison of the polychromatic and monochromatic Ramsey theorems as combinatorial principles on ω.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 78 , Issue 3 , September 2013 , pp. 951 - 968
Copyright
Copyright © Association for Symbolic Logic 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Abraham, Uri, Cummings, James, and Smyth, Clifford, Some results in polychromatic Ramsey theory, this Journal, vol. 72 (2007), no. 3, pp. 865–896.Google Scholar
[2] Alspach, Brian, Gerson, Martin, Hahn, Geňa, and Hell, Pavol, On sub-Ramsey numbers, Ars Combinatorial, vol. 22 (1986), pp. 199–206.Google Scholar
[3] Baumgartner, James E., Ultrafilters on ω, this Journal, vol. 60 (1995), no. 2, pp. 624–639.Google Scholar
[4] Blass, Andreas, Ramsey's theorem in the hierarchy of choice principles, this Journal, vol. 42 (1977), no. 3, pp. 387–390.Google Scholar
[5] Brendle, Jörg, Between P-points and nowhere dense ultrafilters, Israel Journal of Mathematics, vol. 113 (1999), pp. 205–230.CrossRefGoogle Scholar
[6] Csima, Barbara F. and Mileti, Joseph R., The strength of the rainbow Ramsey theorem, this Journal, vol. 74 (2009), no. 4, pp. 1310–1324.Google Scholar
[7] Flašková, J., ℐ-ultrafilters and summable ideals, 10th Asian Logic Conference (Arai, T. et al., editors), World Science Publishers, Hackensack, NJ, 2010, pp. 113–123.Google Scholar
[8] Hell, Pavol and Montellano-Ballesteros, Juan José, Polychromatic cliques, Discrete Mathematics, vol. 285 (2004), no. 1–3, pp. 319–322.CrossRefGoogle Scholar
[9] Jech, Thomas J., The axiom of choice, Studies in Logic and the Foundations of Mathematics, vol. 75, North-Holland, Amsterdam, 1973.Google Scholar
[10] Kanamori, Akihiro, The higher infinite, second ed., Springer Monographs in Mathematics, Springer, 2003.Google Scholar
[11] Kleinberg, E. M., The independence of Ramsey's theorem, this Journal, vol. 34 (1969), no. 2, pp. 205–206.Google Scholar
[12] Kunen, Kenneth, Some points in βN, Mathematical Proceedings of the Cambridge Philosophical Society, vol. 80 (1976), no. 3, pp. 385–398.CrossRefGoogle Scholar
[13] Shelah, Saharon, There may be no nowhere dense ultrafilter, Logic Colloquium '95, Lecture Notes Logic, vol. 11, Springer, 1998, pp. 305–324.Google Scholar
[14] Todorčević, Stevo , Forcing positive partition relations, Transactions of the American Mathematical Society, vol. 280 (1983), no. 2, pp. 703–720.CrossRefGoogle Scholar