Strong Ramsey theorems for Steiner systems
HTML articles powered by AMS MathViewer
- by Jaroslav Nešetřil and Vojtěch Rödl PDF
- Trans. Amer. Math. Soc. 303 (1987), 183-192 Request permission
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
- Fred G. Abramson and Leo A. Harrington, Models without indiscernibles, J. Symbolic Logic 43 (1978), no. 3, 572–600. MR 503795, DOI 10.2307/2273534
- 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, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, pp. 323–332. MR 0369127
- 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
- A. Hajnal, Weak partition relations, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, pp. 817–836. MR 0389604
- Ronald L. Graham, Rudiments of Ramsey theory, CBMS Regional Conference Series in Mathematics, vol. 45, American Mathematical Society, Providence, R.I., 1981. MR 608630, DOI 10.1090/cbms/045
- 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, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, pp. 1127–1132. MR 0392695 —, Type theory of partition problems of graphs, Recent Advances in Graph Theory, Academic Press, pp. 405-412.
- 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 412004, DOI 10.1016/0095-8956(76)90015-0
- 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
- 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, DOI 10.1016/S0195-6698(82)80019-X
- 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, DOI 10.1007/BF02579274
- 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, DOI 10.1016/0095-8956(79)90084-4 H. J. Prömel and B. Voigt, Canonizing Ramsey theory (preprint 1985). F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. 30 (1930), 264-286. 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.
Additional Information
- © Copyright 1987 American Mathematical Society
- 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