A Reverse Sidorenko Inequality

Combinatorics Seminar
Event time: 
Thursday, January 31, 2019 - 4:00pm
DL 431
Yufei Zhao
Speaker affiliation: 
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):