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)

 

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
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] F. G. Abramson and L. A. Harrington, Models without indiscernibles, J. Symbolic Logic 43 (1978), 572-600. MR 503795 (80a:03045)
  • [2] W. Deuber, Generalizations of Ramsey's theorem, Colloq. Math. Soc. János Bolyai 10, North-Holland, 1975 pp. 323-332. MR 0369127 (51:5363)
  • [3] P. Erdös, Problems and results on finite and infinite graphs, Recent Advances in Graph Theory, Academic Press, pp. 183-192. MR 0389669 (52:10500)
  • [4] P. Erdös, A. Hajnal and L. Pósa, Strong embeddings of graphs into colored graphs, Colloq. Math. János Bolyai Soc. 10, North-Holland, 1975, pp. 1127-1132. MR 0389604 (52:10435)
  • [5] R. L. Graham, Rudiments of Ramsey theory, CBMS Regional Conf. Ser. in Math., no. 45, Amer. Math. Soc., Providence, R. I., 1981. MR 608630 (82j:05018)
  • [6] J. Nešetřil and V. Rödl, Ramsey graph without triangles exists for any graph without triangles, Colloq. Math. Soc. János Bolyai 10, North-Holland, 1975, pp. 1127-1132. MR 0392695 (52:13512)
  • [7] -, Type theory of partition problems of graphs, Recent Advances in Graph Theory, Academic Press, pp. 405-412.
  • [8] -, Ramsey property of graphs with forbidden complete subgraphs, J. Combin. Theory Ser. B 20, (1976), 243-249. MR 0412004 (54:133)
  • [9] -, On Ramsey graphs without cycles of short odd length, Comment Math. Univ. Carolin. 29 (1979), 565-582. MR 550457 (81b:05083)
  • [10] -, Two proofs of the Ramsey property of the class of finite hypergraphs, European J. Combin. 3 (1982), 347-352. MR 687733 (85b:05134)
  • [11] -, Simple proof of the existence of restricted Ramsey graphs by means of a partite construction, Combinatorica 1 (1982), 199-202. MR 625551 (83a:05101)
  • [12] -, A short proof of the existence of highly chromatic hypergrahs without short cycles, J. Combin. Theory Ser. B 27 (1979), 225-227. MR 546865 (81b:05048)
  • [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: http://dx.doi.org/10.1090/S0002-9947-1987-0896015-8
PII: S 0002-9947(1987)0896015-8
Article copyright: © Copyright 1987 American Mathematical Society