gpt 6 astra ultra attempt on Math-269

Sidorenko's Conjecture for Bipartite Graphons

Definitions and mathematical statement

A graphon is a symmetric measurable function $W:[0,1]^2\to[0,1]$. For a finite simple graph $H=(V,E)$, define its homomorphism density by \[ t(H,W)=\int_{[0,1]^{V}}\prod_{\{u,v\}\in E}W(x_u,x_v)\prod_{u\in V}{\,\mathrm{d}} x_u. \] Sidorenko's assertion is $t(H,W)\ge t(K_2,W)^{|E(H)|}$ for every bipartite $H$ and every graphon. For the constant graphon $W\equiv p$ there is equality, explaining the quasirandom comparison. Homomorphisms may identify vertices; replacing their density by the density of induced copies or injective embeddings changes the finite-object statement.

Formulation and concept references: [S1].

Short English statement

Among graph limits with a fixed edge density, does the constant graphon minimize the homomorphism density of every bipartite graph?

Research attempt

Scope and primary-source check.

This attempt was developed by GPT-6 Astra Ultra on 27 September 2026. The source [S1] treats reductions involving biregularity; it does not license replacing an arbitrary bipartite graph by a complete bipartite graph without a proof. Here all densities are homomorphism densities with independent uniform vertex variables. The work proves the desired inequality for complete bipartite graphs, trees, even cycles, and rank-one graphons, and examines the obstruction to combining those arguments. These established special mechanisms are not presented as a new general solution.

Put $p=\int_{[0,1]^2}W$ and $d(x)=\int_0^1W(x,y)\,dy$. If $p=0$, then $W=0$ almost everywhere, so every graph with an edge has density zero and the assertion holds. Edgeless graphs have density one; the convention $p^0=1$ is used. Isolated vertices can be removed from $H$ without changing either side. Hence nontrivial proofs below may assume $p>0$ and no isolated vertices.

Complete bipartite graphs: two exact Jensen steps.

Let $H=K_{s,t}$ with $s,t\ge1$. Integrate first over its $t$ vertices on one side and define \[ A(x_1,\ldots,x_s)=\int_0^1\prod_{i=1}^sW(x_i,y)\,dy. \] Fubini's theorem and two uses of Jensen's inequality give \[ \begin{split} t(K_{s,t},W)&=\int A(x_1,\ldots,x_s)^t\,dx_1\cdots dx_s\\ &\ge\left(\int A\right)^t =\left(\int_0^1d(y)^s\,dy\right)^t \ge p^{st}. \end{split} \tag{1} \] All functions are bounded and nonnegative, so the changes of order and powers are justified without integrability qualifications. The argument uses the identical neighborhoods of vertices on one side. General bipartite graphs do not have that factorization.

For $C_4=K_{2,2}$, keeping the intermediate term yields a stability calculation. If $v=\int(d-p)^2$, then $\int d^2=p^2+v$ and \[ t(C_4,W)-p^4\ge2p^2v+v^2. \tag{2} \] Small four-cycle excess thus controls degree variation. Conversely, small degree variation alone does not bound the four-cycle excess. For example take two equal blocks and $W=a$ across the blocks and zero within them, with $0<a\le1$. Every degree is $a/2$, but \[ p=a/2,\qquad t(C_4,W)=a^4/8=2p^4. \] This is a direct test against the inference that regularity alone makes a graphon constant.

Trees: a stationary Markov construction.

Let $T$ be a tree with $v\ge2$ vertices. Initially assume $W\ge\epsilon>0$; the general case will follow by approximation. Define the probability density $\pi(x)=d(x)/p$ and transition density \[ P(x,y)=\frac{W(x,y)}{d(x)}. \] Symmetry of $W$ gives stationarity: $\int\pi(x)P(x,y)\,dx=\pi(y)$. Root the tree anywhere, draw the root from $\pi$, and draw each child from the transition law of its parent, independently given the parents. The resulting density on all vertex variables is \[ f((x_u)_{u\in V(T)})= \frac1p\prod_{uv\in E(T)}W(x_u,x_v) \prod_{u\in V(T)}d(x_u)^{1-\deg_T(u)}.\tag{3} \] This follows by counting denominators at each vertex; the root has one extra factor $d/p$ from its initial density. Every marginal is $\pi$.

Rearranging $3$, and applying Jensen to the exponential, gives \[ \begin{split} t(T,W) &=p\,\mathbb E_f\prod_ud(X_u)^{\deg_T(u)-1}\\ &\ge p\exp\left(\sum_u(\deg_T(u)-1) \int\pi(x)\log d(x)\,dx\right). \end{split} \tag{4} \] The sum of coefficients is $2(v-1)-v=v-2$. Convexity of $z\log z$ implies \[ \int\pi\log d=\frac1p\int d\log d\ge\log p. \] Thus $t(T,W)\ge p^{v-1}$, as required. The use of natural logarithms inside this entropy calculation has no effect on the power-law conclusion.

