Ramsey graphs contain many distinct induced subgraphs
type: Item
instance of: scholarly article
title: Ramsey graphs contain many distinct induced subgraphs
zbMATH Open document ID: 0728.05044
DOI: 10.1007/BF01789457
published in: Graphs and Combinatorics
publication date: 1991-01-01T00:00:00Z
review text: 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)}}\).
reviewed by: Jack E. Graver
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 4202301
zbMATH Keywords: number of isomorphism types of induced subgraphs
zbMATH Keywords: maximum number of vertices in a trivial induced subgraph
zbMATH Keywords: Ramsey graphs
author: Noga Alon
author: Andras Hajnal
MaRDI profile type: Publication
cites work: Ramsey graphs cannot be defined by real polynomials
cites work: Graphs with a small number of distinct induced subgraphs
cites work: Some remarks on the theory of graphs
cites work: Ramsey-type theorems
cites work: On the number of distinct induced subgraphs of a graph
cites work: Q3656899
description: scientific article; zbMATH DE number 4202301