×

Ramsey graphs contain many distinct induced subgraphs. (English) Zbl 0728.05044

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

MSC:

05C55 Generalized Ramsey theory
PDFBibTeX XMLCite
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.