ASYMPTOTICALLY OPTIMAL INDUCED UNIVERSAL GRAPHS

作者：Alon Noga^*

来源：Geometric and Functional Analysis, 2017, 27(1): 1-32.

DOI：10.1007/s00039-017-0396-9

We prove that the minimum number of vertices of a graph that contains every graph on kappa vertices as an induced subgraph is (1+omicron(1))2((kappa-1)/2). This improves earlier estimates of Moon, of Bollobas 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 ((n)(kappa))2(2)(-()(kappa)) = lambda (where lambda can be a function of kappa) then the probability that the random graph G(n, 0.5) contains every graph on kappa vertices as an induced subgraph is (1-e(-lambda))(2) + omicron(1). The proofs combine combinatorial and probabilistic arguments with tools from group theory.

• 出版日期2017-2