Asymptotically optimal induced universal graphs

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)1-32
Number of pages32
JournalGeometric and Functional Analysis
Issue number1
StatePublished - Feb 1 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Analysis
  • Geometry and Topology


  • 05C35
  • 05C80


Dive into the research topics of 'Asymptotically optimal induced universal graphs'. Together they form a unique fingerprint.

Cite this