Ramsey graphs contain many distinct induced subgraphs
Let G denote a finite, simple, undirected graph, and let i(G) denote the total number of isomorphism types of induced subgraphs of G. An induced subgraph of G is said to be trivial if it is either independent or a clique. Let t(G) denote the maximum number of vertices in a trivial induced subgraph of G. One of the well-known results in Ramsey theory is that t(G)\(\geq (1/2)\log n\) (where n is the number of vertices in G and log is the logarithm to the base 2). The graphs G for which t(G) is very small with respect to n are sometimes called Ramsey graphs. The main result of this paper (Theorem 1.1 below) shows that these graphs behave like random graphs in that the number of distinct induced subgraphs is large. Theorem 1.1. For any graph G on n vertices with \(t=t(G):\) \(i(G)\geq 2^{n/2t^{2O\log (2t)}}\).
- On the number of induced subgraphs of a random graph
- On the number of distinct induced subgraphs of a graph
- Erdős and Rényi conjecture
- Graphs with a small number of distinct induced subgraphs
- Ramsey graphs induce subgraphs of many different sizes
- Isomorphisms between random graphs
- Distinct degrees in induced subgraphs
- scientific article; zbMATH DE number 15664 (Why is no real title available?)
- SOME OF MY FAVORITE SOLVED AND UNSOLVED PROBLEMS IN GRAPH THEORY
- scientific article; zbMATH DE number 786171 (Why is no real title available?)
- Proof of a conjecture on induced subgraphs of Ramsey graphs
- Almost every n-vertex graph is determined by its 3 _2n-vertex subgraphs
- Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
- Small but unwieldy: a lower bound on adjacency labels for small classes
- Induced subgraphs of Ramsey graphs with many distinct degrees
This page was built for publication: Ramsey graphs contain many distinct induced subgraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q804596)
