Induced subgraphs with many distinct degrees

DOI10.1017/S0963548317000256MaRDI QIDQ4601057zbMATH OpenOpenAlexFDO

Authors Bhargav P. Narayanan, István Tomon

Publication date 19 January 2018

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.01677

zbMATH Keywords

distinct degreesErdős problemRamsey graphs

Mathematics Subject Classification ID

Vertex degrees (05C07) Generalized Ramsey theory (05C55) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Ramsey theory (05D10)

Abstract: 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 $Omega(n^{1/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^{e}psilon)$, where $epsilon>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 $Omega((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 $kinmathbbN$, that if an $n$-vertex graph $G$ contains no induced subgraph with $k$ distinct degrees, then $hom(G)gen/(k-1)-o(n)$; this bound is essentially best-possible.

Recommendations

• Induced subgraphs of Ramsey graphs with many distinct degrees
• Distinct degrees and homogeneous sets
• Distinct degrees in induced subgraphs
• Large induced subgraphs with equated maximum degree
• Graphs Having Small Number of Sizes on Induced k‐Subgraphs

Cites work

• 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
• Erdős and Rényi conjecture
• Explicit two-source extractors and resilient functions
• scientific article; zbMATH DE number 554066 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• Induced subgraphs of Ramsey graphs with many distinct degrees
• Low rank co-diagonal matrices and Ramsey graphs
• Non-Ramsey graphs are c n-universal
• On a Ramsey type theorem
• Some remarks on the theory of graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs

Cited in

(11)

• Digraphs with degree equivalent induced subdigraphs
• Induced subgraphs with many repeated degrees
• Distinct degrees and homogeneous sets
• Large induced subgraphs with three repeated degrees
• Distinct degrees in induced subgraphs
• Induced subgraphs with distinct sizes
• Proof of a conjecture on induced subgraphs of Ramsey graphs
• Graphs Having Small Number of Sizes on Induced k‐Subgraphs
• A bipartite version of the Erdős–McKay conjecture
• Induced subgraphs of Ramsey graphs with many distinct degrees
• Large induced subgraphs with equated maximum degree

This page was built for publication: Induced subgraphs with many distinct degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601057)