Asymptotically optimal induced universal graphs

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

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)
JournalGeometric and Functional Analysis
Volume27
Issue number1
DOIs
StatePublished - Feb 1 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Analysis
  • Geometry and Topology

Keywords

  • 05C35
  • 05C80

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

Cite this