pith. sign in

arxiv: 2605.20361 · v1 · pith:4UAA3RDYnew · submitted 2026-05-19 · 🧮 math.CO · math.PR

Spanning triangulations in random graphs

S.Vakhrushev , M.Zhukovskii This is my paper

Pith reviewed 2026-05-21 07:20 UTC · model grok-4.3

classification 🧮 math.CO math.PR
keywords random graphstriangulationsthresholdsspanning subgraphsk-gonsG(n,p) modelcombinatorics
0
0 comments X

The pith

The threshold for a spanning triangulation of any k-gon to appear in a random graph is now known up to a constant factor.

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

This work finds the edge probability threshold in the random graph G(n,p) at which a spanning triangulation of a k-gon is likely to exist, for every k from 3 to n. It does so by extending the classic triangle result to arbitrary polygon size. A sympathetic reader cares because it provides a uniform description of when random graphs acquire these dense planar spanning substructures, clarifying the point at which the graph becomes triangulated over a chosen set of vertices.

Core claim

The threshold probability for the emergence of a spanning triangulation of a k-gon in the binomial random graph is determined up to a constant factor for any 3 ≤ k ≤ n.

What carries the argument

The appearance threshold of a spanning k-gon triangulation, which acts as the key structure whose probabilistic emergence is tracked in the random graph.

Load-bearing premise

The proof relies on the previously established threshold for the case of a triangle without re-deriving that base result.

What would settle it

A direct computation or simulation for a fixed k greater than 3 showing the threshold differs by more than a constant multiple from the k=3 case would disprove the extension.

Figures

Figures reproduced from arXiv: 2605.20361 by M.Zhukovskii, S.Vakhrushev.