For a general graphon, set $W_\epsilon=(1-\epsilon)W+\epsilon$. It is bounded below by $\epsilon$ and converges uniformly to $W$. For a graph with $e$ edges, telescoping the product of its edge factors shows $|t(H,W_\epsilon)-t(H,W)|\le e\|W_\epsilon-W\|_\infty$. Also $p_\epsilon\to p$. Letting $\epsilon\downarrow0$ proves the tree inequality without taking logarithms of zero. Disjoint components factor under the defining integral, so the result extends to forests.

This proof specifies the joint distribution rather than assuming that edge variables are independent. Tree structure is used to construct it. Trying the same root-and-child procedure around a cycle creates a compatibility constraint not present in $3$.

Even cycles: the operator argument.

Let $T_W$ be the self-adjoint integral operator on real $L^2[0,1]$, $(T_Wf)(x)=\int W(x,y)f(y)\,dy$. It is Hilbert--Schmidt because $W\in L^2$, and hence compact. For $k\ge2$, its eigenvalues $(\lambda_j)$ satisfy \[ t(C_{2k},W)=\operatorname{tr}(T_W^{2k}) =\sum_j\lambda_j^{2k}. \tag{5} \] One can obtain the first equality by writing the kernel of $T_W^k$ and taking its squared Hilbert--Schmidt norm; Fubini joins two length-$k$ paths into the $2k$-cycle. Absolute convergence follows from $\sum_j\lambda_j^2<\infty$ and boundedness of the eigenvalues. The constant function $1$ has $L^2$ norm one and $\langle1,T_W1\rangle=p$, so $\|T_W\|\ge p$. Consequently \[ t(C_{2k},W)\ge p^{2k}. \tag{6} \] Even powers are essential: the operator need not be positive semidefinite merely because its kernel is pointwise nonnegative.

There is a useful equality check for $C_4$. If $t(C_4,W)=p^4$ with $p>0$, equality in $\sum\lambda_j^4\ge\|T_W\|^4\ge p^4$ forces a single nonzero eigenvalue and equality in the Rayleigh bound at $1$. That eigenvalue is $p$ and its eigenspace contains $1$, so $T_Wf=p\langle f,1\rangle1$. Equality of Hilbert--Schmidt kernels then gives $W=p$ almost everywhere. No injective-copy interpretation is used in this conclusion.

A broad test family: rank-one kernels.

If $W(x,y)=f(x)f(y)$ with $0\le f\le1$, then \[ t(H,W)=\prod_{u\in V(H)}\int f^{\deg_H(u)}. \] Jensen gives $\int f^d\ge(\int f)^d$ for every integer $d\ge1$, so this family satisfies $t(H,W)\ge p^{|E(H)|}$ for every graph $H$, even nonbipartite ones. It follows that restricting a search for a counterexample to rank-one graphons is too narrow. On the other hand, a balanced complete bipartite graphon has $p=1/2$ and triangle density zero. The bipartite hypothesis in the full conjecture is therefore essential; the rank-one calculation does not extend the conjecture to arbitrary graphs.

The failed gluing step.

Suppose two graphs are joined at a distinguished vertex. Integrating all other variables produces rooted densities $a(x),b(x)$, and the joined density is $\int a(x)b(x)\,dx$. Bounds on $\int a$ and $\int b$ alone do not give a bound by their product: two nonnegative functions supported on disjoint half intervals already violate that inference. This functional example is not claimed to realize arbitrary rooted graph densities for a common $W$. It identifies the missing correlation lemma that a gluing proof would need to establish from that structure. Replacing rooted profiles by their averages without such a lemma is not a valid extension of the tree proof.

Verification and remaining target.

The accompanying exact rational checks evaluate small step graphons, including zero degrees and the two-block example, and compare the special graph densities with their proved bounds. They also verify the factorization for rank-one kernels. All integrals in these checks are finite weighted sums. They do not reduce the general conjecture to any fixed partition size or bounded set of graphs.

Final status.

UNRESOLVED. Complete proofs have been given for the specified families, and the equality case for the four-cycle has been checked. The first general gap is a lower bound on the correlations among rooted profiles produced by a bipartite graph with overlapping, unequal neighborhoods. Possible next steps are a justified gluing inequality, a distributional replacement for the tree Markov construction, or a finite-step counterexample search retaining several distinct profile types. No result here covers every bipartite $H$ and every graphon.

Sources

• S1 D. Conlon, J. Lee, A. Sidorenko, 'Biregularity in Sidorenko's Conjecture', arXiv:2108.06599 $2021$. https://arxiv.org/pdf/2108.06599. Formulation source.