Dong Huang and Shuangping Li’s “The lower tail of triangle counts in sparse random graphs” examines how an Erdős–Rényi random graph can contain substantially fewer triangles than expected. In this model, denoted \(G(n,p)\), each possible edge between \(n\) vertices is present independently with probability \(p\). The authors study the sparse regime in which \(p\) tends to zero while remaining much larger than \(n^{-1/2}\). For a fixed \(\eta\in(0,1)\), they investigate the event that the triangle count is at most \(\eta\) times its expectation, asking both how unlikely this event is and what a typical graph looks like when conditioned on it. These questions connect probability with structure. The large-deviation rate captures the leading exponential scale of the lower-tail probability, while the structural analysis identifies the edge arrangements that most efficiently suppress triangles. One possibility is a uniform reduction in edge density. Another is an uneven distribution of edges between groups of vertices. This distinction matters because a graph conditioned on a rare event need not resemble an ordinary random graph with a lower edge probability. Building on earlier work, the authors study a variational problem over graphons—continuous representations of large graph structures that allow competing edge-density patterns to be compared. Their main contribution is to solve this problem for every \(\eta\in(0,1)\) and classify all minimizing graphons. Each minimizer is either constant or a step graphon with two equally sized blocks. Consequently, the conditioned random graph is close either to an Erdős–Rényi graph or to a symmetric two-block stochastic block model. Despite the many conceivable ways to suppress triangles, the optimal structures therefore belong to two simple families. The authors identify a first-order phase transition between these regimes at approximately \(\eta=0.009217\), corresponding to a triangle count of roughly 0.9217 percent of its expectation. The transition marks an abrupt change between competing optimal structures rather than a gradual deformation of a single structural type. According to the abstract, these results resolve a conjecture of Zhao and an open problem of Janson and Warnke concerning triangles, providing a complete description of the lower tail in the stated sparse regime. The conclusions apply specifically to triangle counts, fixed \(\eta\), and probabilities satisfying \(n^{-1/2}\ll p\ll1\). This summary is based solely on the supplied title, authors, and abstract; the full text was unavailable under the stated license restriction. The abstract does not specify the proof techniques, optimal edge densities, explicit large-deviation rate, quantitative error bounds, or precise meaning of structural closeness. It also does not describe coexistence at the transition, so those details cannot be assessed here.
When Random Graphs Have Surprisingly Few Triangles
A triangle is one of the simplest patterns in a network: three vertices, each connected to the other two. Yet understanding what happens when a random graph contains far fewer triangles than expected leads to a surprisingly rich question. Does the graph simply become less connected everywhere, or does it reorganize its edges into a different structure?
In “The lower tail of triangle counts in sparse random graphs,” Dong Huang and Shuangping Li answer this question in an important sparse setting. Their results connect the probability of an unusually low triangle count with the shape of the graphs that produce it. The central finding is striking: although countless arrangements might suppress triangles, the optimal structures fall into just two simple families.
The Random Graph Model
The starting point is the Erdős–Rényi random graph, written G(n,p). There are n vertices, and every possible edge appears independently with probability p. A triangle requires three particular edges, so each set of three vertices forms a triangle with probability p cubed. The expected triangle count is therefore the number of three-vertex subsets multiplied by p cubed.
The authors consider graphs that become increasingly sparse as n grows. Specifically, p tends to zero but remains much larger than the reciprocal of the square root of n. This restriction matters: the conclusions describe this particular range of sparsity, not every possible random graph model or edge probability.
They fix a number eta between zero and one and ask what happens when the triangle count is at most eta times its expectation. For instance, eta equal to 0.1 means allowing no more than one-tenth of the expected number of triangles.
Two Questions Behind One Rare Event
The first question concerns probability: how unlikely is such a substantial triangle deficit? The relevant object is a large-deviation rate, which captures the leading exponential scale of that probability. Rather than merely saying the event becomes rare, this approach identifies its dominant probabilistic cost.
The second question concerns structure: given that the rare event has occurred, what does a typical graph look like? Conditioning on an unusually small triangle count can introduce organization that was absent from the original independent-edge model.
These questions are closely linked. Some edge arrangements suppress triangles more efficiently than others. The structures that achieve the best balance between triangle reduction and probabilistic cost determine both the lower-tail behavior and the typical appearance of a conditioned graph.
Two Ways to Suppress Triangles
Reduce Connections Everywhere
The most straightforward possibility is a uniform reduction in edge density. If every potential connection becomes less likely, triangles become less likely too. In this scenario, the conditioned graph resembles another Erdős–Rényi graph, but with a lower edge probability.
This preserves the original model’s basic symmetry: no group of vertices receives special treatment. The graph is still uniformly random in its overall organization, simply less connected.
Redistribute Connections Between Groups
A different strategy is to divide the vertices into groups and distribute edges unevenly within and between them. Because triangles depend on how three edges fit together, their abundance can change through edge placement, not just through a reduction in the total number of edges.
The authors show that the relevant alternative has two equally sized blocks. Its random-graph counterpart is a symmetric two-block stochastic block model, where connection probabilities depend on whether vertices belong to the same block or different blocks.
Why Graphons Enter the Picture
To compare these possibilities, the paper studies a variational problem over graphons. A graphon is a continuous representation of a large graph’s edge-density pattern. Constant graphons describe uniform connectivity, while step graphons describe block-based patterns.
This framework allows many conceivable arrangements to compete within one optimization problem. Huang and Li’s main contribution is to solve that problem for every fixed eta between zero and one and classify all its minimizers. Every minimizer is either constant or a step graphon with two equally sized blocks.
The corresponding structural conclusion is that a graph conditioned on the triangle deficit is close either to an Erdős–Rényi graph or to a symmetric two-block stochastic block model. The abstract does not specify the precise mathematical meaning of “close,” so that statement should not be read as a claim about any particular distance measure.
An Abrupt Structural Transition
The paper identifies a first-order phase transition at approximately eta equal to 0.009217. This corresponds to a triangle count of roughly 0.9217 percent of its expectation.
The significance is not merely that one numerical threshold separates two regimes. A first-order transition means the optimal structure changes abruptly between competing types, rather than gradually deforming along a single structural family. Uniform thinning and two-block organization represent genuinely different responses to the rare-event constraint.
What the Result Establishes—and What Remains Unspecified Here
The work provides a complete classification of the optimizing structures for this triangle lower-tail problem in the stated sparse regime. It demonstrates why an unusually triangle-poor graph cannot always be understood simply as an ordinary random graph with fewer edges.
This account is based only on the supplied title, authors, and abstract; the full text was unavailable under the stated license restriction. Proof techniques, optimal edge densities, explicit rate formulas, quantitative error bounds, and behavior exactly at the transition are therefore not assessed here. Within those limits, the message is clear: rare events can reshape a random graph, and even a simple constraint on triangles can trigger an abrupt change in its organization.