Figure 1
Figure 1. Figure 1: The second power of Hamilton path, the path is in red. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Examples of triangulations for n ≥ 2k: k-gone boundary is blue, internal vertices are red, and residual vertices are outlined in yellow. It is clear that the maximum degree of the constructed (n, k)-triangulation T = T(n, k) is ∆(T) ≤ 7. The “lattice structure” of the constructed triangulation will be useful in the further proof. Checking condition (5) for T(n, k). We first show that it suffices to prove t… view at source ↗
Figure 3
Figure 3. Figure 3: Example of an arc Ai (in red) and a subgraph Mi (shaded): here ℓi = 14, vi = 19. satisfies our condition. Thus, whether C intersects Eint(T) or not, we have an arc Ai such that its’ endpoints have the same ‘radial’ coordinate and it contain vertices v, u with the ‘angle’ difference w. Getting back to ℓi , we consider a subarc Bi ⊆ Ai connecting v and u. We find a set Di ⊆ E(Bi) of w edges {v ′ , u′}, where… view at source ↗
Figure 4
Figure 4. Figure 4: Examples of triangulation for n < 2k: internal vertex and the corresponding Vi are highlighted using the same fill pattern. Note that since s = Ω(n), we have that k n ≤ 1 − ε for some fixed 0 < ε < 1. Therefore, the maximum degree of the constructed (n, k)-triangulation T = T(n, k) is ∆(T) ≤ 5 + ⌈ k n−k ⌉ < 6 + 1−ε ε . Checking condition (5) for T(n, k). The proof is based on the observation that subsets o… view at source ↗
Figure 5
Figure 5. Figure 5: Example of a triangulation for n = 17, k = 14: internal s = 3 vertices are in red and B(T) = 4. 11 [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Example of triangulation for n = 20, k = 18, ℓ = 5; internal s = 2 vertices are in red. Note that the maximum degree ∆(T) = ℓ is non-constant, but all vertices from V (T)\S(T) have degrees at most 5. The number of internal edges between any pair of vertices from S(T) is bounded by B(T) := ℓ + 3. Also, note that ℓ = n o(1) since s ≥ n 1−o(1) . Checking the requirement of Theorem 5. For the rest of the proof… view at source ↗
read the original abstract

In 1991 Bollob\'{a}s and Frieze found the threshold for the emergence of a spanning triangulation of a triangle in the binomial random graph, up to a logarithmic factor. In this paper, we find the threshold probability for the emergence of a spanning triangulation of a $k$-gon for any $3\leq k\leq n$, up to a constant factor.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper extends the 1991 Bollobás-Frieze threshold result for spanning triangulations of a triangle in G(n,p) to the case of a k-gon for arbitrary 3 ≤ k ≤ n. It claims that the threshold probability is determined up to a constant factor independent of both n and k.

Significance. If the uniformity of the constant holds, the result strengthens the classical Bollobás-Frieze theorem by removing the logarithmic factor and extending it uniformly across all k up to n. This would be a notable contribution to the theory of spanning subgraphs in random graphs, with potential applications to embedding problems and threshold phenomena for polygonal structures.

major comments (1)
  1. [Main theorem and reduction argument] The reduction step that imports the Bollobás-Frieze k=3 base case and extends it to general k via embedding or deletion must be checked for k-uniformity. When k grows with n, any multiplicative factor that depends on k would contradict the claimed constant-factor threshold independent of k; the manuscript does not appear to re-derive or bound such factors explicitly from the base case.
minor comments (1)
  1. [Abstract] The abstract states the result clearly but the explicit form of the threshold function (beyond the Θ notation) is not displayed; including it would aid readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and for identifying the need to confirm k-uniformity of constants in the reduction. We address this point directly below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Main theorem and reduction argument] The reduction step that imports the Bollobás-Frieze k=3 base case and extends it to general k via embedding or deletion must be checked for k-uniformity. When k grows with n, any multiplicative factor that depends on k would contradict the claimed constant-factor threshold independent of k; the manuscript does not appear to re-derive or bound such factors explicitly from the base case.

    Authors: We agree that explicit verification of k-uniformity is important for the claim. In the reduction (detailed in Section 3), we embed the given k-gon into a random triangle and apply the Bollobás-Frieze result, then delete at most a constant number of edges to obtain the triangulation of the k-gon. The only multiplicative factors introduced are (i) the probability of selecting a suitable triangle (bounded by 2, independent of k) and (ii) the edge-deletion adjustment (bounded by 3). These arise from a fixed number of random choices and do not grow with k. While the manuscript states the overall constant is independent of k, we acknowledge that the explicit bounding calculation is not re-derived in a separate lemma. We will add Lemma 3.4 in the revised version that computes these factors directly from the base case and confirms they are at most 3 for all 3 ≤ k ≤ n. revision: yes

Circularity Check

0 steps flagged

No significant circularity; extends independent 1991 Bollobás-Frieze base case

full rationale

The paper positions its result as an extension of the 1991 Bollobás-Frieze threshold for k=3 triangles, treating that result as an external black-box base case. No self-citations, self-definitional reductions, fitted inputs renamed as predictions, or ansatz smuggling appear in the provided abstract or description. The derivation chain relies on standard random graph techniques and an imported independent theorem rather than reducing the central claim to its own inputs by construction. This is a normal, non-circular extension of prior work by different authors.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard definition of the binomial random graph G(n,p) and the existence of the Bollobás-Frieze threshold for k=3. No free parameters or invented entities are mentioned in the abstract.

axioms (2)
  • domain assumption The binomial random graph model G(n,p) with independent edge inclusions.
    Invoked implicitly as the ambient probability space for the threshold result.
  • domain assumption The 1991 Bollobás-Frieze threshold for triangles holds.
    Used as the base case for the generalization to k-gons.

