## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, January 24, 2017, 12:15 pm

Duration: 30 minutes

Location: CAB G51

## Optimal induced universal graphs for bounded-degree graphs

We show that for any constant $\Delta \ge 2$, there exists a graph $\Gamma$ with $O(n^{\Delta / 2})$ vertices which contains every $n$-vertex graph with maximum degree $\Delta$ as an induced subgraph. For odd $\Delta$ this significantly improves the best-known earlier bound of Esperet et al. and is optimal up to a constant factor, as it is known that any such graph must have at least $\Omega(n^{\Delta/2})$ vertices.

Our proof builds on the approach of Alon and Capalbo (SODA 2008) together with several additional ingredients. The construction of $\Gamma$ is explicit and is based on an appropriately defined composition of high-girth expander graphs. The proof also provides an efficient deterministic procedure for finding, for any given input graph $H$ on $n$ vertices with maximum degree at most $\Delta$, an induced subgraph of $\Gamma$ isomorphic to $H$.

This is joint work with Noga Alon.

Information for students and suggested topics for student talks