we-solve (beta)

Math-2388 · mathematics · Graph theory

Minimum Graph Homomorphism Counts at Fixed Density

Status Partially solved · unsolvedmath.comLLM status Open unverified

Statement

Definitions and mathematical statement

Shared notation.
$\mathbb N$, $\mathbb Z$, $\mathbb Q$, $\mathbb R$, and $\mathbb C$ denote the natural numbers, integers, rationals, reals, and complex numbers, respectively. All additional parameters and hypotheses are specified in the question.
Statement recorded in the supplied source.
For a fixed finite graph $F$ and an $n$-vertex graph $G$ with at least $\rho n^2/2$ edges, determine the minimum possible number of graph homomorphisms $F\to G$, where homomorphisms need not be injective and need not preserve nonedges.

Formulation references: [S1], [S2].

Short English statement

For a fixed finite graph $F$ and an $n$-vertex graph $G$ with at least $\rho n^2/2$ edges, determine the minimum possible number of graph homomorphisms $F\to G$, where homomorphisms need not be injective and need not preserve nonedges.

Sources

Catalogue entry

Statement licence: CC-BY-SA-4.0 · Source file

Contributions 1

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

OpenAI claim summary for Math-2388

Sidorenko and forcing counterexamples: For one explicit fixed bipartite graph and density, the host witnesses a homomorphism count below the formerly conjectured random-density lower bound; it does not determine the minimum for general F.

This page records partial support. Complete resolution of the catalogue question is not established by this record.

Minimum Graph Homomorphism Counts at Fixed Density

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 →