OctoInformBeta

A counterexample to Sidorenko’s conjecture

For finite simple graphs HH and GG, let hom⁡(H,G)\hom(H,G) be the number of edge-preserving maps from V(H)V(H) to V(G)V(G), noninjective maps included. The homomorphism density of HH in GG is t(H,G)=hom⁡(H,G)/|V(G)||V(H)|t(H,G)=\hom(H,G)/|V(G)|^{|V(H)|}. The edge density of GG is p(G)=2|E(G)|/|V(G)|2p(G)=2|E(G)|/|V(G)|^2. Sidorenko’s conjecture asserts that t(H,G)≥p(G)|E(H)|t(H,G)\ge p(G)^{|E(H)|} for every bipartite graph HH with at least one edge and every graph GG with at least one vertex.

Sidorenko formulated these inequalities for functionals of nonnegative kernels, in Inequalities for functionals generated by bipartite graphs and A correlation inequality for bipartite graphs. Trees, even cycles and complete bipartite graphs satisfy the conjecture (Sidorenko). Conlon, Fox and Sudakov proved it when HH has a vertex adjacent to every vertex of the opposite part. Hatami settled the case of hypercubes. Kim, Lee and Lee established it for the Cartesian product of a tree with any bipartite graph that satisfies it.

Call a face each of the 2222 triples of points of {0,…,12}\{0,\ldots,12\} listed in Table 1 of the preprint. Let HH be the incidence graph that joins each of the 1313 points to the faces containing it. The graph HH is bipartite, with 3535 vertices and 6666 edges. The preprint proves that HH violates Sidorenko’s conjecture: there is a finite simple graph GG with at least one edge such that t(H,G)<p(G)66t(H,G)<p(G)^{66}. From this theorem the preprint also derives that t(H,F)/p(F)66t(H,F)/p(F)^{66} can be made arbitrarily small over finite simple graphs FF with at least one edge, a consequence the Lean library does not contain.

The Lean library Sidorenko proves this theorem and the results of the preprint that lead to it. The Lean library covers the counterexample to Sidorenko’s conjecture only: the preprint also uses HH to disprove the forcing conjecture, and those results are not in the Lean library. The main theorem of the Lean library carries no hypothesis. Lean has checked every result of the Lean library, so the Lean library is the reference. Each result on these pages is stated as the Lean library states it and is linked to the Lean declaration behind it. Where the preprint states a result differently, the preprint’s statement is given beside the Lean library’s. The preprint is a guide only: it gives the results their order and their names.

The Lean library: Sidorenko

Sidorenko is a Lean library: 38 items, in seven groups. Each has a page written by OctoInform, listed below.

§1. Introduction 2 items
  1. §1 (setting): homomorphism and edge densities, the pattern H The incidence pattern HH and homomorphism densities. §1
  2. Theorem 1.1 [Main theorem] A bipartite graph with 66 edges violates Sidorenko’s conjecture. §1
§2. The finite complex 2 items
  1. §2 (setting): pairs, opposite faces, bits and the separation a_e The finite complex and the bit labels of its faces. §2
  2. Proposition 2.1 [Properties of the complex] Incidences, orderings and color refinement of the finite complex. §2
§3. Constructing a negative kernel correlation 10 items
  1. §3 (setting): the rank-layer kernels K_ξ and the sign model Kernels from the rank and sign of symmetric matrices. §3
  2. Lemma 3.1 [Rank-layer limit] Layer correlations approach the sign model in large even dimension. §3
  3. §3 (setting): activation laws, the kernel W_q and the coefficients C_A Activation laws, their matrix kernel and their coefficients. §3
  4. Lemma 3.2 [Coordinate expansion] A large-field limit for typed matrix kernel moments. §3
  5. §3 (setting): the base laws Corner laws with a negative moment at one corner. §3
  6. Lemma 3.3 [Support forcing] One labelling carries the active coefficient of the corner laws. §3
  7. Lemma 3.4 [Pinning by vertex and pair scores] Scores that pin the identity on 13 points and 22 faces. §3
  8. §3 (proof of Proposition 3.5): priors, thinning, dilution, crossed product A mean-one oriented kernel with moment product below one. §3
  9. Proposition 3.5 [A symmetric kernel with a strict deficit] A symmetric kernel that falls strictly below Sidorenko’s bound. §3
  10. Lemma 3.6 [Transfer to a finite simple host] A kernel counterexample yields finite graph counterexamples. §3
§4. Transverse configurations and determinant signs 8 items
  1. Lemma 4.1 [Subspaces and symmetric matrices] Counting subspaces and symmetric matrices over a finite field. §4
  2. Lemma 4.2 [Split forms and their maximal isotropic subspaces] Hyperbolic symmetric forms and the number of their Lagrangian subspaces. §4
  3. Lemma 4.3 [Concentration of restriction signs] Variance bounds for restriction signs of a random symmetric form. §4
  4. §4 (setting): the local center factor F_j and its model G_j The local center factor of a face and its model. §4
  5. Lemma 4.4 [Complementary images] When a nonsingular matrix splits into two half-rank pieces. §4
  6. Lemma 4.5 [Local transverse approximation] On transverse faces the face polynomial approximates the local average. §4
  7. Lemma 4.6 [Joint determinant signs] Pair determinant signs are asymptotically independent and uniform. §4
  8. Proposition 4.7 [Transverse limit] Kernel means approach a Boolean sign model in large dimension. §4
§5. Lagrangian counts and ordered triple orbits 4 items
  1. §5 (setting): Lagrangians, the matrix chart and the kernel J Lagrangian subspaces, their matrix chart and an intersection kernel. §5
  2. Lemma 5.1 [Lagrangian counting formulas] Counting Lagrangian and isotropic subspaces over a finite field. §5
  3. Lemma 5.2 [Chart comparison] Lagrangian kernels bound rank kernels up to constant factors. §5
  4. Proposition 5.3 [Mass of ordered triple orbits] Defect bounds for orbits and profiles of Lagrangian triples. §5
§6. Local bounds from the planted law 4 items
  1. Lemma 6.1 [Subspace cost] Counting triples of subspaces by intersections and span. §6
  2. Lemma 6.2 [Difference image] Cyclic differences of symmetric forms obey exactly one constraint. §6
  3. Proposition 6.3 [Three active incidences] Bounding the planted face factor of three Lagrangians. §6
  4. Lemma 6.4 [At most two active incidences] Bounds on face densities with at most two active corners. §6
§7. The singular contribution 8 items
  1. §7 (setting): profiles, costs and slack Profiles of thirteen Lagrangians, their cost and tail slack. §7
  2. Proposition 7.1 [Global profile cost] The profile cost bounds the probability of a point profile. §7
  3. Lemma 7.2 [Faces with at most two active incidences] A face with small gain has nonnegative slack. §7
  4. Lemma 7.3 [Coercivity] The tail quadratic part is coercive on feasible tuples. §7
  5. Lemma 7.4 [Profiles not separated by the first cost] In large even dimension, a gain reaching the cost forces rigidity. §7
  6. Lemma 7.5 [A strict span inequality] Local dimensions sum to at least twice the global dimension. §7
  7. Lemma 7.6 [Costs for the remaining profiles] Bounding configurations with pair spaces of dimension 0 or 2. §7
  8. Proposition 7.7 [Vanishing singular contribution] In large dimension the singular contribution tends to zero. §7

No item matches.