Source-linked AI summary
On the logarithimic calculus and Sidorenko's conjecture
J. L. Xiang Li, Balazs Szegedy
TL;DR
The paper studies proof methods for Sidorenko’s conjecture, which asks whether t(H,W) ≥ t(P2,W)^e for every bipartite H and bounded non-negative measurable W. The paper develops a method motivated by earlier entropy calculations in this area. The paper proves that reflection trees are Sidorenko graphs and gives an analytic proof of the result for bipartite graphs with one vertex complete to the other side, also implying their forcing conjecture.
Problem
The paper studies proof methods for Sidorenko’s conjecture, which asks whether t(H,W) ≥ t(P2,W)^e for every bipartite H and bounded non-negative measurable W.
Source: §1 · p. 2Method
The paper develops a method motivated by earlier entropy calculations in this area.
Source: §1 · p. 2Results
The paper proves that reflection trees are Sidorenko graphs and gives an analytic proof of the result for bipartite graphs with one vertex complete to the other side, also implying their forcing conjecture.
Source: §1 · pp. 2–3Takeaways & Limitations
Logarithmic calculus supplies an iterative route to proving Sidorenko’s conjecture through stronger inequalities preserved by gluing operations.
Source: §1 · p. 3
Abstract
from arXiv · showhide
We study a type of calculus for proving inequalities between subgraph densities which is based on Jensen's inequality for the logarithmic function. As a demonstration of the method we verify the conjecture of Erd\"os-Simonovits and Sidorenko for new families of graphs. In particular we give a short analytic proof for a result by Conlon, Fox and Sudakov. Using this, we prove the forcing conjecture for bipartite graphs in which one vertex is complete to the other side.
1 Introduction
The paper develops a logarithmic calculus for subgraph-density inequalities and applies it to Sidorenko’s and the forcing conjectures. It proves Sidorenko’s conjecture for reflection trees and establishes an edge-gluing principle that yields further examples.
Motivation
- The framework is motivated by limitations of the Cauchy–Schwarz calculus, since every true density inequality may require infinitely many Cauchy–Schwarz inequalities and the general problem is undecidable.The paper positions logarithmic calculus as an alternative symbolic framework for these inequalities.Source: §1 · p. 2
Method
- The logarithmic calculus uses Jensen’s inequality for ln z and convexity of z ln z to prove subgraph-density inequalities through symbolic calculations.The approach may suit computer-based algorithms for discovering new inequalities.Source: §1 · p. 2
Problem
- Sidorenko’s conjecture asserts that every bipartite graph H satisfies t(H,W) ≥ t(P2,W)^e for every bounded non-negative measurable W.Here P2 is the single edge and e is the number of edges in H; the forcing conjecture further characterizes equality for non-trees.Source: §1 · p. 2
Applications
- The calculus gives an analytic proof of the result for bipartite graphs with one vertex complete to the other side and also implies the forcing conjecture for those graphs.The earlier proof used the tensor power trick and dependent random choice.Source: §1 · p. 2
New graph families
- Reflection trees are Sidorenko graphs, extending the families covered by the paper’s iterative gluing perspective.Reflection trees are obtained from trees by gluing reflected versions of subtrees.Source: §1 · pp. 2–3
Edge gluing
- If H1 and H2 are Sidorenko graphs, identifying arbitrary edges e1 and e2 produces another Sidorenko graph.The two edges may be identified in either of two ways.Source: §1 · p. 3
2 Basics of Logarithmic Calculus
The section develops a logarithmic calculus based on conditional expectations and Jensen’s inequality, then applies it to subgraph-density inequalities. It proves the Conlon–Fox–Sudakov result and derives the forcing conjecture for a class of bipartite graphs.
Logarithmic calculus
- Jensen’s inequality for logarithmic functions provides the central calculus for comparing subgraph densities through conditional expectations.The method uses both ln z and z ln z, with strict convexity or concavity characterizing equality.Source: §2 · p. 3
- The framework begins with notation for averaging functions over subsets of variables and identifies graph vertices with variables in the density formula.These conditional expectations satisfy E(g) = E(E_S(g)), enabling the graph-theoretic expressions used later.Source: §2 · p. 3
Applications
- The logarithmic-calculus approach gives a short analytic proof of the Conlon–Fox–Sudakov theorem for the specified bipartite graph family.The proof applies Jensen inequalities to functions associated with the common neighborhood structure and permits non-negative graphons via continuity or modified zero-valued functions.Source: §2 · p. 4
- The argument extends from strictly positive to non-negative graphons by continuity in L1 and by carefully replacing undefined zero-weight expressions with zero.The authors note that the proof’s calculations remain valid with these modified functions.Source: §2 · pp. 3–5
Forcing conjecture
- The forcing conjecture holds for bipartite graphs in which one vertex is complete to the other side, excluding trees.Equality in the density inequality forces intermediate quantities to be constant, and the proof concludes using that K2,a_t is forcing.Source: §2 · p. 5
3 Smoothness and Gluing
The paper develops smoothness as a strengthening of the Sidorenko property, using logarithmic-calculus inequalities to prove closure under unlabeling, gluing, and extensions. This framework yields Sidorenko’s conjecture for reflection trees, including even cycles and bipartite graphs with one vertex complete to the other side.
Smoothness
- Smoothness strengthens the Sidorenko property, and the logarithmic calculus proves the required subgraph-density inequalities using conditional expectations and Jensen’s inequality.When no labeled vertices remain, smoothness is equivalent to the Sidorenko property.Source: §3 · pp. 5–6
- A smooth graph remains smooth after unlabeling vertices outside a chosen nonempty subtree of its labeled tree.The proof reduces to unlabeling one leaf and iterating the resulting step.Source: §3 · pp. 6–7
- Every smooth graph is Sidorenko, via the unlabeling lemma and the lemma showing that a smooth graph containing a labeled edge is Sidorenko.This is summarized by Corollary 3.1.Source: §3 · p. 7
Gluing
- Smooth graphs with the same labeled tree can be glued together while preserving smoothness, and the smooth part can also be extended to a larger tree.These operations support constructing new Sidorenko graphs from existing ones.Source: §3 · p. 7
Reflection trees
- Labeling all points in one copy of T in the graph obtained from T 2 produces H, which is smooth; reflecting a subtree also yields a smooth tree T.Source: §3 · pp. 8–9
- Reflection trees are obtained from a tree by reflecting a collection of subtrees, and they include trees, even cycles, and bipartite graphs with one vertex complete to the other side.Theorem 1 states that every reflection tree is Sidorenko.Source: §3 · p. 8
4 Smoothness of edges
This section proves that every edge of a Sidorenko graph is smooth, establishing a special case of the conjectured connection between retracts and smoothness. The proof uses tensor powers and concentration of products of restricted homomorphism densities.
Main result
- Every edge is smooth in every Sidorenko graph, proving the stated special case of the conjecture that retract trees are smooth.The result is Theorem 5.Source: §4 · p. 10
Proof strategy
- The proof studies a fixed edge through tensor powers G^k, where restricted homomorphism densities form products of k independent copies.This converts the problem into analyzing the random variable X_k under a randomly chosen edge of G^k.Source: §4 · p. 10
- A positive lower bound on the proportion of edges with large restricted density combines with the law of large numbers to yield E(ln X_1) ≥ a ln d.The resulting inequality is equivalent to smoothness of the fixed edge.Source: §4 · p. 10
Consequence
- The edge-smoothness theorem immediately implies the edge-gluing theorem: gluing Sidorenko graphs along an edge preserves the Sidorenko property.The paper identifies this as a direct consequence of Theorem 5 and Lemma 3.4.Source: §4 · p. 10