Computer Science/Discrete Mathematics Seminar I
Universal Graphs
Let F be a family of graphs. A graph H is *F-universal* if every G∈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 Ωk(n2−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 Ok(n2−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∈F(n,k) in H(n,k). Joint work with Noga Alon.