REVIEW 2 major objections 4 minor 2 cited by
Emergence in graphs with near-extreme constraints
T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read For near-extreme edge and triangle densities, the entropy-optimal large graph is unique and multipodal, yielding infinitely many distinct phases and phase transitions.
desk verdict Radin-Sadun prove the conjectured infinite phase structure near the boundary of the edge-triangle model, but the claimed analyticity of the phases rests on an unproven tangent-space non-degeneracy condition. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central mechanism is the worth functional $W(C)$ of a column $C$ of a graphon, together with the associated Euler-Lagrange equation. Worth adds the Shannon entropy of a column to its edge and triangle contributions weighted by Lagrange multipliers $(\alpha,\beta)$; Theorem 11 says every column of an entropy-maximizing graphon must maximize $W$. This reduces an infinite-dimensional variational problem to classifying the finitely many worth-maximizing column shapes, after which the paper upgrades approximate block structure to exact multipodality by bounding variations in each rectangle, then analyzes the finite-dimensional space of podes to pin down symmetry and analyticity. A two-pass argument, using the fact that singular entropy-maximizers occur only on a measure-zero set of $t$ for each $e$, extends results from almost every $t$ to all $t$ in the region.
What would settle it
Compute the Jacobian determinant of the Euler–Lagrange system for the $(n,2)$-symmetric multipodal optimizer on each scallop phase; if it vanishes anywhere in the claimed region, the analytic parameterization breaks down and the phase is not a single analytic open set.
Extended reading notes
Core claim
The central discovery is that, for three near-boundary families of constraints, the entropy-optimal reduced graphon is unique and multipodal, and its parameters are analytic in $(e,t)$. For fixed $e<1/2$ and $t$ sufficiently small, the optimizer is symmetric bipodal, with two equal blocks whose diagonal values are exponentially small and whose off-diagonal value is near $2e$; the Boltzmann entropy gain $\Delta B$ scales as $t\ln(1/t)$. For each $n\ge 1$ and $e\in(n/(n+1),(n+1)/(n+2))$, with $t$ just above the minimal triangle density $t_0(e)$, the optimizer is $(n+2)$-podal with $(n,2)$ symmetry, and $\Delta B$ scales as $\sqrt{t-t_0}$. For each $e\in(0,1)$ and $t$ just below $e^{3/2}$, the optimizer is bipodal and the entropy deficit scales as $(e^{3/2}-t)\ln(1/(e^{3/2}-t))$. The distinct symmetries give distinct ranks, and rank-based order parameters show that these phases are analytically disconnected; the paper also proves the nearby points are invisible to exponential random graph models.
Load-bearing premise
The proof that the optimal graphon parameters depend analytically on $(e,t)$ assumes, without proof, that the tangent space to the set of optimal graphons never degenerates; if it did, the implicit function theorem would fail and the "phase" could branch into several analytic sheets.
Editorial extensions
If this is right
- All but an exponentially small fraction of large graphs with $e<1/2$ and tiny $t$ share one symmetric bipodal structure: two equal communities with exponentially small internal densities and cross-density near $2e$.
- Above the $n$-th scallop, typical graphs are $(n+2)$-podal with $n$ identical podes and two small podes; the entropy gain over the minimum-triangle graphon grows as $\sqrt{t-t_0}$, with all block entries exponentially close to $0$ or $1$ except one pair.
- Just below the upper boundary $t=e^{3/2}$, typical large graphs split into a dense block of size $\sqrt{e}$ and a sparse block, with entropy deficit $(e^{3/2}-t)\ln(1/(e^{3/2}-t))$.
- Each scallop phase has a different rank and symmetry, so there are infinitely many phases separated by genuine phase transitions, and the order parameters distinguishing them are polynomials in subgraph densities.
- Points just above the lower scallops and just below the upper boundary are ERGM-invisible: no choice of edge and triangle potentials in an exponential random graph model reproduces their constrained graph distribution.
Reading between the lines
- The column-worth technique is not specific to triangles: the same two-pass strategy should apply to other constrained subgraph densities whose functional derivatives are bilinear, though the classification of worth-maximizing columns would need to be reworked for each target subgraph.
- The rank-based order parameters built from traces of the graphon cube give explicit polynomial statistics in subgraph densities, so the scallop phase boundaries could in principle be detected in finite simulated graphs, a step the paper does not take.
- The paper leaves open whether the bipodal phase near the upper boundary connects to the bipodal phase already found just above the Erdős–Rényi curve; if it does, the phase diagram would contain a transition curve in the interior of the triangle, not just on the boundary.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies entropy-optimal graphons that maximize Shannon entropy subject to fixed edge and triangle densities (e,t) near the boundary of the feasible region. The authors introduce a 'worth' functional for columns of a graphon and use it, together with Lagrange multiplier theory, to prove that optimizers near the lower boundary are unique and symmetric bipodal for e<1/2 (Theorem 14), unique and (n,2)-symmetric (n+2)-podal near the n-th scallop for e in (n/(n+1),(n+1)/(n+2)) (Theorem 17), and unique and bipodal just below the upper boundary (Theorem 20). They also prove that these phases are distinct and cannot be analytically continued into one another (Theorem 19), and that most near-boundary points are invisible to ERGMs (Theorems 22 and 23). The proofs rely on the 'worth' functional, variational equations, and a two-pass argument that uses a theorem to exclude singular entropy maximizers.
Significance. If the proofs are completed, the results constitute a significant advance: they establish the existence of infinitely many phases in the edge-triangle model and give explicit multipodal structure and analytic parameter dependence for entropy-optimal graphons. The 'worth' functional is a genuinely new tool that may be useful in other constrained graphon optimization problems, and the paper gives explicit asymptotic scalings for entropy deficits and Lagrange multipliers. A major caveat is that the analyticity of the optimal graphon parameters, which is essential to the phase concept, rests on an unproven non-degeneracy condition, so the phase and phase-transition claims are conditional until that gap is closed.
major comments (2)
- [Section 4.5 and end of Section 5] The paper's phase concept (Section 1.3.4) requires the optimal reduced graphon to be a real-analytic function of (e,t), and the main theorems assert analytic parameter variation. In Section 4.5 this is justified by an implicit function theorem 'as long as the tangent space does not degenerate', but the non-degeneracy is never checked. This is a load-bearing gap: near the scallop boundary the constraint map has a critical point (dt/dc = 0 at c0, Eq. (58)), so the relevant Jacobian is singular at the boundary, and the paper does not demonstrate that it becomes nondegenerate inside the claimed phase. If the tangent space degenerates, the parameterization could branch or fail to be analytic on part of the phase, and the distinctness argument in Theorem 19 would not follow as stated. The same issue affects the analyticity claim at the end of the proof of Theorem 20. The authors should prove the tangent-space non-degeneracy or supply a different argument that the finitely many parameters are real-analytic functions of (e,t) on the open sets in question.
- [Sections 3.5 and 4.4] The exact-multipodality proofs rely on inequalities that are summarized as 'a little algebra' and are not displayed. Concretely, Eq. (41) and the chain ending at Eq. (46) in Section 3.5, and the analogous inequalities (75)-(76) in Section 4.4, are asserted without derivation. These inequalities are what make the contraction argument work (variations bounded by a small multiple of themselves, forcing exact constancy on each rectangle). The reader cannot verify the contraction without seeing the precise bounds, including the treatment of error terms, the replacement of coefficients such as 4(1-c) by 3, and the control of the denominators -H'' on the relevant intervals. The derivations should be written out in full.
minor comments (4)
- [Section 2, Lemma 12] The proof states that 'S(gs) is an increasing function of s (thanks to the concavity of H(u))', but concavity of H alone does not imply monotonicity along the linear path g_s. What is needed is the inequality S(g_s) > S(g0), which follows from concavity combined with Jensen's inequality: S(e) = H(e) ≥ S(g0), with strict inequality unless g0 is constant, which is excluded for t < e^3. The authors should state this argument explicitly and avoid the stronger monotonicity claim.
- [Section 4.6, Theorem 19] The proof assumes that the optimal graphons in the A(2,0) phase have rank 2 and those in the C(n,2) phases have rank n+2. These rank assertions are not established in the text. It would be useful to add a short linear-algebra verification: for the block matrix with (n,2) symmetry, the rank is n+2 as long as the off-diagonal entry p and the diagonal entries satisfy the non-degeneracy conditions that hold in the phase.
- [Various sections] The text contains numerous typos and small errors, including 'Razbarov' in Remark 8, 'encylopedic' in Section 1.3.1, 'a+n + 2' in Section 4.3, 'In+1 × In2' in Section 4.2, and inconsistent notation W_{e,t} versus W_{e,t}; these should be corrected in a revision.
- [Section 3.4] The analysis of the stationary points of the approximate worth maximization (Eq. (35)) is quite compressed; in particular, the argument that the stationary point with a and b both tiny cannot be a maximum of W should be spelled out, since this exclusion is needed to conclude that all columns are close to one of two worth-maximizing forms.
Circularity Check
No circularity: the near-boundary phases are derived from prior boundary-uniqueness results plus new variational arguments; the unproven tangent-space condition is a proof gap, not a circular reduction.
full rationale
The paper's central claims are not circular. Theorems 14, 17 and 20 each start from the previously established unique entropy-maximizing graphon on the relevant boundary segment (cited from Pikhurko-Razborov [40] and the authors' earlier work [42]) and then use the compactness of reduced graphons, L2-perturbation arguments, the new 'worth' functional, and finite-dimensional calculus to show that nearby optimizers are unique and multipodal. The boundary optimizer is not fitted or defined in terms of the present conclusions; it is an independent prior theorem. No parameter is fitted to a subset of data and then renamed a prediction: the multipodal parameters are determined by the constraint equations (e,t), and the claimed uniqueness and podal structure are derived rather than assumed. The self-citations that do appear ([42], [44], [26]) supply background, the LDP, and the boundary uniqueness theorem; they are load-bearing but independent published results, so they do not constitute circularity. The one caveat worth flagging is in Section 4.5, where analyticity is asserted to follow from the implicit function theorem 'as long as the tangent space does not degenerate'; the non-degeneracy is not proved. That is an omitted hypothesis/proof gap and a genuine correctness risk for the analyticity statements, but it is not a circular step: the paper does not define the phase as that which makes the tangent space nondegenerate, and no equation is shown to reduce to itself by construction. Similarly, the 'little algebra' steps in the multipodality estimates are omitted details, not circular inputs. The derivation chain is self-contained from the stated variational equations and external prior theorems, so the appropriate circularity score is 0.
Assumptions & free parameters
assumptions (5)
- standard math Large deviation principle for G(n,p) graphs and upper semicontinuity of the Shannon entropy on the reduced graphon space.
- standard math Compactness of the space of reduced graphons in the cut metric δcut.
- domain assumption The Boltzmann entropy B(e,t) equals the maximum Shannon entropy over graphons with densities (e,t).
- domain assumption The boundary entropy maximizers at (e,0) and on the scallops are unique and have the stated multipodal forms.
- ad hoc to paper The tangent space of the variety of optimal graphons does not degenerate, so the implicit function theorem yields analytic parameters.
Cite this review
Pith. "Pith review of Emergence in graphs with near-extreme constraints." pith.science (2026). https://pith.science/paper/MN4UV43P
@misc{pith2026241114556,
author = {Pith},
title = {Pith review of: Emergence in graphs with near-extreme constraints},
year = {2026},
howpublished = {\url{https://pith.science/paper/MN4UV43P}},
note = {Machine review of arXiv:2411.14556}
}
read the original abstract
We consider entropy-optimal graphons associated with extreme and near-extreme constraints on the densities of edges and triangles. We prove that the optimizers for near-extreme constraints are unique and multipodal and are perturbations of the previously known unique optimzers for extreme constraints. This proves the existence of infinitely many phases. We determine the podal structures in these phases and prove the existence of phase transitions between them.
Figures
Figures from the paper (2 more)
Forward citations
Cited by 2 Pith papers
-
Constrained Multi-Relational Graphons with Maximum Entropy
The authors claim to resolve the RRS conjecture for multi-relational graphons, but the main theorem silently requires an isolation hypothesis and a keystone topological-stability proof is only sketched.
-
Superfluid helium
The edge/triangle graph model gives a solvable toy analog in which a symmetry-based order parameter distinguishes the helium I and helium II phases.
Reference graph
Works this paper leans on
-
[1]
Aldous, Representations for partially exchangeable arrays of random variables , J
D. Aldous, Representations for partially exchangeable arrays of random variables , J. Multivar. Anal. 11 (1981) 581-598
work page 1981
-
[2]
N. Alon and M. Krivilevich, Extremal and probabilistic combinatorics, in W.T. Gowers (ed.), Prince- ton companion to mathematics, Princeton University Press, Princeton, N.J., 2008, 562-575
work page 2008
-
[3]
Anderson, Basic Notions of Condensed Matter Physics , Benjamin/Cummings, Menlo Park, 1984
P.W. Anderson, Basic Notions of Condensed Matter Physics , Benjamin/Cummings, Menlo Park, 1984
work page 1984
-
[4]
T. Austin, On exchangeable random variables and the statistics of large graphs and hypergraphs , Prob- ability Surveys 5 (2008) 80-145
work page 2008
-
[5]
N. Bogoliubov and D. Shirkov , Introduction to the Theory of Quantized Fields , Interscience Pub- lishers, New York, 1959
work page 1959
-
[6]
Bollobas, Extremal Graph Theory, Dover, New York, 2004
B. Bollobas, Extremal Graph Theory, Dover, New York, 2004
work page 2004
- [7]
- [8]
Show all 53 references
-
[9]
Bhamidi, G
S. Bhamidi, G. Bresler and A. Sly Mixing time of exponential random graphs 49th Annual IEEE Symposium on Foundations of Computer Science IEEE, Washington, DC. (2008) 803–812
2008
-
[10]
Chatterjee, Large Deviations for Random Graphs
S. Chatterjee, Large Deviations for Random Graphs. (Lecture notes for the 2015 Saint-Flour Summer School.) Springer Lecture Notes in Mathematics. Springer, Berlin-Heidelberg, 2017
2015
-
[11]
Chatterjee, An introduction to large deviations for random graphs , Bull
S. Chatterjee, An introduction to large deviations for random graphs , Bull. Amer. Math. Soc. 53 (2016) 617–642
2016
-
[12]
Chatterjee and P
S. Chatterjee and P. Dey Applications of Stein ’s method for concentration inequalities, 38 (2010) 2443-2485
2010
-
[13]
Chatterjee and P
S. Chatterjee and P. Diaconis , Estimating and understanding exponential random graph models , Ann. Statist. 41 (2013) 2428-2461; arXiv:1102.2650 (2011)
2013 arXiv
-
[14]
Chatterjee and S
S. Chatterjee and S. R. S. V aradhan, The large deviation principle for the Erd˝ os-R´ enyi random graph, Eur. J. Comb., 32 (2011) 1000-1017; arXiv:1008.1946 (2010)
2011 arXiv
-
[15]
Dembo and E
A. Dembo and E. Lubetzky, A large deviation principle for the Erd˝ os-R´ enyi uniform random graph, Electron. Commun. Probab. 23 (2018) 1-13
2018
-
[16]
Den Hollander, M
F. Den Hollander, M. Mandjes, A. Roccaverde and N. Starreveld , Breaking of ensemble equivalence for perturbed Erd˝ os-R´ enyi random graphs.Preprint, arXiv:1807.07750v4 (2021)
2021 arXiv
-
[17]
Diaconis, and S
P. Diaconis, and S. Janson, Graph limits and exchangeable random graphs, Rendiconti di Matematica e delle sue Applicazioni. Serie VII, 28(1), 2008, 33–61. http://www1.mat.uniroma1.it/ricerca/rendiconti/
2008
-
[18]
Dunford and J
N. Dunford and J. Schwartz, Linear Operators, Part I , Interscience Publishers, New York, 1967
1967
-
[19]
Ellis, Entropy, Large Deviations, and Statistical Mechanics , Springer-Verlag, New York, 1985
R.S. Ellis, Entropy, Large Deviations, and Statistical Mechanics , Springer-Verlag, New York, 1985
1985
-
[20]
Fienberg, S.E. (2010). Introduction to papers on the modeling and analysis of network data. Ann. Appl. Statist. 4, 1–4
2010
-
[21]
Fienberg, S.E. (2010). Introduction to papers on the modeling and analysis of network data II. Ann. Appl. Statist. 4, 533–534
2010
-
[22]
D. N. Hoover , Row-column exchangeability and a generalized model for probability , Exchangeability in probability and statistics (Rome, 1981), North-Holland, Amsterdam, 1982, 281-291
1981
-
[23]
Israel, Convexity in the Theory of Lattice Gases , Princeton University Press, Princeton, 1979
R. Israel, Convexity in the Theory of Lattice Gases , Princeton University Press, Princeton, 1979
1979
-
[24]
Kellenberg, Probabilistic symmetries and invariance principles , Springer, New York, 2005
O. Kellenberg, Probabilistic symmetries and invariance principles , Springer, New York, 2005
2005
-
[25]
Kenyon, C
R. Kenyon, C. Radin, K. Ren, and L. Sadun , Bipodal structure in oversaturated random graphs , Int. Math. Res. Notices 2018(2016) 1009-1044
2016
-
[26]
Kenyon, C
R. Kenyon, C. Radin, K. Ren, and L. Sadun , The Phases of Large Networks with Edge and Triangle Constraints, J. Phys. A. 50 (2017) 435001 EMERGENCE IN GRAPHS WITH NEAR-EXTREME CONSTRAINTS 45
2017
-
[27]
Lanford, in Lecture Notes in Physics , vol
O.E. Lanford, in Lecture Notes in Physics , vol. 20, ed. A. Lenard, Springer-Verlag, Berlin, 1973
1973
-
[28]
Laughlin, A Different Universe: Reinventing Physics from the Bottom Down , Basic Books (2006)
R. Laughlin, A Different Universe: Reinventing Physics from the Bottom Down , Basic Books (2006)
2006
-
[29]
Lov´asz, Large Networks and Graph Limits , American Mathematical Society, Providence, 2012
L. Lov´asz, Large Networks and Graph Limits , American Mathematical Society, Providence, 2012
2012
-
[30]
Lov´asz and B
L. Lov´asz and B. Szegedy , Limits of dense graph sequences , J. Combin. Theory Ser. B 98 (2006) 933-957
2006
-
[31]
Lov´asz and B
L. Lov´asz and B. Szegedy , Szemer´ edi’s lemma for the analyst, GAF A 17 (2007) 252-270
2007
-
[32]
Lov´asz and B
L. Lov´asz and B. Szegedy, Finitely forcible graphons, J. Combin. Theory Ser. B 101 (2011) 269-301
2011
-
[33]
Maggi, Optimal Mass Transport on Euclidean spaces , Cambridge University Press, to appear
F. Maggi, Optimal Mass Transport on Euclidean spaces , Cambridge University Press, to appear
-
[34]
Mantel, Problem 28, Wiskundige Opgaven, 10 (1906) 60-61
W. Mantel, Problem 28, Wiskundige Opgaven, 10 (1906) 60-61
1906
-
[35]
Neeman, C
J. Neeman, C. Radin and L. Sadun , Phase transitions in finite random networks , J Stat Phys 181 (2020) 305-328
2020
-
[36]
Neeman, C
J. Neeman, C. Radin and L. Sadun , Typical large graphs with given edge and triangle densities , Probab. Theory Relat. Fields (2023), https://doi.org/10.1007/s00440-023-01187-8. arxiv:2110.14052 (2010)
2023 arXiv
-
[37]
Neeman, C
J. Neeman, C. Radin and L. Sadun , Existence of a symmetric bipodal phase in the edge-triangle model, J. Phys. A: Math. Theor. 57 (2024) 095003
2024
-
[38]
Newman, Networks: an Introduction, Oxford University Press, 2010
M.E.J. Newman, Networks: an Introduction, Oxford University Press, 2010
2010
-
[39]
Park and M.E.J
J. Park and M.E.J. Newman , Solution for the properties of a clustered network Phys. Rev. E 72, (2005)026136
2005
-
[40]
Pikhurko and A
O. Pikhurko and A. Razborov, Asymptotic structure of graphs with the minimum number of trian- gles, Combin. Probab. Comput. 26 (2017) 138 - 160; arXiv:1204.2846 (2012)
2017 arXiv
-
[41]
Pippard , The Elements of Classical Thermodynamics , Cambridge University Press, Cambridge, 1979
A. Pippard , The Elements of Classical Thermodynamics , Cambridge University Press, Cambridge, 1979
1979
-
[42]
Radin and L
C. Radin and L. Sadun , Phase transitions in a complex network , J. Phys. A: Math. Theor. 46 (2013) 305002
2013
-
[43]
Radin and L
C. Radin and L. Sadun , Optimal graphons in the edge-2star model , arxiv:2305.00333 (2023)
2023
-
[44]
Radin and L
C. Radin and L. Sadun , Singularities in the entropy of asymptotically large simple graphs, J. Stat. Phys. 158 (2015) 853-865
2015
-
[45]
Razborov , On the Minimal Density of Triangles in Graphs , Combin
A. Razborov , On the Minimal Density of Triangles in Graphs , Combin. Prob. Comp. 17 (2008) 603–618
2008
-
[46]
Ruelle, A variational formulation of equilibrium statistical mechanics and the Gibbs phase rule, Commun
D. Ruelle, A variational formulation of equilibrium statistical mechanics and the Gibbs phase rule, Commun. Math Phys. 5 (1967) 324-329
1967
-
[47]
Ruelle, Statistical Mechanics; Rigorous Results, Benjamin, New York, 1969
D. Ruelle, Statistical Mechanics; Rigorous Results, Benjamin, New York, 1969
1969
-
[48]
Salinas, Introduction to Statistical Physics , , Graduate Texts in Contemporary Physics, Springer, New York, 2001
R. Salinas, Introduction to Statistical Physics , , Graduate Texts in Contemporary Physics, Springer, New York, 2001
2001
-
[49]
Simon, The Statistical Mechanics of Lattice Gases, Volume 1 Princeton University Press, Princeton, 1993
B. Simon, The Statistical Mechanics of Lattice Gases, Volume 1 Princeton University Press, Princeton, 1993
1993
-
[50]
Strauss, On a general class of models for interaction , SIAM Rev
D. Strauss, On a general class of models for interaction , SIAM Rev. 28 (1986) 513–527
1986
-
[51]
Santambrogio, Optimal Transport for Applied Mathematicians , Springer, Chem, 2005
F. Santambrogio, Optimal Transport for Applied Mathematicians , Springer, Chem, 2005
2005
-
[52]
Touchette, Equivalence and nonequivalence of ensembles: Thermodynamic, macrostate, and mea- sure levels, J
H. Touchette, Equivalence and nonequivalence of ensembles: Thermodynamic, macrostate, and mea- sure levels, J. Statist. Phys. 159, 987–1016 (2015)
2015
-
[53]
J. M. Yeomans , Statistical Mechanics of Phase Transitions , Clarendon Press, Oxford, 1992. Department of Mathematics, University of Texas at Austin Email address : radin@math.utexas.edu, sadun@math.utexas.edu
1992
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.