TY - JOUR

T1 - Asymptotically optimal induced universal graphs

AU - Alon, Noga

N1 - Funding Information:
Research supported in part by a USA-Israeli BSF Grant 2012/107, by an ISF Grant 620/13 and by the Israeli I-Core program.
Publisher Copyright:
© 2017, Springer International Publishing.

PY - 2017/2/1

Y1 - 2017/2/1

N2 - We prove that the minimum number of vertices of a graph that contains every graph on k vertices as an induced subgraph is (1 + o(1 ) ) 2 ( k - 1 ) / 2. This improves earlier estimates of Moon, of Bollobás and Thomason, of Brightwell and Kohayakawa and of Alstrup, Kaplan, Thorup and Zwick. The method supplies similarly sharp estimates for the analogous problems for directed graphs, tournaments, bipartite graphs, oriented graphs and more. We also show that if (nk)2-(k2)=λ (where λ can be a function of k) then the probability that the random graph G(n, 0.5) contains every graph on k vertices as an induced subgraph is (1-e-λ)2+o(1). The proofs combine combinatorial and probabilistic arguments with tools from group theory.

AB - We prove that the minimum number of vertices of a graph that contains every graph on k vertices as an induced subgraph is (1 + o(1 ) ) 2 ( k - 1 ) / 2. This improves earlier estimates of Moon, of Bollobás and Thomason, of Brightwell and Kohayakawa and of Alstrup, Kaplan, Thorup and Zwick. The method supplies similarly sharp estimates for the analogous problems for directed graphs, tournaments, bipartite graphs, oriented graphs and more. We also show that if (nk)2-(k2)=λ (where λ can be a function of k) then the probability that the random graph G(n, 0.5) contains every graph on k vertices as an induced subgraph is (1-e-λ)2+o(1). The proofs combine combinatorial and probabilistic arguments with tools from group theory.

KW - 05C35

KW - 05C80

UR - http://www.scopus.com/inward/record.url?scp=85011879021&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85011879021&partnerID=8YFLogxK

U2 - 10.1007/s00039-017-0396-9

DO - 10.1007/s00039-017-0396-9

M3 - Article

AN - SCOPUS:85011879021

VL - 27

JO - Geometric and Functional Analysis

JF - Geometric and Functional Analysis

SN - 1016-443X

IS - 1

ER -