Sidorenko's property and edge retention in deep lower tails

When a random network contains very few copies of a given pattern, how many connections can its most likely configuration retain? For bipartite patterns, we prove that homogeneous minimization at every lower-tail threshold is equivalent to Sidorenko's property, for both Bernoulli graphon entropy and its sparse-limit functional. We then determine the deep-tail power of optimal edge retention. If the pattern has m edges and density-domination exponent CH = C(H,K₂), the normalized entropy saving from the zero graphon and the edge density of every normalized minimizer are θm/CH+o(1) as the relative threshold θ tends to zero, uniformly over all Bernoulli baselines. For a non-Sidorenko pattern, every optimizer therefore retains a diverging multiple of the homogeneous edge density. Applied to the counterexample reported by OpenAI, the characterization gives negative answers to two conjectures of Zhao. The variational comparisons also yield conditional edge-retention bounds for dense and suitably sparse random graphs.

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-10-08
DOI
https://doi.org/10.5281/zenodo.23231374
Primary Topic
Limits and Structures in Graph Theory
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Sidorenko's property and edge retention in deep lower tails

Zixuan He
Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
preprint

Sidorenko's property and edge retention in deep lower tails

Zixuan He
preprint en

Abstract

When a random network contains very few copies of a given pattern, how many connections can its most likely configuration retain? For bipartite patterns, we prove that homogeneous minimization at every lower-tail threshold is equivalent to Sidorenko's property, for both Bernoulli graphon entropy and its sparse-limit functional. We then determine the deep-tail power of optimal edge retention. If the pattern has m edges and density-domination exponent CH = C(H,K₂), the normalized entropy saving from the zero graphon and the edge density of every normalized minimizer are θm/CH+o(1) as the relative threshold θ tends to zero, uniformly over all Bernoulli baselines. For a non-Sidorenko pattern, every optimizer therefore retains a diverging multiple of the homogeneous edge density. Applied to the counterexample reported by OpenAI, the characterization gives negative answers to two conjectures of Zhao. The variational comparisons also yield conditional edge-retention bounds for dense and suitably sparse random graphs.

Zenodo (CERN European Organization for Nuclear Research)
University of Glasgow (GB)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Sidorenko's property and edge retention in deep lower tails — Zixuan He · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS