we-solve (beta)

Math-1059 · mathematics · Graph theory

Sidorenko's Conjecture

Status Open · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Let $H$ and $G$ be finite simple undirected graphs, with $N=|V(G)|\geq1$. A graph homomorphism from $H$ to $G$ is a function $f:V(H)\to V(G)$ for which $f(u)f(v)\in E(G)$ whenever $uv\in E(H)$. The function need not be injective; distinct nonadjacent vertices of $H$ may have the same image. Let $\operatorname{hom}(H,G)$ count these functions, and set \[ t(H,G)=\frac{\operatorname{hom}(H,G)}{N^{|V(H)|}}, \qquad p(G)=\frac{2|E(G)|}{N^2}=t(K_2,G). \] Thus $t(H,G)$ is the probability that a uniformly chosen function on the vertices preserves all edges.

A graph is bipartite if its vertices can be partitioned into two sets with no edges inside either set. Sidorenko's conjecture states that, for every bipartite $H$ and every nonempty $G$, \[ t(H,G)\geq p(G)^{|E(H)|}. \] Equivalently, multiply the right side by $N^{|V(H)|}$ to obtain the lower bound on $\operatorname{hom}(H,G)$. Isolated vertices of $H$ are allowed and contribute freely chosen images. If $H$ has no edges the right side is taken to be $1$, including when $p(G)=0$. The normalization uses $N^2$, because images of the two ends of an edge are chosen independently and in order. It is not the usual density with denominator $\binom N2$.

Short English statement

Does every bipartite pattern have at least as many edge-preserving vertex maps as its normalized edge density predicts?

Sources

Catalogue entry

Statement licence: CC-BY-4.0 · Source file

Contributions 1

Math-1059-A1 · Literature report · LLM-generated · unknown ·

OpenAI claim summary for Math-1059

Sidorenko and forcing counterexamples: The explicit finite bipartite graph H and host G satisfy t(H,G)<t(K_2,G)^e(H). Passing to the associated step graphon also refutes the graphon formulation.

The claimed counterexample lies within the question’s hypotheses and contradicts its universal conclusion.

Sidorenko's Conjecture

OpenAI's claim

Sidorenko and forcing counterexamples: A connected bipartite graph with 35 vertices and 66 edges is claimed to violate Sidorenko’s homomorphism-density lower bound in a finite host. The same pattern is also claimed not to force quasirandomness when the edge and pattern densities match their random values.

Mathematical statement of the claimed result

Mathematical claim 1.
Let $H$ be the incidence graph of the explicitly tabulated $22$ triples on $13$ points: it is connected and bipartite with $35$ vertices and $66$ edges. For $t(H,G)=\operatorname{hom}(H,G)/|V(G)|^{35}$ and $p(G)=2|E(G)|/|V(G)|^2$, a finite simple graph $G$ with $p(G)>0$ is claimed to satisfy $t(H,G)<p(G)^{66}$. Moreover, for every $c>0$ another graph $F$ has $0<t(K_2,F)$ and $t(H,F)<c\,p(F)^{66}$. The forcing corollary claims some $p\in(0,1)$ and a nonconstant symmetric measurable graphon $W:[0,1]^2\to[0,1]$ with \[t(K_2,W)=p,\qquad t(H,W)=p^{66},\qquad t(H,W)=\int_{[0,1]^{35}}\prod_{ij\in E(H)}W(x_i,x_j)\,dx.\] Thus equality at that density does not force this cyclic bipartite graph to be quasirandom.

Outline of the argument

Sidorenko and forcing counterexamples: The construction combines rank and discriminant relations for symmetric matrices with counts of symplectic intersections. Quadratic Gauss-sum estimates control joint signs, while type scores distinguish the desired vertex roles. Singular configurations are estimated separately so that the signed rank-layer correlations survive normalization and transfer to a finite host graph.

Formal verification

Family 161 describes Lean coverage for the fixed-pattern Sidorenko deficit; the forcing consequence is not selected.

Sidorenko and forcing counterexamples: The manuscript links SidorenkoCounterexample.lean.

The documented selection includes this manuscript’s main assertion; that assertion retains the restrictions stated above.

This site has not run the Lean development. These links describe OpenAI’s selected formal statements and should be read with their stated scope.

Status caveat

OpenAI reports that an internal model produced the manuscripts. Their arguments have not been independently verified as proofs by this site. Any portion outside the documented formal scope may contain mistakes, and the catalogue label reports the announced mathematical claim.

Sources

Go to contribution →