Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



A sparse Graham-Rothschild theorem

Authors: Hans Jürgen Prömel and Bernd Voigt
Journal: Trans. Amer. Math. Soc. 309 (1988), 113-137
MSC: Primary 05A05
MathSciNet review: 957064
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The main result of this paper is a sparse version of the Graham-Rothschild partition theorem for $ n$-parameter sets [R. L. Graham and B. L. Rothschild, Ramsey's theorem for $ n$-parameter sets, Trans. Amer. Math. Soc. 159 (1971), 257-292]. In particular, a sparse version of Hales-Jewett's theorem is proved. We give several applications, e.g., for arithmetic progressions and finite sums of integers, confirming conjectures of J. Spencer and of J. Nešetřil and V. Rödl.

We also consider graphs defined on parameter sets and prove a sparse and restricted induced partition theorem for such graphs, extending results from [H. J. Prömel, Induced partition properties of combinatorial cubes, J. Combin. Theory Ser. A 39 (1985), 177-208] and [P. Frankl, R. L. Graham, and V. Rödl, Induced restricted Ramsey theorems for spaces, J. Combin. Theory Ser. A 44 (1987), 120-128].

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05A05

Retrieve articles in all journals with MSC: 05A05

Additional Information

Article copyright: © Copyright 1988 American Mathematical Society