Hostname: page-component-745bb68f8f-f46jp Total loading time: 0 Render date: 2025-02-06T22:19:02.219Z Has data issue: false hasContentIssue false
  • English
  • Français

Induced Subgraphs With Many Distinct Degrees

Part of: Extremal combinatorics Graph theory

Published online by Cambridge University Press:  01 August 2017

BHARGAV NARAYANAN  and
ISTVÁN TOMON
BHARGAV NARAYANAN
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: b.p.narayanan@dpmms.cam.ac.uk, i.tomon@dpmms.cam.ac.uk)
ISTVÁN TOMON
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: b.p.narayanan@dpmms.cam.ac.uk, i.tomon@dpmms.cam.ac.uk)
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.

Let hom(G) denote the size of the largest clique or independent set of a graph G. In 2007, Bukh and Sudakov proved that every n-vertex graph G with hom(G) = O(logn) contains an induced subgraph with Ω(n1/2) distinct degrees, and raised the question of deciding whether an analogous result holds for every n-vertex graph G with hom(G) = O(nϵ), where ϵ > 0 is a fixed constant. Here, we answer their question in the affirmative and show that every graph G on n vertices contains an induced subgraph with Ω((n/hom(G))1/2) distinct degrees. We also prove a stronger result for graphs with large cliques or independent sets and show, for any fixed k ∈ ℕ, that if an n-vertex graph G contains no induced subgraph with k distinct degrees, then hom(G)⩾n/(k − 1) − o(n); this bound is essentially best possible.

MSC classification

Primary: 05D10: Ramsey theory
Secondary: 05C07: Vertex degrees
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 1 , January 2018 , pp. 110 - 123
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Alon, N. and Spencer, J. H. (2008) The Probabilistic Method, third edition, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley.Google Scholar
[2] Barak, B., Rao, A., Shaltiel, T. and Wigderson, A. (2012) 2-source dispersers for n o(1) entropy, and Ramsey graphs beating the Frankl–Wilson construction. Ann. of Math. 176 1483–1543.Google Scholar
[3] Bukh, B. and Sudakov, B. (2007) Induced subgraphs of Ramsey graphs with many distinct degrees. J. Combin. Theory Ser. B 97 612–619.Google Scholar
[4] Caro, Y. (1979) New results on the independence number. Technical report, Tel Aviv University.Google Scholar
[5] Chattopadhyay, E. and Zuckerman, D. (2016) Explicit two-source extractors and resilient functions. In STOC 2016: Proc. 48th Annual ACM Symposium on the Theory of Computing, ACM, pp. 670–683.Google Scholar
[6] Cohen, G. (2016) Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs. In STOC 2016: Proc. 48th Annual ACM Symposium on the Theory of Computing, ACM, pp. 278–284.Google Scholar
[7] Erdős, P. (1947) Some remarks on the theory of graphs. Bull. Amer. Math. Soc. 53 292–294.CrossRefGoogle Scholar
[8] Erdős, P. (1992) Some of my favourite problems in various branches of combinatorics. Matematiche (Catania) 47 231–240.Google Scholar
[9] Erdős, P. and Szekeres, G. (1935) A combinatorial problem in geometry. Compositio Math. 2 463–470.Google Scholar
[10] Erdős, P. and Szemerédi, A. (1972) On a Ramsey type theorem. Period. Math. Hungar. 2 295–299.Google Scholar
[11] Grolmusz, V. (2000) Low rank co-diagonal matrices and Ramsey graphs. Electron. J. Combin. 7 R15.CrossRefGoogle Scholar
[12] Prömel, H. J. and Rödl, V. (1999) Non-Ramsey graphs are clogn-universal. J. Combin. Theory Ser. A 88 379–384.Google Scholar
[13] Shelah, S. (1998) Erdős and Rényi conjecture. J. Combin. Theory Ser. A 82 179–185.Google Scholar
[14] Wei, V. K. (1981) A lower bound on the stability number of a simple graph. Technical memorandum TM 81-11217-9, Bell Laboratories.Google Scholar