An infinitary extension of the Graham–Rothschild Parameter Sets Theorem
HTML articles powered by AMS MathViewer
- by Timothy J. Carlson, Neil Hindman and Dona Strauss PDF
- Trans. Amer. Math. Soc. 358 (2006), 3239-3262 Request permission
Abstract:
The Graham-Rothschild Parameter Sets Theorem is one of the most powerful results of Ramsey Theory. (The Hales-Jewett Theorem is its most trivial instance.) Using the algebra of $\beta S$, the Stone-Čech compactification of a discrete semigroup, we derive an infinitary extension of the Graham-Rothschild Parameter Sets Theorem. Even the simplest finite instance of this extension is a significant extension of the original. The original theorem says that whenever $k<m$ in $\mathbb {N}$ and the $k$-parameter words are colored with finitely many colors, there exist a color and an $m$-parameter word $w$ with the property that whenever a $k$-parameter word of length $m$ is substituted in $w$, the result is in the specified color. The “simplest finite instance” referred to above is that, given finite colorings of the $k$-parameter words for each $k<m$, there is one $m$-parameter word which works for each $k$. Some additional Ramsey Theoretic consequences are derived. We also observe that, unlike any other Ramsey Theoretic result of which we are aware, central sets are not necessarily good enough for even the $k=1$ and $m=2$ version of the Graham-Rothschild Parameter Sets Theorem.References
- Vitaly Bergelson, Andreas Blass, and Neil Hindman, Partition theorems for spaces of variable words, Proc. London Math. Soc. (3) 68 (1994), no. 3, 449–476. MR 1262304, DOI 10.1112/plms/s3-68.3.449
- Timothy J. Carlson, Some unifying principles in Ramsey theory, Discrete Math. 68 (1988), no. 2-3, 117–169. MR 926120, DOI 10.1016/0012-365X(88)90109-4
- T. Carlson, N. Hindman, and D. Strauss, Ramsey theoretic consequences of some new results about algebra in the Stone-Čech compactification, manuscript. (Currently available at http://members.aol.com/nhindman/.)
- Walter Deuber, Partitionen und lineare Gleichungssysteme, Math. Z. 133 (1973), 109–123 (German). MR 325406, DOI 10.1007/BF01237897
- H. Furstenberg, Recurrence in ergodic theory and combinatorial number theory, Princeton University Press, Princeton, N.J., 1981. M. B. Porter Lectures. MR 603625, DOI 10.1515/9781400855162
- R. L. Graham and B. L. Rothschild, Ramsey’s theorem for $n$-parameter sets, Trans. Amer. Math. Soc. 159 (1971), 257–292. MR 284352, DOI 10.1090/S0002-9947-1971-0284352-8
- David S. Gunderson, Imre Leader, Hans Jürgen Prömel, and Vojtěch Rödl, Independent Deuber sets in graphs on the natural numbers, J. Combin. Theory Ser. A 103 (2003), no. 2, 305–322. MR 1996069, DOI 10.1016/S0097-3165(03)00100-6
- A. W. Hales and R. I. Jewett, Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222–229. MR 143712, DOI 10.1090/S0002-9947-1963-0143712-1
- Neil Hindman, Imre Leader, and Dona Strauss, Infinite partition regular matrices: solutions in central sets, Trans. Amer. Math. Soc. 355 (2003), no. 3, 1213–1235. MR 1938754, DOI 10.1090/S0002-9947-02-03191-4
- Neil Hindman and Dona Strauss, Algebra in the Stone-Čech compactification, De Gruyter Expositions in Mathematics, vol. 27, Walter de Gruyter & Co., Berlin, 1998. Theory and applications. MR 1642231, DOI 10.1515/9783110809220
- Neil Hindman and Dona Strauss, Independent sums of arithmetic progressions in $K_m$-free graphs, Ars Combin. 70 (2004), 221–243. MR 2023077
- Paul Milnes, Compactifications of semitopological semigroups, J. Austral. Math. Soc. 15 (1973), 488–503. MR 0348030, DOI 10.1017/S1446788700028858
- Handbook of mathematical logic, Studies in Logic and the Foundations of Mathematics, vol. 90, North-Holland Publishing Co., Amsterdam, 1977. With the cooperation of H. J. Keisler, K. Kunen, Y. N. Moschovakis and A. S. Troelstra. MR 457132
- Hans J. Prömel and Bernd Voigt, Graham-Rothschild parameter sets, Mathematics of Ramsey theory, Algorithms Combin., vol. 5, Springer, Berlin, 1990, pp. 113–149. MR 1083597, DOI 10.1007/978-3-642-72905-8_{9}
Additional Information
- Timothy J. Carlson
- Affiliation: Department of Mathematics, Ohio State University, Columbus, Ohio 43210
- MR Author ID: 45425
- Email: carlson@math.ohio-state.edu
- Neil Hindman
- Affiliation: Department of Mathematics, Howard University, Washington, DC 20059
- MR Author ID: 86085
- Email: nhindman@aol.com
- Dona Strauss
- Affiliation: Department of Pure Mathematics, University of Hull, Hull HU6 7RX, United Kingdom
- Email: d.strauss@maths.hull.ac.uk
- Received by editor(s): February 20, 2004
- Received by editor(s) in revised form: September 14, 2004
- Published electronically: February 20, 2006
- Additional Notes: The second author acknowledges support received from the National Science Foundation (USA) via grant DMS-0070593.
- © Copyright 2006 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 358 (2006), 3239-3262
- MSC (2000): Primary 05D10
- DOI: https://doi.org/10.1090/S0002-9947-06-03899-2
- MathSciNet review: 2216266