Asymptotics of the number of labelled connected sparse multitype graphs

Luisa Andreis; Mario Veshaj

Asymptotics of the number of labelled connected sparse multitype graphs

T0 review · 2 major / 0 minor · reviewed 2026-06-27 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A connected multitype graph with given edge counts equals the giant component of a larger random graph with tuned kernel, which fixes its exponential asymptotics.

desk verdict The multitype extension of Bender-Canfield-McKay via tuned IRG giant components is new but rests on an unverified claim that standard LDPs carry over unchanged under exact edge-matrix conditioning. read the letter →

arxiv 2606.17912 v1 pith:D7A2KXMT submitted 2026-06-16 math.CO math.PR

Luisa Andreis , Mario Veshaj This is my paper · ORCID

classification math.COmath.PR

keywords multitypegraphsasymptoticenumerationconnectedsparselabelledgiantcomponentsedgematrix

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper derives the leading exponential growth rate for the number of labelled connected sparse multitype graphs that have a prescribed number of vertices of each type and a prescribed number of edges between each pair of types. It obtains this rate by showing that any such connected graph arises as the giant component of a suitably chosen larger random graph whose edge probabilities reproduce the given edge matrix. A reader would care because the same mapping supplies a concrete formula that extends the known single-type asymptotics to the multitype case while keeping the excess linear in graph size.

What carries the argument

The identification of a connected multitype graph as the giant component of a larger random graph whose connection kernel is chosen to match the observed edge matrix.

What would settle it

Direct enumeration of all connected multitype graphs on a few dozen vertices for fixed type profile and edge matrix, followed by comparison of the observed log-count growth rate against the rate predicted by the giant-component mapping.

Watch

Extended reading notes

Core claim

From large deviation asymptotics of connected components of inhomogeneous random graphs, we recognize that a connected graph with a given edge statistics corresponds to the (unique) giant component of larger inhomogeneous random graph with a suitably chosen connection kernel. This correspondence allows us to derive the leading exponential asymptotics for the number of connected multitype graphs with fixed type profile and edge matrix.

Load-bearing premise

The large-deviation principles and asymptotic estimates for connectedness probabilities that were previously established for inhomogeneous random graphs extend without modification to the multitype setting with exactly prescribed numbers of vertices per type and edges between each pair of types.

Editorial extensions

If this is right

The exponential asymptotics generalize the Bender-Canfield-McKay formula from ordinary sparse graphs to the multitype setting.
The growth rate is expressed in terms of the large-deviation rate function evaluated at the kernel that reproduces the given edge matrix.
The same probabilistic reduction applies to any enumeration problem whose objects can be realized as giant components of supercritical random graphs with linear excess.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The technique may apply to counting multitype graphs with additional local constraints if the corresponding large-deviation principle still holds.
It suggests a route to asymptotic counts for other labelled structures whose connectivity can be tied to component emergence in random models.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

read the letter

The main new piece is an explicit leading exponential formula for the number of labelled connected multitype graphs with fixed type counts and exact edge matrix between types. It generalizes the classical sparse connected-graph count by mapping the problem to the probability that a suitably tuned inhomogeneous random graph has a giant component whose edge statistics match the target matrix.

The probabilistic route is clean in outline and re-uses existing large-deviation machinery for inhomogeneous graphs, which is a reasonable way to handle the multitype case without reinventing enumeration from scratch.

The soft spot is exactly where the stress-test note flags it. The abstract says the large-deviation estimates extend without modification once the kernel is chosen to match the prescribed edge counts. In the sparse regime the conditioning on exact edge totals between every type pair is not obviously negligible for the rate function; the paper would need to show either that the difference is o(n) or that a conditioned LDP is available. No derivation steps or error-term control appear in the abstract, so the central claim is still sitting on that step.

The work is aimed at people who already care about asymptotic enumeration in random graphs and multitype models. A reader who wants the formula and is willing to accept the mapping on faith will get something usable; anyone who needs the technical justification will have to wait for the full details.

