Hostname: page-component-6898cfcb55-kwdml Total loading time: 0 Render date: 2026-11-11T21:31:35.225Z Has data issue: false hasContentIssue false
  • English
  • Français

Sizes of Induced Subgraphs of Ramsey Graphs

Published online by Cambridge University Press:  01 July 2009

NOGA ALON,
JÓZSEF BALOGH,
ALEXANDR KOSTOCHKA and
WOJCIECH SAMOTIJ
NOGA ALON
Affiliation:
Tel Aviv University, Tel Aviv 69978, Israel and IAS, Princeton, NJ, 08540, USA (e-mail: nogaa@tau.ac.il)
JÓZSEF BALOGH
Affiliation:
Department of Mathematics, University of Illinois, Urbana, IL 61801, USA (e-mail: jobal@math.uiuc.edu)
ALEXANDR KOSTOCHKA
Affiliation:
Department of Mathematics, University of Illinois, Urbana, IL 61801, USA and Sobolev Institute of Mathematics, Novosibirsk, Russia (e-mail: kostochk@math.uiuc.edu)
WOJCIECH SAMOTIJ
Affiliation:
Department of Mathematics, University of Illinois, Urbana, IL 61801, USA (e-mail: samotij2@illinois.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.

An n-vertex graph G is c-Ramsey if it contains neither a complete nor an empty induced subgraph of size greater than c log n. Erdős, Faudree and Sós conjectured that every c-Ramsey graph with n vertices contains Ω(n5/2) induced subgraphs, any two of which differ either in the number of vertices or in the number of edges, i.e., the number of distinct pairs (|V(H)|, |E(H)|), as H ranges over all induced subgraphs of G, is Ω(n5/2). We prove an Ω(n2.3693) lower bound.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 18 , Issue 4 , July 2009, pp. 459 - 476
Copyright
Copyright © Cambridge University Press 2009

References

[1]Alon, N. and Gutin, G. (1997) Properly colored Hamilton cycles in edge-colored complete graphs. Random Struct. Alg. 11 179–186.3.0.CO;2-P>CrossRefGoogle Scholar
[2]Alon, N. and Kostochka, A. (2009) Induced subgraphs with distinct sizes. Random Struct. Alg. 34 45–53.CrossRefGoogle Scholar
[3]Alon, N., Krivelevich, M. and Sudakov, B. (2003) Induced subgraphs of prescribed size. J. Graph Theory 43 239–251.CrossRefGoogle Scholar
[4]Alon, N. and Spencer, J. (2000) The Probabilistic Method, 2nd edn, Wiley.CrossRefGoogle Scholar
[5]Bollobás, B. and Scott, A. D. (2006) Discrepancy in graphs and hypergraphs. Bolyai Soc. Math. Studies 15 33–56.CrossRefGoogle Scholar
[6]Bukh, B. and Sudakov, B. (2007) Induced subgraphs of Ramsey graphs with many distinct degrees. J. Combin. Theory Ser. B 97 612–619.CrossRefGoogle Scholar
[7]Erdős, P. (1992) Some of my favorite problems in various branches of combinatorics. Matematiche (Catania) 47 231–240.Google Scholar
[8]Erdős, P. (1997) Some recent problems and results in graph theory. In The Second Kraków Conference on Graph Theory (Zgorzelisko, 1994), Discrete Math. 164 81–85.CrossRefGoogle Scholar
[9]Erdős, P., Goldberg, M., Pach, J. and Spencer, J. (1988) Cutting a graph into two dissimilar halves. J. Graph Theory 2 121–131.CrossRefGoogle Scholar
[10]Erdős, P. and Hajnal, A. (1977) On spanned subgraphs of graphs. In Contributions to Graph Theory and its Applications (Internat. Colloq., Oberhof, 1977), pp. 80–96.Google Scholar
[11]Erdős, P. and Szemerédi, E. (1972) On a Ramsey type theorem. In Collection of Articles Dedicated to the Memory of A. Rényi, Vol. I, Period. Math. Hungar. 2 295–299.CrossRefGoogle Scholar
[12]Prömel, H. J. and Rödl, V. (1999) Non-Ramsey graphs are c log n-universal. J. Combin. Theory Ser. A 88 379–384.CrossRefGoogle Scholar
[13]Shelah, S. (1998) Erdős and Rényi conjecture. J. Combin. Theory Ser. A 82 179–185.CrossRefGoogle Scholar