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.