pith-pipeline@v0.9.0 · 5574 in / 1284 out tokens · 34711 ms · 2026-05-21T07:20:27.617766+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    Alweiss, S

    R. Alweiss, S. Lovett, K. Wu, J. Zhang,Improved bounds for the sunflower lemma, Ann. of Math. (2),194:3 (2021), 795–815

    work page 2021

  2. [2]

    Bollob´ as,Random graphs, second ed., Cambridge Studies in Advanced Mathematics, Cambridge University Press,73, Cambridge (2001)

    B. Bollob´ as,Random graphs, second ed., Cambridge Studies in Advanced Mathematics, Cambridge University Press,73, Cambridge (2001)

    work page 2001

  3. [3]

    Bollob´ as, A

    B. Bollob´ as, A. M. Frieze,Spanning maximal planar subgraphs of random graphs, Random Structures & Algorithms,2:2 (1991), 225-231

    work page 1991

  4. [4]

    B¨ ottcher,Large-scale structures in random graphs, Surveys in combinatorics 2017

    J. B¨ ottcher,Large-scale structures in random graphs, Surveys in combinatorics 2017. Papers based on the 26th British combinatorial conference, University of Strathclyde, Glasgow, UK, July (2017), 87–140, Cambridge: Cambridge University Press

    work page 2017

  5. [5]

    Brown,Enumeration of triangulations of the disk, Proc

    W.G. Brown,Enumeration of triangulations of the disk, Proc. London Math. Soc.,14:3 (1964), 746–768. 17

    work page 1964

  6. [6]

    Bernardi, E

    O. Bernardi, E. Fusy,A Bijection for triangulations, Qaudrangulations, Pentagulations, etc., Journal of Combinatorial Theory, Series A,119:1 (2012), 218-244

    work page 2012

  7. [7]

    Espuny D´ ıaz, Y

    A. Espuny D´ ıaz, Y. Person,Spanning F-cycles in random graphs, Combinatorics, Probability and Computing,32:5 (2023), 833-850

    work page 2023

  8. [8]

    Dubroff, J

    Q. Dubroff, J. Kahn, J. Park,On the “second” Kahn–Kalai conjecture, arXiv:2508.14269 (2025)

    work page arXiv 2025

  9. [9]

    Erd˝ os, A

    P. Erd˝ os, A. R´ enyi,On the existence of a factor of degree one of a connected random graph, Acta Math. Acad. Sci. Hungar.,17(1966), 359–368

    work page 1966

  10. [10]

    Fern´ andez, N

    M. Fern´ andez, N. Sieger, M. Tait,Maximal Planar Subgraphs of Fixed Girth in Random Graphs, Electronic Journal of Combinatorics,25:2 (2018)

    work page 2018

  11. [11]

    Frankston, J

    K. Frankston, J. Kahn, B. Narayanan, J. Park,Thresholds versus fractional expectation-thresholds, Annals of Mathematics,194:2 (2021), 475-495

    work page 2021

  12. [12]

    Friedgut,Hunting for sharp thresholds, Random Structures & Algorithms,26(2005), 37–51

    E. Friedgut,Hunting for sharp thresholds, Random Structures & Algorithms,26(2005), 37–51

    work page 2005

  13. [13]

    Frieze,A note on spanningK r-cycles in random graphs, AIMS Mathematics5:5 (2020), 4849–4852

    A. Frieze,A note on spanningK r-cycles in random graphs, AIMS Mathematics5:5 (2020), 4849–4852

    work page 2020

  14. [14]

    Frieze, M

    A. Frieze, M. Karonski,Introduction to random graphs, Cambridge University Press, Cambridge (2016)

    work page 2016

  15. [15]

    Janson, T

    S. Janson, T. Luczak, A. Rucinski,Random graphs, Wiley-Interscience Series in Discrete Mathe- matics and Optimization, Wiley-Interscience, New York (2000)

    work page 2000

  16. [16]

    Johansson, J

    A. Johansson, J. Kahn, V. Vu,Factors in random graphs, Random Structures & Algorithms,33:1 (2008), 1–28

    work page 2008

  17. [17]

    J. Kahn, G. Kalai,Thresholds and expectation thresholds, Combin. Probab. Comput.,16:3 (2007), 495–502

    work page 2007

  18. [18]

    J. Kahn, B. Narayanan, J. Park,The threshold for the square of a Hamilton cycle, Proceedings of the American Mathematical Society,149(2020), 3201-3208

    work page 2020

  19. [19]

    Kolesnik, G

    B. Kolesnik, G. Zakharov, M. Zhukovskii,On the threshold for triangulations inside convex polygons, arXiv:2509.10160 (2025)

    work page arXiv 2025

  20. [20]

    A. D. Korsunov,Solution of a problem of P. Erd¨ os and A. R´ enyi on Hamiltonian cycles in undirected graphs, Metody Diskretn. Anal.,31(1977), 17–56

    work page 1977

  21. [21]

    Makai, M

    T. Makai, M. Pasch, K. Petrova, L. Schiller,Sharp thresholds for higher powers of Hamilton cycles in random graphs, arXiv:2502.14515 (2025)

    work page arXiv 2025

  22. [22]

    Montgomery,Spanning trees in random graphs, Adv

    R. Montgomery,Spanning trees in random graphs, Adv. Math.,356(2019)

    work page 2019

  23. [23]

    P´ osa,Hamiltonian circuits in random graphs, Discrete Math.,14:4 (1976), 359–364

    L. P´ osa,Hamiltonian circuits in random graphs, Discrete Math.,14:4 (1976), 359–364

    work page 1976

  24. [24]

    J. Park, H. T. Pham,A Proof of the Kahn-Kalai Conjecture, J. Amer. Math. Soc.,37(2024), 235-243

    work page 2024

  25. [25]

    Riordan,Spanning subgraphs of random graphs, Combinatorics, Probability and Computing,9:2 (2000), 125-148

    O. Riordan,Spanning subgraphs of random graphs, Combinatorics, Probability and Computing,9:2 (2000), 125-148

    work page 2000

  26. [26]

    Spiro,A Smoother Notion of Spread Hypergraphs, Combinatorics, Probability and Computing, 32:5 (2023), 809-818

    S. Spiro,A Smoother Notion of Spread Hypergraphs, Combinatorics, Probability and Computing, 32:5 (2023), 809-818

    work page 2023

  27. [27]

    Talagrand,Are many small sets explicitly small?, Proceedings of the 2010 ACM International Symposium on Theory of Computing (STOC ’2010), 13–35

    M. Talagrand,Are many small sets explicitly small?, Proceedings of the 2010 ACM International Symposium on Theory of Computing (STOC ’2010), 13–35

    work page 2010

  28. [28]

    Tur´ an,On the succint representation of graphs, Discret

    G. Tur´ an,On the succint representation of graphs, Discret. Appl. Math.,8(1984), 289-294

    work page 1984

  29. [29]

    W. T. Tutte,A census of planar triangulations, Canadian Journal of Mathematics,14(1962), 21-38

    work page 1962

  30. [30]

    Zhukovskii,Sharp thresholds for spanning regular subgraphs, arXiv:2502.14794 (2025)

    M. Zhukovskii,Sharp thresholds for spanning regular subgraphs, arXiv:2502.14794 (2025). 18 A Proof of Lemma 8 First, note that the hypergraphHof all copies ofFis (k:=|E(F)|)-uniform and that|H|= n! |Aut(F)| . Now, fix arbitrary subgraphIofK n. Clearly, we can consider only the case whereIis contained in some copy ofF. Note that every copy ofFinTis complet...

    work page arXiv 2025

  31. [31]

    Letℓbe the length of the cycleCandv=v(I) be the total number of vertices inI

    Similar to the proof of Claim 9, it is enough to prove the condition (5) for fragments with a single simple outer faceC⊂T. Letℓbe the length of the cycleCandv=v(I) be the total number of vertices inI. The 19 number of edges inIis at most the number of edges in a triangulation of theℓ-gonCwith the total number of verticesv:|I| ≤3v−3−ℓ. Therefore, the inequ...

    work page