Computer Science/Discrete Mathematics Seminar I

Let $F$ be a family of graphs. A graph $H$ is *$F$-universal* if every $G\in F$ is isomorphic to a subgraph of $H$. Besides being of theoretical interest, universal graphs have applications in chip design and network simulation. For any two positive integers $n$ and $k$, let $F(n,k)$ be the family of graphs on at most $n$ vertices with maximum degree at most $k$. It has been known that any $F(n,k)$-universal graph must have $\Omega_k(n^{2-2/k})$ edges. We show that this lower bound is tight up to a constant factor by presenting an explicit construction of a $F(n,k)$-universal graph $H(n,k)$ with $O_k(n^{2-2/k})$ edges, which is an improvement over the best previously known construction which uses a logarithmic (in $n$) factor more edges. We also present an efficient deterministic algorithm for finding a copy of each $G \in F(n,k)$ in $H(n,k)$. Joint work with Noga Alon.