Induced subgraphs of Ramsey graphs with many distinct degrees
It is shown that if \(G\) is a graph of order \(n\) such that \(\max\{\alpha(G), \omega(G)\} \leq C \log n\) for some constant \(C\), then \(G\) contains an induced subgraph of order \(\alpha n\) with \(\beta \sqrt{n}\) vertices of different degrees, where \(\alpha\) and \(\beta\) depend only on \(C\). This proves a conjecture of Erdős, Faudree, and Sós appearing in several of the survey papers of Erdős. It is also shown under the same conditions that there exists \(\Omega(n{3/2})\) induced subgraphs \(H\) of \(G\) with distinct pairs \((| V(H)| , | E(H)| )\). An outline of a proof of a corresponding result for tournaments is also given. If \(T\) is a tournament with trans\((T) \leq C\log n\) (where trans\((T)\) is the order of the largest transitive subtournament of \(T\)), then \(T\) contains an induced subtournament of order \(\alpha n\) with \(\beta \sqrt{n}\) vertices of different degrees, where \(\alpha\) and \(\beta\) depend only on \(C\).
- Erdős and Rényi conjecture
- Graphs with a small number of distinct induced subgraphs
- scientific article; zbMATH DE number 3628985 (Why is no real title available?)
- scientific article; zbMATH DE number 554066 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- scientific article; zbMATH DE number 3019031 (Why is no real title available?)
- Induced subgraphs of prescribed size
- Non-Ramsey graphs are c n-universal
- On a Ramsey type theorem
- On Subgraph Sizes in Random Graphs
- On the number of distinct induced subgraphs of a graph
- Ramsey graphs contain many distinct induced subgraphs
- Ramsey-type theorems
- Random regular tournaments
- Some extremal properties concerning transitivity in graphs
- Some recent problems and results in graph theory
- Some remarks on the theory of graphs
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Graphs with a small number of distinct induced subgraphs
- Distinct degrees and homogeneous sets
- Distinct degrees in induced subgraphs
- Sizes of induced subgraphs of Ramsey graphs
- Induced subgraphs with distinct sizes
- Rao's degree sequence conjecture
- Induced subgraphs with many distinct degrees
- Ramsey graphs induce subgraphs of quadratically many sizes
- An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs
- Proof of a conjecture on induced subgraphs of Ramsey graphs
- Graphs Having Small Number of Sizes on Induced k‐Subgraphs
- Induced Ramsey-type theorems
- Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
- Combinatorics. Abstracts from the workshop held January 1--7, 2023
- A bipartite version of the Erdős–McKay conjecture
- On the number of homogeneous subgraphs of a graph
- Ramsey graphs contain many distinct induced subgraphs
This page was built for publication: Induced subgraphs of Ramsey graphs with many distinct degrees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q885296)
