Ramsey graphs contain many distinct induced subgraphs (Q804596)

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)}}\).