pith. sign in

arxiv: 1906.10355 · v1 · pith:R65YJX2Dnew · submitted 2019-06-25 · 🧮 math.PR · math.CO

Graphon convergence of random cographs

Benedikt Stufler This is my paper

Pith reviewed 2026-05-25 16:46 UTC · model grok-4.3

classification 🧮 math.PR math.CO
keywords cographsgraphonsrandom graphsgraphon convergenceprobabilistic limitlabelled graphsunlabelled graphs
0
0 comments X

The pith

Random labelled and unlabelled cographs converge in probability to a deterministic graphon as the number of vertices tends to infinity.

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

The paper examines sequences of random cographs on n vertices, considering both labelled and unlabelled versions generated according to standard models. It establishes that these sequences converge in the graphon metric to a fixed limit object in the space of graphons. A sympathetic reader would care because graphon convergence supplies a compact way to describe the asymptotic structure of dense random graphs, allowing one to read off limiting properties such as subgraph densities directly from the limit. The result applies separately to the labelled and unlabelled cases yet produces the same limiting graphon.

Core claim

Random cographs on n vertices, whether generated in the labelled or unlabelled model, converge in probability to a specific graphon W as n tends to infinity; the same deterministic W arises in both models.

What carries the argument

The graphon, a symmetric measurable function [0,1]×[0,1]→[0,1] that encodes the limiting edge probabilities of a sequence of graphs.

If this is right

  • Subgraph densities in random cographs approach the integrals defined by the limit graphon.
  • The same limit object governs both the labelled and unlabelled ensembles.
  • Any continuous functional of the graphon, such as homomorphism densities, admits an explicit limiting value.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The convergence may extend to other graph classes that admit recursive decompositions similar to cographs.
  • One could test the result by sampling large cographs and numerically estimating their cut distance to the predicted W.
  • The common limit suggests that the labelled and unlabelled models become indistinguishable at the level of global statistics.

Load-bearing premise

The specific random generation processes used for labelled and unlabelled cographs are assumed to be compatible with the topology on the space of graphons.

What would settle it

A direct computation showing that the cut distance between the empirical graphon of a random cograph on n vertices and the claimed limit W fails to tend to zero in probability as n grows.

read the original abstract

We study the behaviour of random labelled and unlabelled cographs with n vertices as n tends to infinity. Our main result is a novel probabilistic limit in the space of graphons.

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

0 major / 1 minor

Summary. The manuscript studies the asymptotic behaviour of two models of random cographs (labelled and unlabelled) on n vertices. Its central claim is the existence of a novel probabilistic limit object in the space of graphons.

Significance. If the claimed limit holds, the result supplies a concrete new example of graphon convergence for a hereditary graph class (P4-free graphs) generated via cotree representations. This could serve as a test case for general theorems on graphon limits of random graphs with forbidden induced subgraphs and would be of interest to researchers working on graph limits and random combinatorial structures.

minor comments (1)
  1. The abstract refers to 'random labelled and unlabelled cographs' without specifying the precise probability measures; the manuscript should make the two generative models explicit in the introduction or §2 before stating the limit theorem.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their review and for noting the potential interest of our result on graphon limits for random cographs. The recommendation is listed as uncertain with no specific major comments provided in the report, so we have no individual points to rebut. We remain available to supply additional details or clarifications if needed to resolve any uncertainty.

Circularity Check

0 steps flagged

No significant circularity: limit theorem derived from model definitions

full rationale

The paper establishes a probabilistic limit for random labelled and unlabelled cographs in the graphon space as n tends to infinity. The abstract and context describe a standard convergence result in a metric space of graphons, with no equations or steps shown that reduce the claimed limit to a fitted parameter, self-definition, or load-bearing self-citation. The derivation is expected to proceed from the cotree-based generative models to the cut-metric or homomorphism-density limit via standard probabilistic arguments, remaining self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The abstract does not provide sufficient detail to identify any free parameters, axioms, or invented entities.

