An information theoretic approach to Sidorenko's conjecture

1 introduction

• The results suggest that a topological phenomenon may underlie a complete classification of graphs and hypergraphs satisfying Sidorenko’s conjecture.The framework also works in the non-symmetric multipartite setting with minor modifications.Source: §1 · pp. 2–3
• A probability scheme built by gluing along forest-spanning subsets yields graphs satisfying Sidorenko’s conjecture.This includes tree-arrangeable graphs, graphs with one side of size at most 4, and hypercubes up to dimension 5.Source: §1 · p. 2
• Thick graphs, defined through line graphs of suitable reflection complexes, satisfy Sidorenko’s conjecture and contain all previously known examples.They are closed under a subdivision operation using spanned forests, including the □-product with a tree.Source: §1 · p. 3
• If H is thick and T is a tree, then H□T is thick, placing high-dimensional grids and hypercubes among the resulting examples.The paper notes that the hypercube examples constructed in, including hypercubes, are thick graphs.Source: §1 · p. 3
• The information-theoretic method replaces uniform homomorphism measures with witness measures whose relative entropy can be controlled.Conditional independent couplings provide an inclusion-exclusion formula for analyzing the resulting relative entropy.Source: §1 · p. 3
• The approach extends to k-uniform hypergraphs, producing large families satisfying Sidorenko’s conjecture even though the conjecture fails for general k-uniform hypergraphs when k > 2.The paper proves a hypergraph analogue of the Bakley-Roy inequality.Source: §1 · p. 3

• Relative entropy is defined through Eµ(log(dµ/dν)) for absolutely continuous probability measures, with entropy inequalities supplying its basic lower bounds.Source: §2 · p. 4
• A coupling joins two probability spaces over a shared joint factor while preserving both marginal measures through the coordinate projections.Source: §2 · p. 4
• The conditionally independent coupling is formed over the common factor and preserves the prescribed marginals of both component spaces.Source: §2 · p. 4
• The entropy calculation yields an inclusion-exclusion identity for conditionally independent couplings, providing the central mechanism for later witness-measure arguments.Source: §2 · pp. 4–5
• Among couplings over the same joint factor, the conditionally independent coupling minimizes relative entropy with respect to its corresponding conditionally independent reference coupling.Source: §2 · pp. 4–5

• A witness measure is a probability distribution on Hom(H, G) whose relative entropy is at most |E(H)|De; such a measure proves Sidorenko’s conjecture for H in G.Source: §3 · p. 5
• Probability schemes assign distributions on homomorphisms, and coupling structures generate new schemes from the uniform edge distribution through conditionally independent couplings over joint vertex factors.Source: §3 · p. 6
• Every coupling-structure distribution has identical edge marginals τ(e, G) and identical vertex marginals κ, while every coupling frame is necessarily bipartite.Source: §3 · p. 6
• Every scheme using only couplings over independent vertex sets yields witness measures, so its frame satisfies Sidorenko’s conjecture.Source: §3 · p. 6
• The forest-gluing extension likewise produces witness measures, covering tree-arrangeable graphs and incorporating trees, reflection trees, even cycles, and graphs with one complete vertex.Source: §3 · p. 7

• The generalized method studies restrictions of coupling structures to vertex subsets and records conditional independence and isomorphism relations among those restrictions.Source: §4 · p. 8
• The spaces Cf and If encode, respectively, conditional-independence relations and equalities between isomorphic vertex factors.Source: §4 · p. 8
• If sH(A) belongs to Cf + If + QV, then the graph induced by A satisfies Sidorenko’s conjecture.Source: §4 · p. 8
• The proof defines g(B) := D(fB(G)) for B ⊆ V(H), establishes its supermodularity, and uses encoded relations to derive (sH(A), g) ≥ 0.Source: §4 · p. 8
• Because the condition is a finite linear-programming feasibility problem, membership in the relevant cone can be decided computationally.Source: §4 · p. 9

• A b-hypergraph augments a hypergraph with a symmetric binary relation on vertex subsets, and its frame consists of its two-element edges.Source: §5 · pp. 9–10
• The gluing operations identify vertices with matching labels and combine edges and relations, with the extended operation adding cross-component edges and relations.Source: §5 · p. 9
• A reflection complex is obtained from the trivial reflection complex by a finite sequence of operations rL,X, and its full vertex set remains an edge.Source: §5 · pp. 9–10
• Every reflection complex is 2-reducible: every edge larger than two vertices has a proper decomposition into smaller edges linked by the binary relation.Source: §5 · p. 10
• The reflection operation does not add new two-element edges, yielding a controlled description of the resulting frame.Source: §5 · p. 10

6 Thick reflection complexes and graphs

