Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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

DOI: http://dx.doi.org/10.1090/S0002-9947-1988-0957064-5
PII: S 0002-9947(1988)0957064-5
Article copyright: © Copyright 1988 American Mathematical Society