Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-08T15:27:08.466Z Has data issue: false hasContentIssue false
  • English
  • Français

Distance Preserving Ramsey Graphs

Published online by Cambridge University Press:  23 April 2012

DOMINGOS DELLAMONICA Jr  and
VOJTĚCH RÖDL
DOMINGOS DELLAMONICA Jr
Affiliation:
Department of Mathematics and Computer Science, Emory University, 400 Dowman Dr., W401, Atlanta, GA 30322, USA (e-mail: ddellam@mathcs.emory.edu, rodl@mathcs.emory.edu)
VOJTĚCH RÖDL
Affiliation:
Department of Mathematics and Computer Science, Emory University, 400 Dowman Dr., W401, Atlanta, GA 30322, USA (e-mail: ddellam@mathcs.emory.edu, rodl@mathcs.emory.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We prove the following metric Ramsey theorem. For any connected graph G endowed with a linear order on its vertex set, there exists a graph R such that in every colouring of the t-sets of vertices of R it is possible to find a copy G* of G inside R satisfying:

  • • distG*(x, y) = distR(x, y) for every x, y ∈ V(G*);

  • • the colour of each t-set in G* depends only on the graph-distance metric induced in G by the ordered t-set.

Keywords

Primary 05C55

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 21 , Issue 4 , July 2012 , pp. 554 - 581
Copyright
Copyright © Cambridge University Press 2012

References

[1]Abramson, F. G. and Harrington, L. A. (1978) Models without indiscernibles. J. Symbolic Logic 43 572–600.CrossRefGoogle Scholar
[2]Deuber, W. (1975) Generalizations of Ramsey's theorem. In Infinite and Finite Sets I: Colloq., Keszthely, 1973, dedicated to P. Erdős on his 60th birthday, Vol. 10 of Colloq. Math. Soc. János Bolyai, North-Holland, pp. 323–332.Google Scholar
[3]Deuber, W. (1975) Partitionstheoreme für Graphen. Comment. Math. Helv. 50 311–320.CrossRefGoogle Scholar
[4]Erdős, P., Hajnal, A. and Pósa, L. (1975) Strong embeddings of graphs into colored graphs. In Infinite and Finite Sets I: Colloq., Keszthely, 1973, dedicated to P. Erdős on his 60th birthday, Vol. 10 of Colloq. Math. Soc. János Bolyai, North-Holland, pp. 585–595.Google Scholar
[5]Graham, R. L., Grötschel, M. and Lovász, L., editors (1995) Handbook of Combinatorics, Vols 1, 2, Elsevier Science.Google Scholar
[6]Graham, R. L., Leeb, K. and Rothschild, B. L. (1972) Ramsey's theorem for a class of categories. Proc. Nat. Acad. Sci. USA 69 119–120.CrossRefGoogle ScholarPubMed
[7]Graham, R. L., Rothschild, B. L. and Spencer, J. H. (1990) Ramsey Theory, second edition, Wiley-Interscience Series in Discrete Mathematics and Optimization.Google Scholar
[8]Graham, R. L. and Winkler, P. M. (1984) Isometric embeddings of graphs. Proc. Nat. Acad. Sci. USA 81 7259–7260.CrossRefGoogle ScholarPubMed
[9]Hales, A. W. and Jewett, R. I. (1963) Regularity and positional games. Trans. Amer. Math. Soc. 106 222–229.CrossRefGoogle Scholar
[10]Nešetřil, J. (2005) Ramsey classes and homogeneous structures. Combin. Probab. Comput. 14 171–189.CrossRefGoogle Scholar
[11]Nešetřil, J. (2007) Metric spaces are Ramsey. European J. Combin. 28 457–468.CrossRefGoogle Scholar
[12]Nešetřil, J. and Rödl, V. (1975) Partitions of subgraphs. In Recent Advances in Graph Theory: Proc. Second Czechoslovak Sympos., Prague, 1974, Academia, pp. 413–423.Google Scholar
[13]Nešetřil, J. and Rödl, V. (1977) Partitions of finite relational and set systems. J. Combin. Theory Ser. A 22 289–312.CrossRefGoogle Scholar
[14]Nešetřil, J. and Rödl, V. (1978) On a probabilistic graph-theoretical method. Proc. Amer. Math. Soc. 72 417–421.CrossRefGoogle Scholar
[15]Nešetřil, J. and Rödl, V. (1979) Partition theory and its application. In Surveys in Combinatorics: Proc. Seventh British Combinatorial Conf., Cambridge, 1979, Vol. 38 of London Math. Soc. Lecture Note Ser., Cambridge University Press, pp. 96–156.CrossRefGoogle Scholar
[16]Nešetřil, J. and Rödl, V. (1979) A short proof of the existence of highly chromatic hypergraphs without short cycles. J. Combin. Theory Ser. B 27 225–227.CrossRefGoogle Scholar
[17]Nešetřil, J. and Rödl, V. (1984) Combinatorial partitions of finite posets and lattices: Ramsey lattices. Algebra Universalis 19 106–119.CrossRefGoogle Scholar
[18]Nešetřil, J. and Rödl, V. (1987) Strong Ramsey theorems for Steiner systems. Trans. Amer. Math. Soc. 303 183–192.CrossRefGoogle Scholar
[19]Nešetřil, J. and Rödl, V. (1989) The partite construction and Ramsey set systems. Discrete Math. 75 327–334.CrossRefGoogle Scholar
[20]Nešetřil, J. and Rödl, V. (1990) Introduction: Ramsey theory old and new. In Mathematics of Ramsey Theory, Vol. 5 of Algorithms Combin., Springer, pp. 1–9.CrossRefGoogle Scholar
[21]Nešetřil, J. and Rödl, V. (1992) On Ramsey graphs without bipartite subgraphs. Discrete Math. 101 223–229.CrossRefGoogle Scholar
[22]Rödl, V. (1973) A generalization of Ramsey theorem and dimension of graphs. Master's thesis, Charles University, Prague.Google Scholar
[23]Rödl, V. (1976) A generalization of the Ramsey theorem. In Graphs, Hypergraphs and Block Systems: Zielona Góra 1976, pp. 211–219.Google Scholar
[24]Winkler, P. M. (1984) Isometric embedding in products of complete graphs. Discrete Appl. Math. 7 221–225.CrossRefGoogle Scholar