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)

 

 

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 Free Access

Abstract | References | Similar Articles | Additional Information

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


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

  • [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.

Similar Articles

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