An infinitary extension of the Graham-Rothschild Parameter Sets Theorem

Authors:
Timothy J. Carlson, Neil Hindman and Dona Strauss

Journal:
Trans. Amer. Math. Soc. **358** (2006), 3239-3262

MSC (2000):
Primary 05D10

DOI:
https://doi.org/10.1090/S0002-9947-06-03899-2

Published electronically:
February 20, 2006

MathSciNet review:
2216266

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 , the Stone-Cech 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 in and the -parameter words are colored with finitely many colors, there exist a color and an -parameter word with the property that whenever a -parameter word of length is substituted in , the result is in the specified color. The ``simplest finite instance'' referred to above is that, given finite colorings of the -parameter words for each , there is one -parameter word which works for each . 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 and version of the Graham-Rothschild Parameter Sets Theorem.

**1.**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**, https://doi.org/10.1112/plms/s3-68.3.449**2.**T. Carlson,*Some unifying principles in Ramsey Theory*, Discrete Math.**68**(1988), 117-169. MR**0926120 (89b:04006)****3.**T. Carlson, N. Hindman, and D. Strauss,*Ramsey theoretic consequences of some new results about algebra in the Stone-Cech compactification*, manuscript. (Currently available at`http://members.aol.com/nhindman/`.)**4.**Walter Deuber,*Partitionen und lineare Gleichungssysteme*, Math. Z.**133**(1973), 109–123 (German). MR**0325406**, https://doi.org/10.1007/BF01237897**5.**H. Furstenberg,*Recurrence in ergodic theory and combinatorical number theory*, Princeton University Press, Princeton, 1981. MR**0603625 (82j:28010)****6.**R. L. Graham and B. L. Rothschild,*Ramsey’s theorem for 𝑛-parameter sets*, Trans. Amer. Math. Soc.**159**(1971), 257–292. MR**0284352**, https://doi.org/10.1090/S0002-9947-1971-0284352-8**7.**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**, https://doi.org/10.1016/S0097-3165(03)00100-6**8.**A. W. Hales and R. I. Jewett,*Regularity and positional games*, Trans. Amer. Math. Soc.**106**(1963), 222–229. MR**0143712**, https://doi.org/10.1090/S0002-9947-1963-0143712-1**9.**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**, https://doi.org/10.1090/S0002-9947-02-03191-4**10.**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****11.**Neil Hindman and Dona Strauss,*Independent sums of arithmetic progressions in 𝐾_{𝑚}-free graphs*, Ars Combin.**70**(2004), 221–243. MR**2023077****12.**Paul Milnes,*Compactifications of semitopological semigroups*, J. Austral. Math. Soc.**15**(1973), 488–503. MR**0348030****13.**J. Paris and L. Harrington,*A mathematical incompleteness in Peano arithmetic*, in Handbook of Mathematical Logic, J. Barwise, ed., North Holland, Amsterdam, 1977, 1133-1142. MR**0457132 (56:15351)****14.**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**, https://doi.org/10.1007/978-3-642-72905-8_9

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (2000):
05D10

Retrieve articles in all journals with MSC (2000): 05D10

Additional Information

**Timothy J. Carlson**

Affiliation:
Department of Mathematics, Ohio State University, Columbus, Ohio 43210

Email:
carlson@math.ohio-state.edu

**Neil Hindman**

Affiliation:
Department of Mathematics, Howard University, Washington, DC 20059

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

DOI:
https://doi.org/10.1090/S0002-9947-06-03899-2

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.

Article copyright:
© Copyright 2006
American Mathematical Society