Tripodal structure in undersaturated random graphs
William DiCarlo, Lorenzo Sadun · 2025
Read Tripodal structure in undersaturated random graphs by William DiCarlo, Lorenzo Sadun (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-16797.txt.
Introduction
William DiCarlo and Lorenzo Sadun explore, in a 2025 paper, the typical shape of random networks under two constraints at once: how many links they contain and how many triangles. In one puzzling region, theory expected the typical network to split into two blocks, but simulations hinted at three. The authors map that region of link and triangle densities numerically to find where the three-block, or tripodal, pattern actually holds.
They show the tripodal region ends at a sharp boundary, where the typical graph jumps suddenly to the two-block form rather than shading into it. They also find at least one more sudden jump inside the tripodal region itself, where the numbers describing typical graphs change abruptly. The work clarifies a corner of random graph theory where smooth expectations failed, and shows phase changes hiding where none were predicted.
Catalog record
| CREATOR | William DiCarlo, Lorenzo Sadun |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 37 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-16797
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Tripodal structure in undersaturated random graphs William DiCarlo, Lorenzo Sadun Abstract . We numerically investigate typical graphs in a region of the Strauss model of random graphs with constraints on the densities of edges and triangles. This region, where typical graphs had been expected to be bipodal but turned out to be tripodal, involves edge densities e e below e 0 = ( 3 − 3 ) / 6 ≈ 0.2113 e_{0}=(3-\sqrt{3})/6\approx 0.2113 and triangle densities t t slightly below e 3 e^{3} . We determine the extent of this region in ( e , t ) (e,t) space and show that there is a discontinuous phase transition at the boundary between this region and a bipodal phase. We further show that there is at least one phase transition within this region, where the parameters describing typical graphs change discontinuously. 2020 Mathematics Subject Classification 05C80, 60C05, also 05C35, 82-05 1. Introduction and results 1.1. Background We are investigating the structure of large random graphs with specified densities (e,t) of edges and triangles, the so-called Strauss model [ 20 ] . More precisely, we consider the ensemble of all graphs on n vertices that have the specified densities of edges and triangles, up to a small tolerance that goes to zero as n\to\infty . For most values of (e,t) , there is a typical structure to such graphs, with all but a tiny fraction having essentially the same statistical properties. The fundamental question is understanding how this structure varies with (e,t) . In this paper we study this question when t is slightly below e^{3} and e is less than the threshold e_{0}=(3-\sqrt{3})/6\approx 0.2113 . The key algebraic tool is graphons . (See [ 10 ] for an overview of this expansive subject and [ 2 , 3 , 11 ] for some original references.) A graphon is a function g:[0,1]^{2}\to[0,1] with g(x,y)=g(y,x) . This can be viewed either as a limit of large graphs or as a random process for producing graphs. To generate a graph on n vertices from a graphon, first pick n numbers x_{i} independently and uniformly on [0,1] . Then flip \binom{n}{2} independent biased coins, assigning an edge to vertices i and j with probability g(x_{i},x_{j}) . The statistical properties of graphs that are generated this way are easy to read off from the graphon. For instance, the expected densities of edges and triangles are (1) \displaystyle\varepsilon(g) \displaystyle:= \displaystyle\int_{0}^{1}\!\int_{0}^{1}g(x,y)\,dx\,dy\qquad\qquad\hbox{and} (2) \displaystyle\tau(g) \displaystyle:= \displaystyle\int_{0}^{1}\!\int_{0}^{1}\!\int_{0}^{1}g(x,y)g(y,z)g(z,x)\,dx\,dy\,dz, respectively. As n\to\infty , the variance in the edge and triangle densities go to zero, so almost all graphs generated by g have edge and triangle densities close to (\varepsilon(g),\tau(g)) . We can thus speak of \varepsilon(g) and \tau(g) as the edge/triangle densities of the graphon, and not just as the expected densities. The number of graphs that are created in this way is determined by the Shannon entropy of the graphon, (3) S(g):=\int_{0}^{1}\!\int_{0}^{1}H(g(x,y))\,dx\,dy, where H(u)=-(u\ln(u)+(1-u)\ln(1-u)) is the usual entropy of a coin flip with probability u of getting heads. Thanks to the large deviations principle of Chatterjee and Varadhan [ 4 ] and to subsequent work by Radin and Sadun [ 17 ] , understanding the typical structure of graphs with edge/triangle densities (e,t) is equivalent to finding the graphon g that maximizes S(g) subject to the constraints (\varepsilon(g),\tau(g))=(e,t) . If \tilde{g}(x,y)=g(\sigma(x),\sigma(y)) , where \sigma is a measure-preserving transformation of [0,1] , then \tilde{g} and g have the same densities and the same entropy. Indeed, they generate the same graphs on n vertices with exactly the same probabilities! When we apply constraints, maximize the entropy, and speak of the optimal graphon being unique, we always mean “unique up to measure-preserving transformation.” If the entropy-maximizing graphon g with edge/triangle densities (e,t) is unique (up to measure-preserving transformations), then the ensemble of large graphs with edge/triangle densities close to (e,t) is essentially the same as the ensemble of large graphs generated by g . Specifically, for any \epsilon>0 there exists a constant K>0 such that all but a fraction e^{-Kn^{2}} of the graphs on n vertices with edge/triangle densities close to (e,t) are within \epsilon of g in the “cut metric” [ 17 , 19 ] . Conversely, all but an exponentially small fraction of the graphs generated by g have edge/triangle densities close to (e,t) . The combinatorial problem of understanding typical graphs with specified edge/triangle densities thus reduces to the analytic problem of maximizing S(g) subject to the constraints (\varepsilon(g),\tau(g))=(e,t) . The space of all possible values of (e,t) in the edge-triangle model was first worked out by Razborov [ 16 ] (see also [ 15 ] ) and is called the Razborov triangle. See Figure 1 . A phase is an open subset of the Razborov triangle where the typical structure is a real-analytic function of (e,t) in the sense that the optimal graphon is unique and depends analytically on (e,t) . This implies that the density of any fixed subgraph, such as a square or pentagon or tetrahedron, is also an analytic function of (e,t) . At a phase boundary, the optimal graphon fails to be analytic and may even change discontinuously, implying an abrupt change in the density of some subgraph. Figure 1. The Razborov triangle. The curvature of the “scallops” on the lower right is exaggerated for visibility. In 2017, [ 8 ] conjectured that the Razborov triangle consisted of one phase above the “Erdős-Rényi” curve t=e^{3} and three infinite families of phases below the Erdős-Rényi curve. See Figure 2 for a schematic phase diagram. The conjectured phase picture has been proven to be correct • Just above the Erdős-Rényi curve. [ 7 ] • Just below the Erdős-Rényi curve when e>1/2 . [ 12 ] • Near the line segment e=1/2 , 0<t<1/8 . [ 14 ] • Just below the top boundary t=e^{3/2} . [ 18 ] • Just above the bottom boundary when e<1/2 . [ 18 ] • Just above each of the “scallops” on the lower right portion of the boundary, with the k -th scallop running from e=\frac{k}{k+1} to e=\frac{k+1}{k+2} . [ 18 ] That is, the optimal graphons in open subsets of the F(1,1) , B(1,1) , A(2,0) , and C(k,2) phases, for every positive integer k , have been proven to exist, to be unique, and to have the form conjectured in [ 8 ] . Figure 2. A conjectured phase portrait in the edge/triangle model. The size and shape of each phase are only schematic. In a realistic rendering, many of the phases would be too small to see. However, there is also a region, with e<e_{0}:=(3-\sqrt{3})/6\approx 0.2113 and with t slightly below e^{3} , where the optimal graphon is not described by the A(2,0) phase of Figure 2 [ 14 ] ! Unfortunately, the proof that the typical structure is not A(2,0) did not provide any estimates for how big this exceptional region is or what the typical structure is. [ 14 ] exhibited a “tripodal” graphon that has more entropy than the “bipodal” A(2,0) graphon, but did not optimize the parameters of this tripodal graphon or rule out the possibility that there is a different kind of graphon with even more entropy. In other words, Figure 2