Forcing Quasirandomness via Rooted F-Densities

Heng Li; Xizhi Liu

Forcing Quasirandomness via Rooted F-Densities

T0 review · 0 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that a graphon whose edge-rooted densities for every edge of a fixed graph are constant must either have zero density or be constant itself, and derives the consequence that every clique is 2-forcing.

desk verdict A clean, correct proof of all-edge rooted forcing, with a solid resolution of the Reiher-Schacht clique question and a unified entropy+Hoeffding method that extends well beyond the graphon case. read the letter →

arxiv 2608.08679 v1 pith:OTWDDJGJ submitted 2026-08-09 math.CO

Heng Li , Xizhi Liu This is my paper · ORCID

classification math.CO MSC 05C8005C2005C3505C6005C6560G09

keywords graphonsrootedsubgraphdensitiesquasirandomnessANOVAdecompositionentropymethodhypergraphonstournamentonscliqueforcing

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves a strong rigidity statement for dense graph limits. If, for every edge e of some fixed graph F, the density of F in a graphon W rooted at e is constant almost everywhere, then either the total F-density is zero or W itself is constant, with constant value p = t(F,W)^{1/m}. The proof's two-step mechanism—an entropy (relative-entropy) argument converts constant rooted densities into an additive identity for log W over the edges of F, and an orthogonal ANOVA variance decomposition shows that only a constant function can satisfy it—extends to hyperkernels, dissociated hypergraphons, directed kernels, and tournamentons, including explicit stability estimates when W is bounded away from zero. As a corollary, every clique is 2-forcing, which determines the exact minimum number of vertex sets needed in the forcing question from the edge-rooted triangle literature.

What carries the argument

The load-bearing object is the edge-rooted density r^W_e, obtained from the homomorphism density t(F,W) by fixing the two vertex variables of an edge and integrating out all other vertices. The proof has two reductions. First, the probability measure on vertex assignments proportional to the product of edge weights has uniform edge marginals exactly when rooted densities are constant; relative entropy and the convexity of the exponential then force the sum of log W over the edges of F to be constant almost everywhere. Second, the orthogonal ANOVA decomposition writes a symmetric L2 function as a sum of components depending on exactly 0, 1, or 2 coordinates; computing the variance of that edge sum shows that a constant sum is possible only when all nonconstant components vanish. The directed case uses the nonsymmetric version of the same decomposition, whose one-coordinate terms leave the gauge freedom $\varphi$(x)-$\varphi$(y), and the hypergraph case applies the decomposition to local coordinates attached to proper subsets of an edge.

What would settle it

Run a finite search over two-part step graphons for a fixed graph F: if any nonconstant symmetric 2x2 matrix W with entries in [0,1] and t(F,W)>0 has all edge-rooted densities exactly equal to the same constant, Theorem 1.1 is false. The rooted densities are polynomials in the matrix entries, so the search is a finite system of polynomial equations. A directed falsifier would be a non-Eulerian oriented graph D and a nonconstant directed kernel with t(D,W)>0 and all arc-rooted densities constant, which the paper's Theorem 1.3 rules out.

Watch

Extended reading notes

Core claim

The central discovery is a dichotomy for edge-rooted densities: for any finite graph F with m>0 edges and any graphon W, if every edge-rooted density r^W_e is constant almost everywhere, then either t(F,W)=0 or W=p almost everywhere with p=t(F,W)^{1/m}. The paper proves the same dichotomy in three further settings: symmetric k-uniform hyperkernels and dissociated hypergraphons (where the rooted variables include all coordinates attached to nonempty proper subsets of an edge), one-function directed kernels (where non-Eulerian oriented templates force W constant and Eulerian templates allow the gauge family W(x,y)=p exp($\varphi$(x)-$\varphi$(y))), and tournamentons, where the antisymmetry W(x,y)+W(y,x)=1 collapses the gauge family to the uniform kernel W=1/2. Quantitative versions replace exact constancy by a bound on the total L1 marginal error and give explicit L1 and L2 bounds on W-p; in the exact positive-density case the equations themselves imply the lower bound W>=t(F,W), so no separate boundedness assumption is needed.

Load-bearing premise

The load-bearing assumption is that a tiny error over all pairs of vertex subsets in a finite graph implies a tiny error in the edge-rooted density of the limiting graphon; if that continuity failed, the combinatorial 2-forcing condition would not imply the pointwise constancy that the main theorem solves.

