An approximate version of Sidorenko's conjecture

Motivation

• Sidorenko’s conjecture predicts that every bipartite graph H has asymptotically at least as many copies in any graph G as in a random graph with the same edge density.The conjecture has equivalent homomorphism and analytic formulations and connects to matrix theory, Markov chains, graph limits, and quasirandomness.Source: §1 · p. 2

Quasirandomness

• The forcing conjecture asks whether a graph is forcing exactly when it is bipartite and contains a cycle.Forcing means that matching the expected densities of K2 and H forces quasirandomness; the conjecture would also yield stability for Sidorenko’s conjecture.Source: §1 · p. 3

Main results

• Sidorenko’s conjecture holds for every bipartite graph H with a vertex complete to the other part.This is obtained as a consequence of Theorem 1.1, whose hypotheses include a complete vertex and a minimum-degree condition in one part.Source: §1 · p. 3

Approximate Sidorenko bound

• For a bipartite graph with m edges and width w, the paper proves the approximate inequality t_H(G) ≥ t_K2(G)^(m+w) for every graph G.Width is defined through the minimum degree of the bipartite complement, summed over connected components; it is zero exactly when a connected component has a vertex complete to the other part.Source: §1 · p. 4

Quasirandomness

• The forcing conjecture holds for bipartite graphs with at least two vertices in one part complete to the other part, provided the graph has at least two vertices.This gives a stronger stability conclusion for the corresponding Sidorenko inequality.Source: §1 · pp. 3–4

Proof approach

• The proofs use simple combinatorial tools rather than the analytic approach previously suggested for Sidorenko’s conjecture.The proof outline invokes dependent random choice to control common neighborhoods and derive the key bound.Source: §1 · p. 4

Proof idea

• Dependent random choice shows that most small subsets of a suitable neighborhood have large common neighborhoods, enabling homomorphism counts close to the random-graph scale.The construction chooses the image of a complete vertex, then vertices in the opposite part, and finally images for the remaining vertices.Source: §2 · pp. 4–5

Proof of Theorem 1.1

• Good sequences retain at least half of the relevant K_{r,d} homomorphism mass, while rare sequences are controlled through convexity and neighborhood counting.A sequence is good when, for every d ≤ k ≤ n, it is not bad; the proof bounds bad pairs by summing over rare sequences.Source: §2 · p. 5
• The hypergraph lemma converts the abundance of non-rare sequences into a lower bound on homomorphisms from H to G.A random mapping fails on each hyperedge with bounded probability, so the union bound guarantees many mappings that preserve all required edges.Source: §2 · p. 6
• Tensor powers eliminate the positive constant factor in the preliminary estimate, yielding the desired inequality for every graph G.The tensor product satisfies t_H(F × G) = t_H(F)t_H(G), and applying the lemma to sufficiently large powers gives a contradiction otherwise.Source: §2 · p. 7

Corollary

• The argument extends the inequality to arbitrary bipartite H by adding edges through a minimum-degree vertex and decomposing disconnected graphs into components.For connected H, the augmented graph H′ has more edges and the theorem applies; disconnected homomorphism densities factor over components.Source: §2 · p. 8

Forcing result

• For graphs with two vertices complete to the opposite part, equality at the random-graph homomorphism scale forces quasirandomness, including when degree-one vertices are removed and later restored.The minimum-degree-at-least-two case uses K2,2 forcing; the degree-one case first proves that all but o(N) vertices have near-expected degree, then extends homomorphisms back to H.Source: §2 · pp. 8–9

• For bipartite graphs, Sidorenko’s conjecture implies the Ramsey multiplicity conjecture, while the paper’s theorems provide this implication and stability for a large class, with an approximate version for all bipartite graphs.Source: §3 · p. 9
• A proposed nonnegative-correlation inequality for edge-partitions would encompass Sidorenko’s conjecture and imply the forcing conjecture, but London’s example for P3 disproves it in general.Source: §3 · p. 9
• If the graph functional defined by the integral is a norm, then Sidorenko’s conjecture and, for graphs containing cycles, forcing follow; however, this norm class is smaller than the Sidorenko class.Source: §3 · pp. 9–10
• The broader comparison problem asks when ∥·∥H ≥ ∥·∥H′; known cases include complete-bipartite comparisons, while complete-tripartite analogues can fail and the general problem may be undecidable.Source: §3 · p. 10
• The hypergraph analogue of Sidorenko’s conjecture is false, because counterexamples exist for the natural extension to functions of more than two variables.Source: §3 · p. 10