Universal Graphs

COMPUTER SCIENCE/DISCRETE MATH I
Topic:Universal Graphs
Speaker:Michael Capalbo
Affiliation:DIMACS
Date:Monday, May 8
Time/Room:11:15am - 12:15pm/S-101

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.