It is worth sending to referees. The idea is straightforward enough that a careful check of the conditioning argument should settle whether the leading term is correct.

Referee Report

2 major / 0 minor

Summary. The paper claims to derive the leading exponential asymptotics for the number of labelled connected sparse multitype graphs with prescribed type profile and edge matrix. It does so by establishing a correspondence between such a connected graph and the unique giant component of a larger inhomogeneous random graph whose connection kernel is tuned to match the prescribed edge counts, then invoking large-deviation principles and connectedness-probability estimates for inhomogeneous random graphs to obtain the asymptotics; the resulting formula is presented as a direct generalization of the Bender-Canfield-McKay enumeration for ordinary sparse connected graphs.

Significance. If the claimed correspondence and the requisite error controls can be made rigorous, the work would supply a probabilistic route to asymptotic enumeration in the multitype sparse regime that avoids direct combinatorial generating-function analysis, thereby extending a classical result to a broader setting where type-dependent edge statistics are prescribed.

major comments (2)

[Abstract (approach paragraph)] Abstract, paragraph beginning 'From large deviation asymptotics...': the central claim that the counting formula follows from the giant-component probability in a tuned IRG rests on the assertion that standard LDP results for inhomogeneous random graphs extend without modification to the exactly conditioned multitype setting. No derivation, citation, or error-term analysis is supplied showing that the conditioning on exact edge totals between every type pair changes the rate function by o(n) in the sparse regime (where excess is Θ(n)).
[Abstract] Abstract: the statement that 'a connected graph with a given edge statistics corresponds to the (unique) giant component of larger inhomogeneous random graph with a suitably chosen connection kernel' is presented without verification that the kernel tuning simultaneously enforces the exact prescribed edge matrix while preserving the leading exponential term for the connectedness probability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the specific comments on the abstract. We agree that the abstract is concise and will revise it to make the technical justifications more explicit while preserving its summary character. Below we respond point by point to the major comments.

read point-by-point responses

Referee: [Abstract (approach paragraph)] Abstract, paragraph beginning 'From large deviation asymptotics...': the central claim that the counting formula follows from the giant-component probability in a tuned IRG rests on the assertion that standard LDP results for inhomogeneous random graphs extend without modification to the exactly conditioned multitype setting. No derivation, citation, or error-term analysis is supplied showing that the conditioning on exact edge totals between every type pair changes the rate function by o(n) in the sparse regime (where excess is Θ(n)).

Authors: The abstract summarizes the overall strategy; the full large-deviation analysis for the exactly conditioned multitype setting, including the demonstration that the conditioning changes the rate function by at most o(n) via concentration of the edge counts around their means, appears in the body of the paper (Sections 3 and 4). To address the referee’s concern directly at the abstract level we will insert a short clause referencing the relevant LDP extension and the o(n) error control. revision: yes
Referee: [Abstract] Abstract: the statement that 'a connected graph with a given edge statistics corresponds to the (unique) giant component of larger inhomogeneous random graph with a suitably chosen connection kernel' is presented without verification that the kernel tuning simultaneously enforces the exact prescribed edge matrix while preserving the leading exponential term for the connectedness probability.

Authors: The kernel parameters are chosen to solve the fixed-point equations that make the expected edge counts between every pair of types coincide with the prescribed matrix; this system is solvable in the supercritical regime under the paper’s assumptions. The leading exponential term is preserved because the giant-component probability is a continuous functional of the kernel (via the branching-process survival probability) and the difference between the tuned kernel and the exact conditioning is absorbed into the o(n) error already controlled by the LDP. We will add one clarifying sentence to the abstract to record this verification explicitly. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: derivation maps to external LDP results for IRGs without internal reduction to inputs

full rationale

