Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

A Reverse Sidorenko Inequality

Yufei Zhao, MIT

Location:  Hill 705
Date & time: Monday, 18 February 2019 at 2:00PM - 3:00PM

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

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.