Strong Ramsey theorems for Steiner systems
Authors:
Jaroslav Nešetřil and Vojtěch Rödl
Journal:
Trans. Amer. Math. Soc. 303 (1987), 183192
MSC:
Primary 05C55
MathSciNet review:
896015
Fulltext PDF Free Access
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]
F. G. Abramson and L. A. Harrington, Models without indiscernibles, J. Symbolic Logic 43 (1978), 572600. MR 503795 (80a:03045)
 [2]
W. Deuber, Generalizations of Ramsey's theorem, Colloq. Math. Soc. János Bolyai 10, NorthHolland, 1975 pp. 323332. MR 0369127 (51:5363)
 [3]
P. Erdös, Problems and results on finite and infinite graphs, Recent Advances in Graph Theory, Academic Press, pp. 183192. 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, NorthHolland, 1975, pp. 11271132. 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, NorthHolland, 1975, pp. 11271132. MR 0392695 (52:13512)
 [7]
, Type theory of partition problems of graphs, Recent Advances in Graph Theory, Academic Press, pp. 405412.
 [8]
, Ramsey property of graphs with forbidden complete subgraphs, J. Combin. Theory Ser. B 20, (1976), 243249. MR 0412004 (54:133)
 [9]
, On Ramsey graphs without cycles of short odd length, Comment Math. Univ. Carolin. 29 (1979), 565582. MR 550457 (81b:05083)
 [10]
, Two proofs of the Ramsey property of the class of finite hypergraphs, European J. Combin. 3 (1982), 347352. MR 687733 (85b:05134)
 [11]
, Simple proof of the existence of restricted Ramsey graphs by means of a partite construction, Combinatorica 1 (1982), 199202. 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), 225227. 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), 264286.
 [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. 211220.
 [1]
 F. G. Abramson and L. A. Harrington, Models without indiscernibles, J. Symbolic Logic 43 (1978), 572600. MR 503795 (80a:03045)
 [2]
 W. Deuber, Generalizations of Ramsey's theorem, Colloq. Math. Soc. János Bolyai 10, NorthHolland, 1975 pp. 323332. MR 0369127 (51:5363)
 [3]
 P. Erdös, Problems and results on finite and infinite graphs, Recent Advances in Graph Theory, Academic Press, pp. 183192. 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, NorthHolland, 1975, pp. 11271132. 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, NorthHolland, 1975, pp. 11271132. MR 0392695 (52:13512)
 [7]
 , Type theory of partition problems of graphs, Recent Advances in Graph Theory, Academic Press, pp. 405412.
 [8]
 , Ramsey property of graphs with forbidden complete subgraphs, J. Combin. Theory Ser. B 20, (1976), 243249. MR 0412004 (54:133)
 [9]
 , On Ramsey graphs without cycles of short odd length, Comment Math. Univ. Carolin. 29 (1979), 565582. MR 550457 (81b:05083)
 [10]
 , Two proofs of the Ramsey property of the class of finite hypergraphs, European J. Combin. 3 (1982), 347352. MR 687733 (85b:05134)
 [11]
 , Simple proof of the existence of restricted Ramsey graphs by means of a partite construction, Combinatorica 1 (1982), 199202. 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), 225227. 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), 264286.
 [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. 211220.
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/S00029947198708960158
PII:
S 00029947(1987)08960158
Article copyright:
© Copyright 1987
American Mathematical Society