The paper derives leading exponential asymptotics for connected multitype graphs by recognizing a correspondence between a connected graph with fixed edge statistics and the giant component of a larger tuned IRG. This relies on large-deviation principles and connectedness estimates previously established for inhomogeneous random graphs, which the abstract states extend without modification to the multitype setting with prescribed type and edge counts. No self-definitional step, fitted parameter renamed as prediction, or load-bearing self-citation chain appears in the provided text; the central formula generalizes Bender-Canfield-McKay results via an external probabilistic correspondence rather than by construction from the counting inputs themselves. The derivation is therefore self-contained against external benchmarks.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

The derivation rests on large-deviation principles for inhomogeneous random graphs that are treated as established background; no new free parameters or invented entities are introduced in the abstract.

assumptions (1)

domain assumption Large-deviation principles and connectedness asymptotics hold for inhomogeneous random graphs with the required kernel tuning
Invoked to equate the counting problem with the giant-component probability.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Asymptotics of the number of labelled connected sparse multitype graphs." pith.science (2026). https://pith.science/paper/D7A2KXMT

@misc{pith2026260617912,
  author       = {Pith},
  title        = {Pith review of: Asymptotics of the number of labelled connected sparse multitype graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/D7A2KXMT}},
  note         = {Machine review of arXiv:2606.17912}
}

read the original abstract

We study the asymptotic enumeration of labelled connected multitype graphs in the sparse regime, where both the number of vertices and edges grow linearly and the excess is proportional to the size of the graph. Extending the classical theory of connected graph enumeration to the multitype setting, we consider graphs with prescribed numbers of vertices of each type and prescribed edge counts between each pair of types. Our approach is probabilistic and relies on the theory of inhomogeneous random graphs. In particular, we exploit large-deviation principles and asymptotic estimates for connectedness probabilities to relate the counting problem to the emergence of giant components in suitably tuned supercritical random graphs. From large deviation asymptotics of connected components of inhomogeneous random graphs, we recognize that a connected graph with a given edge statistics corresponds to the (unique) giant component of larger inhomogeneous random graph with a suitably chosen connection kernel. This correspondence allows us to derive the leading exponential asymptotics for the number of connected multitype graphs with fixed type profile and edge matrix. The resulting formula generalizes the asymptotic enumeration results of Bender, Canfield, and McKay for connected sparse graphs to the multitype framework. More broadly, the paper illustrates how probabilistic techniques can provide transparent and effective tools for addressing new combinatorial enumeration problems.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 3 canonical work pages

[1]

Alon and J

N. Alon and J. H. Spencer.The probabilistic method. John Wiley & Sons, 2016

2016
[2]

Andreis, W

L. Andreis, W. K¨ onig, H. Langhammer, and R. I. A. Patterson. A large-deviations principle for all the components in a sparse inhomogeneous random graph.Probability Theory and Related Fields, 186:521–620, 2023

2023
[3]

S. Bell, S. Donderwinkel, and R. van der Hofstad. The number and structure of connected graphs with a fixed degree sequence.arXiv preprint arXiv:2605.07923, 2026

work page Pith review arXiv 2026
[4]

E. A. Bender, E. R. Canfield, and B. D. McKay. The asymptotic number of labeled connected graphs with a given number of vertices and edges.Random Structures & Algorithms, 1(2):127–169, 1990

1990
[5]

Bernardi and A

O. Bernardi and A. H. Morales. Counting trees using symmetries.Journal of Combinatorial Theory, Series A, 123(1):104–122, 2014

2014
[6]

Bhamidi, A

S. Bhamidi, A. Budhiraja, and A. Sakanaveeti. Functional central limit theorems for microscopic and macroscopic functionals of inhomogeneous random graphs.arXiv preprint arXiv:2412.13672, 2024

work page arXiv 2024
[7]

Bhamidi, R

S. Bhamidi, R. van Der Hofstad, and J. S. Van Leeuwaarden. Novel scaling limits for critical inhomogeneous random graphs.The Annals of probability, pages 2299–2361, 2012

2012
[8]

Bollob´ as, S

