Alon, N.; Hajnal, András Ramsey graphs contain many distinct induced subgraphs. (English) Zbl 0728.05044 Graphs Comb. 7, No. 1, 1-6 (1991). 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)}}\). Reviewer: J.E.Graver (Syracuse) Cited in 4 Documents MSC: 05C55 Generalized Ramsey theory Keywords:number of isomorphism types of induced subgraphs; maximum number of vertices in a trivial induced subgraph; Ramsey graphs PDFBibTeX XMLCite \textit{N. Alon} and \textit{A. Hajnal}, Graphs Comb. 7, No. 1, 1--6 (1991; Zbl 0728.05044) Full Text: DOI References: [1] Alon, N.: Ramsey graphs cannot be defined by real polynomials. J. Graph Theory, in press. · Zbl 0743.05025 [2] Alon, N., Bollobás, B.: Graphs with a small number of distinct induced subgraphs. Discrete Math.75, 23–30 (1989) · Zbl 0681.05060 [3] Erdös, P.: Some remarks on the theory of graphs. Bull. Am. Math. Soc.53, 292–294 (1947) · Zbl 0032.19203 [4] Erdös, P., Hajnal, A.: Ramsey type theorems. Discrete Applied Math.25, 37–52 (1989) · Zbl 0715.05052 [5] Erdös, P., Hajnal, A.: On the number of distinct induced subgraphs of a graph. Discrete Math.75, 145–154 (1989) · Zbl 0668.05037 [6] Graham, R.L., Rothschild, B.L., Spencer, J.H.: Ramsey Theory. New York: Wiley Interscience 1980 [7] Rödl, V.: Private communication · Zbl 1207.68077 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.