Seminar Details
A Reverse Sidorenko Inequality
- Start Date: February 18, 2019
- Event Start Time: 2:00 PM
- Event End Time: 3:00 PM
- Seminar Series: Rutgers Discrete Mathematics Seminar
- Presenter(s): Yufei Zhao - Massachusetts Institute of Technology
- Event Location: Hill Center-Room 705
- Presentation Type: Stand Alone Presentation
- 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