Universality of Random Graphs
Universality of Random Graphs
We prove that asymptotically (as $n\to\infty$) almost all graphs with n vertices and $C_dn^{2-\frac{1}{2d}} \log^{\frac{1}{d}} n$ edges are universal with respect to the family of all graphs with maximum degree bounded by d. Moreover, we provide an efficient deterministic embedding algorithm for finding copies of bounded degree graphs in graphs …