pith-pipeline@v0.9.0 · 5527 in / 968 out tokens · 49870 ms · 2026-05-25T16:46:13.476261+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages · 2 internal anchors

  1. [1]

    , " * write output.state after.block = add.period write newline

    ENTRY address archive author booktitle chapter doi edition editor eid eprint howpublished institution isbn issn journal key month note number organization pages publisher school series title type url volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'b...

    work page

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...

    work page

  3. [3]

    The continuum random tree

    David Aldous. The continuum random tree. III . Ann. Probab. 21 (1), 248--289 (1993). ISSN 0091-1798

    work page 1993

  4. [4]

    Universal limits of substitution-closed permutation classes

    Fr \'e d \'e rique Bassino , Mathilde Bouvel , Valentin F \'e ray , Lucas Gerin , Micka \"e l Maazoun and Adeline Pierrot . Universal limits of substitution-closed permutation classes . arXiv e-prints arXiv:1706.08333 (2017). 1706.08333

    work page arXiv 2017

  5. [5]

    Scaling limits of permutation classes with a finite specification: a dichotomy

    Fr \'e d \'e rique Bassino , Mathilde Bouvel , Valentin F \'e ray , Lucas Gerin , Micka \"e l Maazoun and Adeline Pierrot . Scaling limits of permutation classes with a finite specification: a dichotomy . arXiv e-prints arXiv:1903.07522 (2019). 1903.07522

    work page arXiv 1903

  6. [6]

    The B rownian limit of separable permutations

    Fr\' e d\' e rique Bassino, Mathilde Bouvel, Valentin F\' e ray, Lucas Gerin and Adeline Pierrot. The B rownian limit of separable permutations. Ann. Probab. 46 (4), 2134--2189 (2018). ISSN 0091-1798. doi:10.1214/17-AOP1223. ://doi.org/10.1214/17-AOP1223

    work page doi:10.1214/17-aop1223 2018

  7. [7]

    Bell, Stanley N

    Jason P. Bell, Stanley N. Burris and Karen A. Yeats. Counting rooted trees: the universal law t(n) C -n n -3/2 . Electron. J. Combin. 13 (1), Research Paper 63, 64 pp. (electronic) (2006). ISSN 1077-8926. ://www.combinatorics.org/Volume_13/Abstracts/v13i1r63.html

    work page 2006

  8. [8]

    Boltzmann samplers, P \'olya theory, and cycle pointing

    Manuel Bodirsky, \'E ric Fusy, Mihyun Kang and Stefan Vigerske. Boltzmann samplers, P \'olya theory, and cycle pointing. SIAM J. Comput. 40 (3), 721--769 (2011). ISSN 0097-5397. doi:10.1137/100790082. ://dx.doi.org/10.1137/100790082

    work page doi:10.1137/100790082 2011

  9. [9]

    A decorated tree approach to random permutations in substitution-closed classes

    Jacopo Borga , Mathilde Bouvel , Valentin F \'e ray and Benedikt Stufler . A decorated tree approach to random permutations in substitution-closed classes . arXiv e-prints arXiv:1904.07135 (2019). 1904.07135

    work page arXiv 1904

  10. [10]

    A simple linear time L ex BFS cograph recognition algorithm

    Anna Bretscher, Derek Corneil, Michel Habib and Christophe Paul. A simple linear time L ex BFS cograph recognition algorithm. SIAM J. Discrete Math. 22 (4), 1277--1296 (2008). ISSN 0895-4801. doi:10.1137/060664690. ://doi.org/10.1137/060664690

    work page doi:10.1137/060664690 2008

  11. [11]

    Large deviation probabilities for sums of random variables with heavy or subexponential tails

    Daren BH Cline and Tailen Hsing. Large deviation probabilities for sums of random variables with heavy or subexponential tails. Department of Statistics, Texas A & M University (1989)

    work page 1989

  12. [12]

    D. G. Corneil, H. Lerchs and L. Stewart Burlingham. Complement reducible graphs. Discrete Appl. Math. 3 (3), 163--174 (1981). ISSN 0166-218X. doi:10.1016/0166-218X(81)90013-5. ://doi.org/10.1016/0166-218X(81)90013-5

    work page doi:10.1016/0166-218x(81)90013-5 1981

  13. [13]

    Graph limits and exchangeable random graphs

    Persi Diaconis and Svante Janson. Graph limits and exchangeable random graphs. Rend. Mat. Appl. (7) 28 (1), 33--61 (2008). ISSN 1120-7183

    work page 2008

  14. [14]

    Boltzmann samplers for the random generation of combinatorial structures

    Philippe Duchon, Philippe Flajolet, Guy Louchard and Gilles Schaeffer. Boltzmann samplers for the random generation of combinatorial structures. Combin. Probab. Comput. 13 (4-5), 577--625 (2004). ISSN 0963-5483. doi:10.1017/S0963548304006315. ://dx.doi.org/10.1017/S0963548304006315

    work page doi:10.1017/s0963548304006315 2004

  15. [15]

    Schr\"oder parenthesizations and chordates

    Richard Ehrenborg and Miguel M \'e ndez. Schr\"oder parenthesizations and chordates. J. Combin. Theory Ser. A 67 (2), 127--139 (1994). ISSN 0097-3165. doi:10.1016/0097-3165(94)90008-6. ://dx.doi.org/10.1016/0097-3165(94)90008-6

    work page doi:10.1016/0097-3165(94)90008-6 1994

  16. [16]

    Boltzmann sampling of unlabelled structures

    Philippe Flajolet, \'E ric Fusy and Carine Pivoteau. Boltzmann sampling of unlabelled structures. In Proceedings of the N inth W orkshop on A lgorithm E ngineering and E xperiments and the F ourth W orkshop on A nalytic A lgorithmics and C ombinatorics , pages 201--211. SIAM, Philadelphia, PA (2007)

    work page 2007

  17. [17]

    B. V. Gnedenko and A. N. Kolmogorov. Limit distributions for sums of independent random variables. Addison-Wesley Publishing Company, Inc., Cambridge, Mass. (1954). Translated and annotated by K. L. Chung. With an Appendix by J. L. Doob

    work page 1954

  18. [18]

    Algorithmic graph theory and perfect graphs, volume 57 of Annals of Discrete Mathematics

    Martin Charles Golumbic. Algorithmic graph theory and perfect graphs, volume 57 of Annals of Discrete Mathematics. Elsevier Science B.V., Amsterdam, second edition (2004). ISBN 0-444-51530-5. With a foreword by Claude Berge

    work page 2004

  19. [19]

    Scaling limits of M arkov branching trees with applications to G alton- W atson and random unordered trees

    B \'e n \'e dicte Haas and Gr \'e gory Miermont. Scaling limits of M arkov branching trees with applications to G alton- W atson and random unordered trees. Ann. Probab. 40 (6), 2589--2666 (2012). ISSN 0091-1798. doi:10.1214/11-AOP686. ://dx.doi.org/10.1214/11-AOP686

    work page doi:10.1214/11-aop686 2012

  20. [20]

    Sesqui-type branching processes

    S. Janson , O. Riordan and L. Warnke . Sesqui-type branching processes . ArXiv e-prints (2017). 1706.00283

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  21. [21]

    Sadagopan

    Harshita Kona and N. Sadagopan. On some combinatorial problems in cographs. Int. J. Adv. Eng. Sci. Appl. Math. 11 (1), 25--39 (2019). ISSN 0975-0770. doi:10.1007/s12572-019-00244-7. ://doi.org/10.1007/s12572-019-00244-7

    work page doi:10.1007/s12572-019-00244-7 2019

  22. [22]

    Large networks and graph limits, volume 60 of American Mathematical Society Colloquium Publications

    L\' a szl\' o Lov\' a sz. Large networks and graph limits, volume 60 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI (2012). ISBN 978-0-8218-9085-1. doi:10.1090/coll/060. ://doi.org/10.1090/coll/060

    work page doi:10.1090/coll/060 2012

  23. [23]

    The CRT is the scaling limit of unordered binary trees

    Jean-Fran c ois Marckert and Gr \'e gory Miermont. The CRT is the scaling limit of unordered binary trees. Random Structures Algorithms 38 (4), 467--501 (2011). ISSN 1042-9832. doi:10.1002/rsa.20332. ://dx.doi.org/10.1002/rsa.20332

    work page doi:10.1002/rsa.20332 2011

  24. [24]

    Scaling limits of random P \'olya trees

    Konstantinos Panagiotou and Benedikt Stufler. Scaling limits of random P \'olya trees. Probab. Theory Related Fields 170 (3-4), 801--820 (2018). ISSN 0178-8051. doi:10.1007/s00440-017-0770-4. ://doi.org/10.1007/s00440-017-0770-4

    work page doi:10.1007/s00440-017-0770-4 2018

  25. [25]

    Asymptotic enumeration of cographs

    Vlady Ravelomanana and Lo\" y s Thimonier. Asymptotic enumeration of cographs. In Brazilian S ymposium on G raphs, A lgorithms and C ombinatorics , volume 7 of Electron. Notes Discrete Math., page 4. Elsevier Sci. B. V., Amsterdam (2001)

    work page 2001

  26. [26]

    Riordan and L

    O. Riordan and L. Warnke . The phase transition in bounded-size Achlioptas processes . ArXiv e-prints (2017). 1704.08714

    work page arXiv 2017

  27. [27]

    Limits of random tree-like discrete structures

    Benedikt Stufler . Limits of random tree-like discrete structures . ArXiv e-prints (2016). 1612.02580

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  28. [28]

    Random enriched trees with applications to random graphs

    Benedikt Stufler. Random enriched trees with applications to random graphs. Electronic Journal of Combinatorics 25 (3) (2018)

    work page 2018

  29. [29]

    The continuum random tree is the scaling limit of unlabeled unrooted trees

    Benedikt Stufler. The continuum random tree is the scaling limit of unlabeled unrooted trees. Random Structures & Algorithms 0 (0) (2019+)

    work page 2019

  30. [30]

    @lbibitem[#1]#2 [\@biblabel #1 ] @tempwidthb \@biblabel #1 @tempwidthb> @tempwidtha @tempwidtha= @tempwidthb @filesw \@auxout #2 #1 @bibitem#1 @filesw \@auxout #1 \@listctr @tempwidthb \@biblabel @tempwidthb> @tempwidtha @tempwidtha= @tempwidthb \@lbibitem @lbibitem \@bibitem @bibitem @multicol multicol.sty \@classname Loading multicol.sty multicol @multi...

    work page 2000