Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Ramsey Graphs Induce Subgraphs of Many Different Sizes

  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

A graph on n vertices is said to be C-Ramsey if every clique or independent set of the graph has size at most C logn. The only known constructions of Ramsey graphs are probabilistic in nature, and it is generally believed that such graphs possess many of the same properties as dense random graphs. Here, we demonstrate one such property: for any fixed C > 0, every C-Ramsey graph on n vertices induces subgraphs of at least n2-o(1) distinct sizes. This near-optimal result is closely related to two unresolved conjectures, the first due to Erdős and McKay and the second due to Erdős, Faudree and Sós, both from 1992.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. N. Alon, J. Balogh, A. Kostochka and W. Samotij: Sizes of induced subgraphs of Ramsey graphs, Combin. Probab. Comput. 18 (2009), 459–476.

    Article  MathSciNet  MATH  Google Scholar 

  2. N. Alon and A. Kostochka: Induced subgraphs with distinct sizes, Random Structures Algorithms 34 (2009), 45–53.

    Article  MathSciNet  MATH  Google Scholar 

  3. N. Alon, M. Krivelevich and B. Sudakov: Induced subgraphs of prescribed size, J. Graph Theory 43 (2003), 239–251.

    Article  MathSciNet  MATH  Google Scholar 

  4. N. Alon and J. H. Spencer: The probabilistic method, 3rd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., Hoboken, NJ, 2008.

    Book  MATH  Google Scholar 

  5. B. Barak, A. Rao, T. Shaltiel and A. Wigderson: 2-source dispersers for no(1) entropy, and Ramsey graphs beating the Frankl-Wilson construction, Ann. of Math. 176 (2012), 1483–1543.

    MATH  Google Scholar 

  6. B. Bukh and B. Sudakov: Induced subgraphs of Ramsey graphs with many distinct degrees, J. Combin. Theory Ser. B 97 (2007), 612–619.

    Article  MathSciNet  MATH  Google Scholar 

  7. P. Erdős: Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292–294.

    Article  MathSciNet  MATH  Google Scholar 

  8. P. Erdős and G. Szekeres: A combinatorial problem in geometry, Compositio Math. 2 (1935), 463–470.

    MathSciNet  MATH  Google Scholar 

  9. P. Erdős: Some of my favourite problems in various branches of combinatorics, Matematiche (Catania) 47 (1992), 231–240.

    MathSciNet  MATH  Google Scholar 

  10. P. Erdős: Some recent problems and results in graph theory, Discrete Math. 164 (1997), 81–85.

    Article  MathSciNet  MATH  Google Scholar 

  11. P. Erdős and A. Szemerédi: On a Ramsey type theorem, Period. Math. Hungar. 2 (1972), 295–299.

    Article  MathSciNet  MATH  Google Scholar 

  12. P. Frankl and R. M. Wilson: Intersection theorems with geometric consequences, Combinatorica 1 (1981), 357–368.

    Article  MathSciNet  MATH  Google Scholar 

  13. W. Hoeffding: Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963), 13–30.

    Article  MathSciNet  MATH  Google Scholar 

  14. H. J. Prömel and V. Rödl: Non-Ramsey graphs are c logn-universal, J. Combin. Theory Ser. A 88 (1999), 379–384.

    Article  MathSciNet  MATH  Google Scholar 

  15. F. P. Ramsey: On a problem of formal logic, Proc. London Math. Soc. 30 (1930), 264–286.

    Article  MathSciNet  MATH  Google Scholar 

  16. S. Shelah: Erdős and Rényi conjecture, J. Combin. Theory Ser. A 82 (1998), 179–185.

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge, CB3 0WB, UK

    Bhargav Narayanan & István Tomon

  2. Department of Mathematical Sciences, University of Memphis, Memphis, TN, 38152, USA

    Julian Sahasrabudhe

Authors
  1. Bhargav Narayanan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Julian Sahasrabudhe
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. István Tomon
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bhargav Narayanan.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Narayanan, B., Sahasrabudhe, J. & Tomon, I. Ramsey Graphs Induce Subgraphs of Many Different Sizes. Combinatorica 39, 215–237 (2019). https://doi.org/10.1007/s00493-017-3755-0

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00493-017-3755-0

Mathematics Subject Classification (2010)

Search

Navigation