Yufei Zhao, Massachusetts Institute of Technology

Abstract

We prove a number of tight graph homomorphism inequalities, where, for a fixed H, we wish to maximize the number of homomorphism from G to H (after exponentially normalizing by the size of G) under certain degree constraints on G (e.g., d-regular). A highlight of our results is that, among d-regular graphs of the same size, a disjoint complete bipartite graphs has the most number of proper q-colorings. Our results also extend to irregular graphs and list colorings. These results settle a number of conjectures by Kahn, Galvin-Tetali, Galvin, and Cohen-Csikvári-Perkins-Tetali.
Joint work with Ashwin Sah, Mehtaab Sawhney, and David Stoner