Blog
Back to main  List of entries 
A reverse Sidorenko inequality
September 26, 2018
Together with undergraduates Ashwin Sah, Mehtaab Sawhney, and David Stoner (the same team that proved Kahn’s conjecture on independent sets that I blogged about earlier, we are excited to announce our new paper A reverse Sidorenko inequality. This paper solves several open problems concerning graph colorings and homomorphisms, including one of my favorite problems regarding maximizing the number of qcolorings in a dregular graph. I had previously blogged about some of these problems.
It has been truly a pleasure working with Ashwin, Mehtaab, and David on this project. I have learned so much from them.
Here are some highlights of our new results.
1. Graph colorings.
Among dregular graphs, which graph has the most number of proper qcolorings, exponentially normalized by the number of vertices of G?
We show that the extremal graph is the complete bipartite graph \(K_{d,d}\) (or disjoint unions thereof, as taking disjoint copies does not change the quantity due to the normalization).
2. Graph homomorphisms.
Among dregular graphs, which trianglefree graph G has the most number of homomorphisms into a fixed H, again exponentially normalized by the number of vertices of G?
We show that the extremal graph G is the complete bipartite graph \(K_{d,d}\).
The trianglefree hypothesis on G is best possible in general. For certain specific H, such as \(K_q\), corresponding to proper qcolorings as earlier, the trianglefree hypothesis can be dropped. It remains a wide open problem to determine for which H can one drop the trianglefree hypothesis on G.
3. Partition functions of Ferromagnetic spin models.
Among dregular graphs, which graph maximizes the logpartition function per vertex of a given Ferromagnetic spin model (e.g., Ising model)?
We show that the extremal graph is the clique \(K_{d+1}\).
For each setting, we establish our results more generally for irregular graphs as well, similar to our earlier work on independent sets.
Our results can be interpreted as a reverse form of the inequality in Sidorenko’s conjecture, an important open problem in graph theory stating a certain positive correlation on twovariable functions.
One can also view our results as a graphical analog of the Brascamp–Lieb inequalities, a central result in analysis.
This paper resolves one of my favorite open problems on this topic (the number of graph colorings). It also points us to many other open problems. Let me conclude by highlighting one of them (mentioned in #2 earlier). I’ll state it in a simpler form for dregular graphs, but it can be stated more generally as well.
Open problem. Classify all H with the following property: among dregular graphs G, the number of homomorphisms from G to H, exponentially normalized by the number of vertices of G, is maximized by \(G = K_{d,d}\).
Our results show that \(H = K_q\) works, even when some of its vertices are looped. Generalizing this case, we conjecture that all antiferromagnetic models H have the same property (though we know that this would not be the complete class, even if true).
Back to main

List of entries
