For finite simple graphs and , let be the number of edge-preserving maps from to , noninjective maps included. The homomorphism density of in is . The edge density of is . Sidorenko’s conjecture asserts that for every bipartite graph with at least one edge and every graph 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 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 triples of points of listed in Table 1 of the preprint. Let be the incidence graph that joins each of the points to the faces containing it. The graph is bipartite, with vertices and edges. The preprint proves that violates Sidorenko’s conjecture: there is a finite simple graph with at least one edge such that . From this theorem the preprint also derives that can be made arbitrarily small over finite simple graphs 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 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.
Sidorenko is a Lean library: 38 items, in seven groups. Each has a page written by OctoInform, listed below.
No item matches.