A designed tree model with a sharp congestion–fragmentation transition
When demand grows, a network can admit less of each extra unit of traffic. At the same time, its unused capacity can break into small pieces. This paper gives an explicit tree example in which both changes occur in the same shrinking interval, with a guarantee covering every optimal way to admit traffic.
The example responds to David Aldous’s conceptual request for a tractable congestion model. The physical tree is sparse, but its traffic is dense. Its capacities grow with network size, and its fixed random growth rates give quadratic time variance. These choices are part of the result’s scope.
Original abstract
We construct a bounded-degree physical tree model in which the normalized marginal admitted demand drops from one to zero while the spare-capacity graph changes from the entire tree to isolated vertices. Capacities arise from the unique cheapest fixed-topology enlargement supporting doubled initial traffic. Each of the k² cross-root streams has an independent, fixed-law exponential growth rate. An all-cuts estimate confines both changes, with probability tending to one, to an interval of width 16√(log k/k) around mean doubled demand. Both outer-phase conclusions hold for every optimizer. This is a specialized existence response to Aldous's conceptual congestion toy-model request. The width is an upper bound; no critical profile or universal traffic law is asserted.
The designed network
Take a complete rooted binary tree of height H ≥ 2. Each root side has k = 2H−1 leaves, and the whole tree has N = 4k−1 vertices and maximum degree three. Every left leaf sends one initial unit to every right leaf: k² streams in total. Each stream follows its unique tree path.
An edge with ke descendant leaves initially carries kke units and has that capacity. Increase capacities just enough to carry doubled initial traffic, charging a strictly positive linear price for each increment. The paths force the unique cheapest design:
Ce = 2kke.
Each terminal edge has capacity 2k; each of the two root edges has capacity 2k². The topology and these capacities then stay fixed.
Independently sample one rate Xij from the rate-one exponential distribution for each stream. Keep these samples fixed as time changes, and set its offered demand to dij(t) = 1 + (t−1)Xij, for t ≥ 1. Each stream has mean t and variance (t−1)².
Let Fk(t) be the largest total demand that can be admitted, allowing partial admission of each stream. The normalized marginal admission is its right derivative divided by the realized total offered slope Sk = ∑ijXij, which is positive almost surely:
rk(t) = F′k,+(t)/Sk.
For any optimizing admitted flow, keep exactly the physical edges whose load is strictly below capacity. This spare-capacity graph retains all N original vertices. Write Mk for its largest component size. Inside the transition window, this graph can depend on which optimizer is selected.
The joint transition, uniformly over optimizers
Put δk = 8√(log k/k) and
εk = 2k−31 + 2k−2/(1−k−2)² + (4/k²)k.
For every binary k large enough that δk < 1, with probability at least 1−εk, the following two statements hold simultaneously for every indicated time and every optimizer:
- For every 1 ≤ t ≤ 2−δk, all offered demand is admitted, rk(t) = 1, and the entire tree has spare capacity. Thus Mk(t) = N.
- For every t ≥ 2+δk, admitted throughput is Fk(t) = 2k², rk(t) = 0, and every physical edge is saturated. The spare graph consists of isolated vertices, so Mk(t) = 1.
The sufficient interval has total width 16√(log k/k) around t = 2, the point of mean doubled demand. Throughput saturates; its marginal drops.
For each fixed 1 ≤ t < 2, both rk(t) and Mk(t)/N converge in probability to one. For each fixed t > 2, both converge to zero. The component statement applies to any measurable choice of an optimizer. For every fixed t ≥ 1, including t = 2, Fk(t)/k² converges in probability to min(t, 2). Along the binary sizes, the outer-phase events also hold eventually almost surely under any common coupling.
Why the proof reduces to cuts
Every internal edge load is the sum of its descendant terminal loads. Physical feasibility therefore reduces exactly to a transportation problem: each left row and right column has capacity 2k, and each stream is bounded by its offered demand. Classical max-flow/min-cut expresses admitted throughput as the minimum of finitely many affine cut capacities. Their active slopes give the right derivative, including ties.
Before the window, exponential concentration makes every offered terminal total strictly smaller than its capacity. Full admission then leaves every physical edge slack. After the window, a bound over all transportation cuts shows that total throughput reaches 2k². Every optimizer must fill every terminal capacity and hence every physical edge. Monotonicity extends the two endpoint events to all earlier and later times simultaneously. The proof is analytic; finite controls in the supplement support checks of the reduction and do not establish the asymptotic theorem.
Scope and limitations
The displayed width is a sufficient upper bound. There is no matching lower bound, exact critical scale, asserted limit for rk(2), or critical component-size profile. The theorem applies to the stated binary sizes with δk < 1.
The physical network is sparse while its k² traffic streams are dense. Capacities increase with k; paths cannot reroute; internal constraints reduce to terminal constraints. The exponential slopes are sampled once, and their time variance is quadratic. Dividing by the realized offered slope is essential to the marginal statement. No adaptive growth, arbitrary cyclic-network result, linear-variance growth process or universal congestion law is supplied.
Aldous’s 2005 discussion, slide 5, already notes the explanatory limitations of easy tree models and expresses a preference for mean-field models. This example retains that limitation. It establishes one explicit existence result; suitability as the uniquely right conceptual model and historical priority remain unresolved.
Original files and manuscript
- Source and verification package (ZIP, 245,047 bytes) · Zenodo original ZIP
- Manuscript (PDF, 79,981 bytes) · Zenodo original PDF
Open the original five-page PDF · Download PDF · Zenodo record
The local PDF and ZIP are unchanged copies of the published originals, listed in the record’s order. The PDF is dated 21 October 2026 and prints version 1.0. Use the direct PDF link if the embedded reader is unavailable. The supplement documents its replay assumptions and limitations.
Prior work and source limits
Aldous supplies the conceptual request and doubled-demand design suggestion. Max-flow/min-cut and exponential concentration are classical ingredients. Capacitated random transportation, the highly optimized tolerance design paradigm, and congestion-related fragmentation are established antecedents. The contribution here is the explicit cheapest-design tree construction with its simultaneous marginal-admission and every-optimizer spare-connectivity theorem.
- D. Aldous, Congestion in networks: SOC, HOT and the percolation-fragmentation phase transition; conceptual problem index.
- L. R. Ford Jr. and D. R. Fulkerson, Maximal flow through a network (1956). DOI.
- R. Hassin and E. Zemel, Probabilistic analysis of the capacitated transportation problem (1988). DOI.
- R. M. Karp, R. Motwani and N. Nisan, Probabilistic analysis of network flow algorithms: December 1988 Berkeley report CSD-88-392; 1993 journal article.
- J. M. Carlson and J. Doyle, Complexity and robustness (2002), for the HOT/design background. DOI.
- M. Kim and F. Radicchi, Shortest-path percolation on random networks (2024), a related model that removes requested shortest paths sequentially. DOI.
Hassin–Zemel’s sufficient exponent separation does not directly cover this balanced near-capacity regime. The directed theorem in the actual 1988 Karp–Motwani–Nisan report assumes bounded integer capacities and positive constant mean surplus. Here the transportation reduction has continuous unbounded stream capacities and vanishing normalized surplus. The final 1993 journal body was not inspected. These comparisons do not rule out every deduction from older transportation results. Uninspected editions and unindexed or unpublished work remain limits on priority assessment; no worldwide firstness claim is made.
Citation and rights
Kriebel, Alec. (2026). A designed tree model with a sharp congestion–fragmentation transition (Version 1.0) [Unrefereed preprint]. Zenodo. doi:10.5281/zenodo.23527793. Download BibTeX.
The authored manuscript and supplement are licensed Creative Commons Attribution 4.0 International, as stated in the original LICENSE.txt. Third-party works retain their own rights.
Status and collaboration
AI tools were used extensively in the research, proof development, computation, literature review and writing. This is an unrefereed preprint; internal AI reviews do not constitute independent human peer review. The author is responsible for the claims.
Independent verification of the all-cuts argument, substantive comparison with the transportation literature, and work toward a journal version would be useful contributions. Collaboration and authorship would be based on actual contributions.