Strong Ramsey theorems for Steiner systems

Authors:
Jaroslav Nešetřil and Vojtěch Rödl

Journal:
Trans. Amer. Math. Soc. **303** (1987), 183-192

MSC:
Primary 05C55

DOI:
https://doi.org/10.1090/S0002-9947-1987-0896015-8

MathSciNet review:
896015

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: It is shown that the class of partial Steiner -systems has the edge Ramsey property, i.e., we prove that for every partial Steiner -system there exists a partial Steiner -system such that for every partition of the edges of into two classes one can find an induced monochromatic copy of . As an application we get that the class of all graphs without cycles of lengths and has the edge Ramsey property. This solves a longstanding problem in the area.

**[1]**Fred G. Abramson and Leo A. Harrington,*Models without indiscernibles*, J. Symbolic Logic**43**(1978), no. 3, 572–600. MR**503795**, https://doi.org/10.2307/2273534**[2]**W. Deuber,*Generalizations of Ramsey’s theorem*, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. I, North-Holland, Amsterdam, 1975, pp. 323–332. Colloq. Math. Soc. János Bolyai, Vol. 10. MR**0369127****[3]**Paul Erdős,*Problems and results on finite and infinite graphs*, Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974) Academia, Prague, 1975, pp. 183–192. (loose errata). MR**0389669****[4]**A. Hajnal,*Weak partition relations*, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, North-Holland, Amsterdam, 1975, pp. 817–836. Colloq. Math. Soc. Janos Bolyai, Vol. 10. MR**0389604****[5]**Ronald L. Graham,*Rudiments of Ramsey theory*, CBMS Regional Conference Series in Mathematics, vol. 45, American Mathematical Society, Providence, R.I., 1981. MR**608630****[6]**J. Nešetřil and V. Rödl,*A Ramsey graph without triangles exists for any graph without triangles*, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. III, North-Holland, Amsterdam, 1975, pp. 1127–1132. Colloq. Math. Soc. Janos Bolyai, Vol. 10. MR**0392695****[7]**-,*Type theory of partition problems of graphs*, Recent Advances in Graph Theory, Academic Press, pp. 405-412.**[8]**Jaroslav Nešetřil and Vojtěch Rödl,*The Ramsey property for graphs with forbidden complete subgraphs*, J. Combinatorial Theory Ser. B**20**(1976), no. 3, 243–249. MR**0412004****[9]**J. Nešetřil and V. Rödl,*On Ramsey graphs without cycles of short odd lengths*, Comment. Math. Univ. Carolin.**20**(1979), no. 3, 565–582. MR**550457****[10]**Jaroslav Nešetřil and Vojtěch Rödl,*Two proofs of the Ramsey property of the class of finite hypergraphs*, European J. Combin.**3**(1982), no. 4, 347–352. MR**687733**, https://doi.org/10.1016/S0195-6698(82)80019-X**[11]**Jaroslav Nešetřil and Vojtěch Rödl,*Simple proof of the existence of restricted Ramsey graphs by means of a partite construction*, Combinatorica**1**(1981), no. 2, 199–202. MR**625551**, https://doi.org/10.1007/BF02579274**[12]**Jaroslav Nešetřil and Vojtěch Rödl,*A short proof of the existence of highly chromatic hypergraphs without short cycles*, J. Combin. Theory Ser. B**27**(1979), no. 2, 225–227. MR**546865**, https://doi.org/10.1016/0095-8956(79)90084-4**[13]**H. J. Prömel and B. Voigt,*Canonizing Ramsey theory*(preprint 1985).**[14]**F. P. Ramsey,*On a problem of formal logic*, Proc. London Math. Soc.**30**(1930), 264-286.**[15]**V. Rödl,*A generalization of Ramsey theorem and dimension of graphs*, Thesis, Charles University, 1973 (in Czech); English transl.,*A generalization of Ramsey theorem, Graphs, hypergraphs and block systems*, (Eds., M. Borowiecki, Z. Skupien, and L. Szamkolowicz), Zielona Gora, 1976, pp. 211-220.

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

Retrieve articles in all journals with MSC: 05C55

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1987-0896015-8

Article copyright:
© Copyright 1987
American Mathematical Society