Explicit Sparse Almost-Universal Graphs for G(n, k/n)
For any integer n, let 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 Gamma is G-almost-universal if Gamma satisifies the following: If G is chosen according to the probability distribution G, then G is isomorphic to a subgraph of Gamma with probability 1 - 1/root n. For any p is an element of [0, 1], let 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 is an element of V(G) are mutually independent. For k >= 4 and n sufficiently large we construct a G(n, k/n)-almost-universal-graph on n vertices and with O(n(2-q-1)) polylog(n) edges, where q = inverted right perpendicular k+3/2 inverted left perpendicular for such k  = 7. The number of edges is close to the lower bound of Omega (n(2-2/k)) for the number of edges in a universal graph for the family of graphs with n vertices and maximum degree k. (C) 2010 Wiley Periodicals, Inc. Random Struct. Alg., 37, 437-454, 2010
universal graphs random graphs erdos-renyi