• A reflection complex is thick when its defining vector lies in the cone W_B + Q_V.The cone W_B + Q_V is described as large enough to contain h_H(V).Source: §6 · pp. 10–11
• Thick graphs satisfy Sidorenko’s conjecture.Frames of thick reflection complexes are called thick graphs.Source: §6 · pp. 10–11
• Weak thickness would also imply Sidorenko’s conjecture, but the paper gives no example that is weakly thick without being thick.Thickness is noted to behave better under certain operations than weak thickness.Source: §6 · p. 11
• For forests H, the quantity −h_H(V) belongs to Q_V, providing the inductive ingredient for thickness closure.The proof decomposes a forest into smaller overlapping subgraphs.Source: §6 · p. 11
• If two thick b-hypergraphs are glued along an isomorphic forest, the resulting b-hypergraph remains thick.The proof combines the two thickness conditions with the forest lemma.Source: §6 · pp. 11–12
• For a reflection complex M in C, every edge spans a thick b-hypergraph, and therefore M is a thick reflection complex; this includes the stated forest-operation setting.Source: §6 · p. 12

7 Subdivisions of graphs and reflection complexes

• A reflection-complex subdivision replaces each point of the base graph by J1 or J2 and each frame edge by a copy of the subdividing complex.The resulting frame is the corresponding graph subdivision, independent of the construction sequence used for the complex.Source: §7 · pp. 12–13
• If H1 and H2 are thick and J1,J2 span disjoint forests in H1, their {H1,J1,J2} subdivision of H2 is thick.The proof establishes thickness for the corresponding subdivided reflection complex.Source: §7 · pp. 12, 14
• If H1 is a tree and H2 is thick, then the Cartesian product H1□H2 is thick.This extends the previously known closure under □-products with trees to thick graphs.Source: §7 · p. 13
• The maps γ_i track subsets through the recursive subdivision and preserve the relevant unions, intersections, and relation terms.Their linear extension γ* maps the original cone W_B into the subdivided cone.Source: §7 · p. 13
• The thickness proof combines the original complex’s thickness with the subdividing complex’s thickness and the forest condition on each inserted copy.These ingredients place the resulting h-vector in the target cone.Source: §7 · p. 14

8 Reflection complexes and coupling structures

• The coupling is constructed inductively by taking a conditionally independent coupling over the shared coordinates of each reflection operation.Uniqueness follows from the uniqueness of the relevant marginals.Source: §8 · pp. 14–15
• Every reflection complex has a unique coupling structure with its frame, uniform random-edge marginals, and conditional independence on each relation pair.The coupling also assigns every edge of the complex to the required admissible family.Source: §8 · p. 14
• Frames of reflection complexes are coupling frames.This is stated as Corollary 8.1 for every reflection complex.Source: §8 · p. 15
• The coupling structure converts the thickness condition s_H(V) ∈ W_B + Q_V into Sidorenko’s conjecture for the frame H.The proof uses the coupling theorem and the general information-theoretic result.Source: §8 · p. 15

9 Hypergraphs

• The results generalize to k-uniform hypergraphs, with the trivial k-reflection complex defined as the single k-edge {1, 2, . . ., k} with the trivial binary relation.Lemma 5.1 is changed to state that k-reflection complexes are k-reducible, and the proof is basically identical.Source: §9 · pp. 15–16
• Every weakly thick k-uniform hypergraph satisfies Sidorenko’s conjecture.Weak thickness is defined through s_H(V) ∈ W_B + Q_V for a k-reflection complex frame.Source: §9 · p. 16
• The class Z_k contains isolated points and non-intersecting k-edges, for which −s_H(V) belongs to Q_V.This property supplies the hypergraph analogue of the forest lemma.Source: §9 · p. 16
• Hypergraphs in R_k are weakly thick and therefore satisfy Sidorenko’s conjecture.R_k consists of frames built using operations whose inserted subhypergraphs belong to Z_k.Source: §9 · p. 16
• The resulting family R_k contains hypergraph analogues of forests and connects the theorem to the Blakley-Roy inequality and work of Conlon-Fox and Sudakov.The passage presents this as a hypergraph generalization of those results.Source: §9 · p. 16

Reflection trees

• Reflection trees lie in R and are thick graphs, encompassing bipartite graphs with one side complete to the other and all even cycles.Source: §10 · p. 17

Tree-arrangeable graphs

• Tree-arrangeable graphs satisfy Sidorenko’s conjecture and are all thick graphs, because their construction operations can be represented by reflections.Source: §10 · p. 17

Hypercubes and grids

• Hypercubes and grids satisfy Sidorenko’s conjecture and are thick graphs, while hypercubes through dimension 5 also belong to R.Source: §10 · pp. 17–18
• The authors conjecture that sufficiently high-dimensional hypercubes leave R, which would make the thick-graph class strictly larger than R.Source: §10 · p. 17

Bipartite graphs with at most 4 vertices on one side

• Bipartite graphs with at most four vertices on one side are contained in R and therefore are thick, although the proof involves tedious case analysis.Source: §10 · p. 18

Hypergraph forests and other hypergraph examples

• The paper defines k-forests recursively by gluing a new k-edge along a subset of an existing edge, and proves that every k-forest satisfies Sidorenko’s conjecture.Source: §10 · p. 18
• This hypergraph result yields a generalization of the Blakley-Roy inequality for symmetric non-negative functions on [0,1]^k.Source: §10 · p. 18
• The class R_k contains additional Sidorenko hypergraphs, including the face-hypergraph of the octahedron and complete k-uniform, k-partite hypergraphs.Source: §10 · p. 19