B. Bollob´ as, S. Janson, and O. Riordan. The phase transition in inhomogeneous random graphs. Random Structures & Algorithms, 31(1):3–122, 2007

2007

Show all 18 references

[9]

Chakrabarty, R

A. Chakrabarty, R. S. Hazra, F. Den Hollander, and M. Sfragara. Spectra of adjacency and laplacian matrices of inhomogeneous erd˝ os–r´ enyi random graphs.Random matrices: Theory and applications, 10(01):2150009, 2021. 11

2021
[10]

Devroye and N

L. Devroye and N. Fraiman. Connectivity of inhomogeneous random graphs.Random Structures & Algorithms, 45(3):408–420, 2014

2014
[11]

L. R. Ford. Solution of a ranking problem from binary comparisons.The American Mathematical Monthly, 64(8P2):28–33, 1957

1957
[12]

Panafieu

´E. Panafieu. Analytic combinatorics of connected graphs.Random Structures & Algorithms, 55(2):427–495, 2019

2019
[13]

Pittel and N

B. Pittel and N. C. Wormald. Counting connected graphs inside-out.Journal of Combinatorial Theory, Series B, 93(2):127–172, 2005

2005
[14]

S¨ oderberg

B. S¨ oderberg. General formalism for inhomogeneous random graphs.Physical review E, 66(6):066121, 2002

2002
[15]

van der Hofstad.Random graphs and complex networks, volume 2

R. van der Hofstad.Random graphs and complex networks, volume 2. Cambridge university press, 2024

2024
[16]

van der Hofstad and J

R. van der Hofstad and J. Spencer. Counting connected graphs asymptotically.European J. Combin., 27(8):1294–1320, 2006

2006
[17]

Yu and W

R. Yu and W. Sun. On the moderate deviation principles in the sparse multi-type Erd˝ os R´ enyi random graph.arXiv preprint arXiv:2412.09471, 2024

2024
[18]

E. Zermelo. Die berechnung der turnier-ergebnisse als ein maximumproblem der wahrscheinlichkeit- srechnung.Mathematische Zeitschrift, 29(1):436–460, 1929. 12

1929

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.

[1] [1]

Alon and J

N. Alon and J. H. Spencer.The probabilistic method. John Wiley & Sons, 2016

2016

[2] [2]

Andreis, W

L. Andreis, W. K¨ onig, H. Langhammer, and R. I. A. Patterson. A large-deviations principle for all the components in a sparse inhomogeneous random graph.Probability Theory and Related Fields, 186:521–620, 2023

2023

[3] [3]

S. Bell, S. Donderwinkel, and R. van der Hofstad. The number and structure of connected graphs with a fixed degree sequence.arXiv preprint arXiv:2605.07923, 2026

work page Pith review arXiv 2026

[4] [4]

E. A. Bender, E. R. Canfield, and B. D. McKay. The asymptotic number of labeled connected graphs with a given number of vertices and edges.Random Structures & Algorithms, 1(2):127–169, 1990

1990

[5] [5]

Bernardi and A

O. Bernardi and A. H. Morales. Counting trees using symmetries.Journal of Combinatorial Theory, Series A, 123(1):104–122, 2014

2014

[6] [6]

Bhamidi, A

S. Bhamidi, A. Budhiraja, and A. Sakanaveeti. Functional central limit theorems for microscopic and macroscopic functionals of inhomogeneous random graphs.arXiv preprint arXiv:2412.13672, 2024

work page arXiv 2024

[7] [7]

Bhamidi, R

S. Bhamidi, R. van Der Hofstad, and J. S. Van Leeuwaarden. Novel scaling limits for critical inhomogeneous random graphs.The Annals of probability, pages 2299–2361, 2012

2012

[8] [8]

Bollob´ as, S

B. Bollob´ as, S. Janson, and O. Riordan. The phase transition in inhomogeneous random graphs. Random Structures & Algorithms, 31(1):3–122, 2007

2007