Editorial extensions

If this is right

Every clique K_k is 2-forcing; for k>=4 the minimum number of vertex subsets in the forcing condition is exactly 2, improving the earlier upper bound ceil((k+1)/2).
At positive density, constant rooted densities imply the pointwise lower bound W >= t(F,W), so the classification needs no extra hypotheses beyond the rooted equations.
For non-Eulerian oriented graphs, constant arc-rooted densities force the directed kernel to be constant; for Eulerian templates the only solutions are the gauge kernels p exp(phi(x)-phi(y)), and the tournamenton identity forces p=1/2 and phi constant.
In the hypergraph models, rooting only vertex variables is provably insufficient; rigidity holds only when all coordinates attached to proper subsets of the edge are fixed.
The stability estimates give an explicit quantitative certificate: a small total marginal error Delta_F(W) forces W to be close in L1 and L2 to the constant graphon p.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because the argument uses only convexity and orthogonality, the same dichotomy should hold for weighted graphons and for kernels taking values in any bounded interval; a direct check on weighted step graphons would be a cheap extension.
The Eulerian gauge family suggests that in a two-function digraphon model, where opposite arcs are governed by independent kernels, constant arc-rooted densities may admit a wider family of solutions; the one-function model used here is the symmetric case, so the classification is not automatically the general digraphon classification.
The hypergraph remark implies a practical warning: any quasirandomness test for k-uniform hypergraphs that roots only vertex coordinates can be fooled by additive pair-coordinate perturbations, so tests should use full-edge-rooted densities.
The total marginal error Delta is a graphon functional that can be estimated from a single large graph by sampling; the stability estimate then yields a computable bound on the distance to p-quasirandomness, which is a testable algorithmic consequence.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper is a strong, self-contained contribution to the graph-limits side of quasirandomness. The main result — if every edge-rooted F-density in a graphon is constant, then either the F-density is zero or the graphon is constant — is proved by a genuinely clean two-step method: constant rooted densities make the Gibbs edge marginals uniform, and equality in Jensen plus strict convexity gives a constant sum of log-weights; the Hoeffding decomposition then rules out nonconstant symmetric kernels. The same argument answers the Reiher-Schacht question (every clique is 2-forcing) and extends, with explicit stability estimates, to uniform hyperkernels, the dissociated Aldous-Hoover hypergraphon model, directed kernels, and tournamentons. The directed classification is interesting in its own right: the only nonconstant positive-density solutions come from Eulerian templates and have the form p exp(phi(x)-phi(y)).

I checked the main line of proof and it holds up. The entropy step and the variance computation are correct. The stability estimates are explicit and the constants are honest. The zero-density alternative is handled carefully. The citations look appropriate, and related work on hereditary quasirandomness, forcing pairs, and tournament limits is discussed rather than ignored.

Soft spots, in proportion: the most intricate part is Lemma 4.4 for full hypergraphons. I believe the orthogonality/cancellation argument is correct, but it is the kind of thing a referee should verify slowly. The transfer in Corollary 3.1 from the finite two-set condition to the limiting rooted identity uses the weighted counting lemma as a black box. This is standard (Lovasz 10.23, or a telescoping proof), and the paper sketches the reduction, so I do not regard it as a gap. The directed kernel model is explicitly one-function, so the Eulerian family may not survive in a more general digraphon framework; the paper is upfront about that. The stability constants are not optimized; the paper says so.

Who it is for: anyone working on quasirandomness, graph limits, or forcing. It also gives a usable template for other rooted-density problems. I would bring it to a reading group and likely cite it.

Recommendation: send it to a serious referee. The referee should focus on Section 4 and the quantitative tournamenton estimate. I expect acceptance after that pass.

Referee Report

0 major / 4 minor

Summary. The paper studies rooted subgraph-density rigidity for graphons. Theorem 1.1 states that if every edge-rooted F-density of a graphon W is constant, then either t(F,W)=0 or W is constant equal to t(F,W)^{1/m}. The proof combines two reductions: a relative-entropy argument showing that the sum of log W over the edges of F is almost surely constant, and a Hoeffding/ANOVA variance computation showing that such a constant sum forces log W to be constant. Section 3 derives the clique-forcing corollary (every clique is 2-forcing), answering a question of Reiher and Schacht, and gives a quantitative stability estimate. Section 4 extends the result to symmetric uniform hyperkernels and to dissociated Aldous-Hoover hypergraphons, with stability estimates. Section 5 classifies the directed analogue: non-Eulerian templates force W to be constant, while Eulerian templates allow the family W(x,y)=p exp(phi(x)-phi(y)); imposing the tournamenton identity collapses this family to W=1/2. Explicit stability estimates are given for non-Eulerian directed templates and for regular tournaments.

