Event time:
Thursday, January 31, 2019 - 4:00pm
Location:
DL 431
Speaker:
Yufei Zhao
Speaker affiliation:
MIT
Event description:
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
Research Area(s):