Explicit sparse almost‐universal graphs for ${\bf {{\cal G}(n, {k \over n})}}$

Abstract For any integer n , let ${\cal G}$ be a probability distribution on the family of graphs on n vertices (where every such graph has nonzero probability associated with it). A graph Γ is ${\cal G}$ ‐almost‐universal if Γ satisifies the following: If G is chosen according to the probability distribution ${\cal G}$ , then G is isomorphic to a subgraph of Γ with probability 1 ‐ ${1 \over \sqrt{n}}$ . For any p ∈ [0,1], let ${\cal G}$ ( n , p ) denote the probability distribution on the family of graphs on n vertices, where two vertices u and v form an edge with probability p , and the events { u and v form an edge}; u , v ∈ V ( G ) are mutually independent. For k ≥ 4 and n sufficiently large we construct a ${{\cal G}(n, {k \over n})}$ ‐almost‐universal‐graph on n vertices and with O ( n   2‐ q   ‐1)polylog( n ) edges, where q = ⌈ ${k + 3 \over 2}$ ⌉ for such k ≤ 6, and where q = ⌈ ${k + 2 \over 2}$ ⌉ for k ≥ 7. The number of edges is close to the lower bound of Ω ( ${n^{2- {2 \over k}}}$ ) for the number of edges in a universal graph for the family of graphs with n vertices and maximum degree k . © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010