Significance. If correct, the main theorem is a substantial and elegant generalization of the edge-rooted triangle theorem of Reiher and Schacht. The proof is fully written, self-contained apart from standard tools, and yields explicit quantitative bounds. The clique-forcing answer settles a question in the literature. The method, relative-entropy equality combined with Hoeffding variance, is likely to be reusable in related rigidity problems. The hypergraphon and directed results are model-dependent, but the paper is transparent about these limitations. There are no fitted parameters and the predictions are concrete. Overall this is a strong contribution to the quasirandomness and graph-limits literature.

minor comments (4)

[Corollary 5.5] In Eq. (5.8), the factor '2emM' appears to be a typo for '2e^{mM}'; every other use of Lemma 2.3 in Theorems 3.2, 4.3, 4.5, and 5.2 has the exponential e^{mM}. Please correct this.
[Section 2] The phrase 'ANOV A decomposition' should read 'ANOVA decomposition'; the spacing is a typo.
[Corollary 3.1] The transfer from the finite two-set condition to the pointwise identity r_e^W = p^m rests on the weighted counting lemma [21, Theorem 10.23]. The step is standard and the paper sketches it, but a one-sentence reminder of why the telescoping proof applies with the two vertex weights 1_A and 1_B bounded by 1 would make this load-bearing passage more self-contained.
[Sections 4 and 5] The hypergraphon classification is stated for the dissociated Aldous-Hoover representation, and the directed classification for the one-function kernel model; the paper is explicit about this, but it may be worth repeating in the conclusion that these classifications do not automatically transfer to general digraphon or hypergraphon frameworks with a global mixing coordinate.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central graphon theorem is proved from entropy, Jensen, and Hoeffding decompositions, with the only external input being the standard weighted counting lemma used in the clique-forcing corollary.

full rationale

The paper's derivation chain is self-contained. Theorem 1.1 is proved by turning constant rooted densities into a constant logarithmic edge-sum via the Gibbs marginal and entropy calculation (Proposition 2.1), then applying the Hoeffding/ANOVA variance computation (Proposition 2.2). Neither step presupposes the conclusion: the entropy and Jensen inequalities are standard external tools, and the Hoeffding decomposition is stated and proved in the paper. There are no fitted parameters, no prediction renamed from an input, and no self-citations by the present authors. The only load-bearing external citation is the weighted counting lemma ([21, Theorem 10.23]) used in Corollary 3.1 to pass from finite two-set clique counts to the limiting rooted identity; this is a standard, independently established theorem, and the paper also sketches the telescoping argument that makes it applicable. The recovery of the Reiher--Schacht triangle theorem is presented as a special case, not as a premise. The hypergraphon, directed-kernel, and tournamenton results are explicitly scoped to the stated coordinate models, and their proofs use the same entropy-plus-Hoeffding reductions. The stability estimates are genuine quantitative bounds in terms of explicitly defined rooted-density error terms, with no hidden reuse of the target rigidity as an assumption. No circular step could be identified.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claims rest on standard mathematical tools (Jensen, entropy, Hoeffding decomposition, graphon continuity) plus two explicitly stated modeling choices: the dissociated Aldous-Hoover representation for hypergraphons and the one-function directed kernel model. No free parameters are fitted and no new postulated entities are introduced.

assumptions (6)

standard math Jensen's inequality and strict convexity of exp
Used in Proposition 2.1 and analogues to turn equality in Jensen into the additive identity (2.3).
standard math Relative entropy nonnegativity and its equality case
The Gibbs entropy identity in Proposition 2.1 bounds the Jensen deficit; used throughout the paper.
standard math Hoeffding/ANOVA decomposition and orthogonality of components
Propositions 2.2, 4.1, 4.2, 4.4, and 5.1 rely on this decomposition to establish variance lower bounds.
standard math Graphon compactness and the weighted counting lemma (Lovász, Theorem 10.23)
Corollary 3.1 uses these cited results to transfer finite setting conditions to the limit graphon identity.
domain assumption Existence of the dissociated Aldous-Hoover representation for dense hypergraph limits
Theorem 1.2(ii) and Section 4.2 are stated in this model; the paper is explicit that this is the convention used.
domain assumption One-function directed kernel model for directed graphs
Section 5.1 states this is not the most general digraphon model; Theorem 1.3 applies only in this model.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Forcing Quasirandomness via Rooted F-Densities." pith.science (2026). https://pith.science/paper/OTWDDJGJ

@misc{pith2026260808679,
  author       = {Pith},
  title        = {Pith review of: Forcing Quasirandomness via Rooted F-Densities},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OTWDDJGJ}},
  note         = {Machine review of arXiv:2608.08679}
}

abstract

Let $F$ be a finite graph with at least one edge, and let $W$ be a graphon. We show that if the density of $F$ rooted at each edge is almost everywhere constant, then either $t(F,W)=0$ or $W$ is constant. For edge-transitive $F$, one rooted equation suffices. This recovers the edge-rooted triangle theorem of Reiher and Schacht. In their terminology, our result also shows that every clique is $2$-forcing, answering a question they posed. We give an explicit stability estimate when $W$ is bounded away from zero. Our proof has two steps: an entropy argument turns constant rooted densities into an additive identity for $\log W$, and a Hoeffding decomposition determines all solutions of that identity. The same method gives exact classifications and quantitative stability estimates for symmetric uniform hyperkernels, dissociated Aldous--Hoover hypergraphons, directed kernels, and tournamentons.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 27 canonical work pages

[1]

D. J. Aldous. Representations for partially exchangeable arrays of random variables.J. Multivariate Anal., 11(4):581–598, 1981

work page 1981
[2]

T. Austin. On exchangeable random variables and the statistics of large graphs and hypergraphs. Probab. Surv., 5:80–145, 2008

work page 2008
[3]

Borgs, J

C. Borgs, J. T. Chayes, L. Lov´ asz, V. T. S´ os, and K. Vesztergombi. Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing.Adv. Math., 219(6):1801–1851, 2008

work page 2008
[4]

Borgs, J

C. Borgs, J. T. Chayes, L. Lov´ asz, V. T. S´ os, and K. Vesztergombi. Convergent sequences of dense graphs. II. Multiway cuts and statistical physics.Ann. of Math. (2), 176(1):151–219, 2012

work page 2012
[5]

Buci´ c, E

M. Buci´ c, E. Long, A. Shapira, and B. Sudakov. Tournament quasirandomness from local counting. Combinatorica, 41(2):175–208, 2021

work page 2021
[6]

Transitivity in Inhomogeneous Random Tournaments

S. Chatterjee and B. B. Bhattacharya. Transitivity in inhomogeneous random tournaments. arXiv:2606.02340, 2026

work page Pith review arXiv 2026
[7]

F. R. K. Chung and R. L. Graham. Quasi-random tournaments.J. Graph Theory, 15(2):173–198, 1991

work page 1991
[8]

F. R. K. Chung, R. L. Graham, and R. M. Wilson. Quasi-random graphs.Combinatorica, 9(4):345– 362, 1989

work page 1989

Show all 29 references

[9]

Conlon, J

D. Conlon, J. Fox, and B. Sudakov. Hereditary quasirandomness without regularity.Math. Proc. Cambridge Philos. Soc., 164(3):385–399, 2018

2018
[10]

Diaconis and S

P. Diaconis and S. Janson. Graph limits and exchangeable random graphs.Rend. Mat. Appl. (7), 28(1):33–61, 2008

2008
[11]

Elek and B

G. Elek and B. Szegedy. A measure-theoretic approach to the theory of dense hypergraphs.Adv. Math., 231(3-4):1731–1772, 2012. 20

2012
[12]

J. Fox, Z. Himwich, N. Mani, and Y. Zhou. A note on directed analogues of the Sidorenko and forcing conjectures.Electron. J. Combin., 32(3):Paper No. P3.38, 14, 2025

2025
[13]

Grzesik, D

A. Grzesik, D. Kr´ al’, and O. Pikhurko. Forcing generalised quasirandom graphs efficiently.Combin. Probab. Comput., 33(1):16–31, 2024

2024
[14]

Hancock, A

R. Hancock, A. Kabela, D. Kr´ al’, T. Martins, R. Parente, F. Skerman, and J. Volec. No additional tournaments are quasirandom-forcing.European J. Combin., 108:Paper No. 103632, 10, 2023

2023
[15]

Hoeffding

W. Hoeffding. A class of statistics with asymptotically normal distribution.Ann. Math. Statistics, 19(3):293–325, 1948

1948
[16]

Hubai, D

T. Hubai, D. Kr´ al’, O. Parczyk, and Y. Person. More non-bipartite forcing pairs.Acta Math. Univ. Comenianae, 88(3):819–825, 2019

2019
[17]

S. Janson. Quasi-random graphs and graph limits.European J. Combin., 32(7):1054–1083, 2011

2011
[18]

Kallenberg.Probabilistic Symmetries and Invariance Principles

O. Kallenberg.Probabilistic Symmetries and Invariance Principles. Probability and its Applications (New York). Springer, New York, 2005

2005
[19]

Kr´ al’, M

D. Kr´ al’, M. Krnc, F. Kuˇ cer´ ak, B. Lidick´ y, and J. Volec. Sidorenko property and forcing in regular tournaments. arXiv:2602.12551, 2026

2026 arXiv
[20]

Lov´ asz

L. Lov´ asz. Graph homomorphisms: open problems. Manuscript, June 2008

2008
[21]

Lov´ asz.Large Networks and Graph Limits, volume 60 ofAmerican Mathematical Society Colloquium Publications

L. Lov´ asz.Large Networks and Graph Limits, volume 60 ofAmerican Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2012

2012
[22]

Lov´ asz and V

L. Lov´ asz and V. T. S´ os. Generalized quasirandom graphs.J. Combin. Theory Ser. B, 98(1):146–163, 2008

2008
[23]

Lov´ asz and B

L. Lov´ asz and B. Szegedy. Limits of dense graph sequences.J. Combin. Theory Ser. B, 96(6):933–957, 2006

2006
[24]

Lov´ asz and B

L. Lov´ asz and B. Szegedy. Finitely forcible graphons.J. Combin. Theory Ser. B, 101(5):269–301, 2011

2011
[25]

J. A. Noel, A. Ranganathan, and L. M. Simbaqueba. Forcing quasirandomness in a regular tournament. Innov. Graph Theory, 3:127–169, 2026

2026
[26]

Reiher and M

C. Reiher and M. Schacht. Forcing quasirandomness with triangles.Forum Math. Sigma, 7:Paper No. e9, 19, 2019

2019
[27]

Simonovits and V

M. Simonovits and V. T. S´ os. Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs.Combinatorica, 17(4):577–596, 1997

1997
[28]

Th¨ ornblad

E. Th¨ ornblad. Decomposition of tournament limits.European J. Combin., 67:96–125, 2018

2018
[29]

Y. Zhao. Hypergraph limits: a regularity approach.Random Structures Algorithms, 47(2):205–226, 2015. 21

2015

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

D. J. Aldous. Representations for partially exchangeable arrays of random variables.J. Multivariate Anal., 11(4):581–598, 1981

work page 1981

[2] [2]

T. Austin. On exchangeable random variables and the statistics of large graphs and hypergraphs. Probab. Surv., 5:80–145, 2008

work page 2008

[3] [3]

Borgs, J

C. Borgs, J. T. Chayes, L. Lov´ asz, V. T. S´ os, and K. Vesztergombi. Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing.Adv. Math., 219(6):1801–1851, 2008

work page 2008

[4] [4]

Borgs, J

C. Borgs, J. T. Chayes, L. Lov´ asz, V. T. S´ os, and K. Vesztergombi. Convergent sequences of dense graphs. II. Multiway cuts and statistical physics.Ann. of Math. (2), 176(1):151–219, 2012

work page 2012

[5] [5]

Buci´ c, E

M. Buci´ c, E. Long, A. Shapira, and B. Sudakov. Tournament quasirandomness from local counting. Combinatorica, 41(2):175–208, 2021

work page 2021

[6] [6]

Transitivity in Inhomogeneous Random Tournaments

S. Chatterjee and B. B. Bhattacharya. Transitivity in inhomogeneous random tournaments. arXiv:2606.02340, 2026

work page Pith review arXiv 2026

[7] [7]

F. R. K. Chung and R. L. Graham. Quasi-random tournaments.J. Graph Theory, 15(2):173–198, 1991

work page 1991

[8] [8]

F. R. K. Chung, R. L. Graham, and R. M. Wilson. Quasi-random graphs.Combinatorica, 9(4):345– 362, 1989

work page 1989