Asymptotic enumeration of linear hypergraphs with given number of vertices and edges

Brendan D. McKay; Fang Tian

REVIEW 1 major objections 3 minor 11 references

Asymptotic enumeration of linear hypergraphs with given number of vertices and edges

T0 review · 1 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read The paper proves an asymptotic formula for the number of linear r-uniform hypergraphs with a given number of edges, valid when m=o(r^{-3}n^{3/2}).

desk verdict First enumeration of linear hypergraphs by edge count; technically impressive, but the proof of Theorem 3.2(f) has a genuine gap that needs fixing. read the letter →

arxiv 1908.06333 v1 pith:IE2NQYYD submitted 2019-08-17 math.CO

Brendan D. McKay , Fang Tian This is my paper · ORCID

classification math.CO MSC 05C3005C6505C8005B05

keywords linearhypergraphspartialSteinersystemsswitchingmethodasymptoticenumerationrandomclusterclassificationsubhypergraphcontainmentfallingfactorials

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

This paper establishes the first asymptotic formula for the number of linear r-uniform hypergraphs on n labelled vertices with exactly m edges, in the range m=o($r^{{-3}}$$n^{{3/2}}$). The count is a binomial factor for all r-element edge sets times an exponential correction: the correction measures how a random r-graph fails to be linear, with the dominant terms coming from pairs and triples of edges that share too many vertices. The result matters because it turns a previously open enumeration problem into an explicit expression and, as a byproduct, gives the probability that the independent-edge random hypergraph H_r(n,p) is linear. The same switching machinery also yields the probability that a random linear hypergraph with m edges contains a given linear subhypergraph.

What carries the argument

The load-bearing mechanism is a combined switching argument on the set $\mathcal H^+_r(n,m)$ of r-graphs whose overlapping-edge clusters have one of four explicit shapes (three three-edge configurations and one two-edge configuration where the two edges share two vertices) and whose vertex degrees are at most $M_0$. Four switching operations remove one Type-1, Type-2, Type-3, or Type-4 cluster while leaving other cluster types unchanged; the ratio of the numbers of forward and reverse switchings between cluster-count classes is estimated using a bipartite-graph degree lemma, Lemma 3.6. Summing these ratios over all possible cluster counts, using summation lemmas developed in earlier sparse-enumeration work, produces the exponential factor in the theorem.

What would settle it

Enumerate $|\mathcal L_3(n,m)|$ exactly by computer for r=3 and increasing n, with m chosen just inside the allowed range, such as $m=\lfloor n^{4/3}\rfloor$, and check that the logarithm of the count divided by $\binom{N}{m}$ minus the predicted correction tends to zero at the stated rate. A deviation larger than the claimed $O(r^6m^2/n^3)$ error term would refute the theorem.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.1: for r(n)\ge 3 and m=o($r^{{-3}}$$n^{{3/2}}$), the number of linear r-uniform hypergraphs is $$|\mathcal L_r(n,m)|=\binom{N}{m}\exp\left(-\frac{[r]$_2^{2}$[m]_2}{$4n^{2}$}-\frac{[r]$_3^{2}$($3r^{2}$-15r+20)$m^{3}$}{$24n^{4}$}+O\left(\frac{$r^{6}$$m^{2}$}{$n^{3}$}\right)\right),$$ where $N=\binom{n}{r}$ and $[x]_t$ is the falling factorial. The proof works by computing the probability that a uniformly random r-graph with m edges is linear and showing it equals the exponential factor. This is achieved by restricting to r-graphs whose linked-edge clusters belong to four explicit types and whose degrees are bounded, showing all other r-graphs contribute only the stated error term, and then using switching operations to relate the numbers of r-graphs with different cluster counts.

Load-bearing premise

The proof assumes that nearly every r-graph with m edges lies in the restricted set $\mathcal H^+_r(n,m)$: all overlapping-edge configurations are among the four allowed cluster types and all vertex degrees are at most M0, with only $O(r^6m^2/n^3)$ exceptions. If the fraction of exceptional r-graphs were larger than this error term, the switching ratios would not sample the true configurations and the formula would fail.

Editorial extensions

If this is right

If Theorem 1.1 is correct, the number of linear r-uniform hypergraphs with m edges is now known asymptotically for all m up to o(r^{-3}n^{3/2}), a range that includes the sparse regime where most linear hypergraphs live.
The probability that a uniformly random r-graph with m edges is linear is exactly the exponential factor in the theorem, so the same formula gives the linearity probability for the uniform edge-count model.
For the independent-edge model H_r(n,p), Theorem 1.2 gives the asymptotic probability of linearity in terms of m_0=Np, with different corrections in the ranges m_0=O(r^{-2}n) and r^{-2}n\le m_0=o(r^{-3}n^{3/2}).
Corollary 1.3 says that, conditioned on being linear, the number of edges of H_r(n,p) is asymptotically normal with mean m_0 - [r]_2^2 m_0^2/(2n^2) and variance m_0.
Theorem 1.4 gives the probability that a random linear hypergraph with m edges contains a specified linear subhypergraph K with k edges, as $[m]_k/N^k$ times a small correction.

Reading between the lines

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

If the four-cluster classification and switching ratios extend to $\ell$-wise linear hypergraphs, or partial Steiner $(n,r,\ell)$-systems for $\ell\geq 3$, the same proof strategy could yield asymptotic counts for those families; the paper itself only treats $\ell=2$.
The error term $O(r^6m^2/n^3)$ suggests the formula may remain valid somewhat beyond the stated range; the maximum possible m for linear hypergraphs is $O(r^{-2}n^2)$, and probing the transition near $m=o(r^{-2}n^2)$ is a natural next step that the present method does not reach.
Theorem 1.4 can be iterated to estimate the number of linear hypergraphs containing a fixed collection of subhypergraphs, which would give a way to study subgraph statistics of random linear hypergraphs beyond containment of a single subhypergraph.

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, and a circularity audit.

Desk Editor's Note

read the letter

Good paper, with one genuine proof gap that the authors should be asked to fix.

The newness is real: no one had asymptotic enumeration of linear r-uniform hypergraphs by number of edges in this regime, and the switching construction combining four cluster types is a serious piece of work. The error terms are explicit and the self-contained derivation is refreshing—there are no fitted constants, and the applications to random hypergraph linearity and subhypergraph containment are natural.

The soft spot is in Theorem 3.2(f). The proof bounds the expected number of ℓ1 vertex-disjoint Type-1 clusters, then claims that under property (d) this controls the probability of having more than M1 Type-1 clusters. But property (d) only says the intersection graph of Type-1 clusters is a matching. If there are M1+1 clusters arranged as overlapping pairs, the largest vertex-disjoint collection is about (M1+1)/2, which is smaller than ℓ1. So the event C>M1 does not imply existence of ℓ1 vertex-disjoint clusters, and the expectation bound does not give the claimed probability. The same defect applies to the Type-2 and Type-3 cluster counting. Since Theorem 3.2 is the gate for the rest of the switching analysis, this is a real hole.

The rest of the paper reads carefully. I noticed a couple of typos (an extra n in (3.4), and an O(r^{-2}m) that should be O(r^{-2}n) in the proof of Theorem 1.1), but nothing else that worries me at this level. The summation lemmas from [8] are used appropriately, and I don't see circularity or fitted parameters.

Bottom line: the theorem may well be true, and the approach is promising, but the proof of the key concentration property is incomplete as written. This should go to a serious referee with a request to fix the cluster-counting argument—perhaps by bounding the total number of clusters directly rather than via vertex-disjoint sets. With that patched, I'd expect the paper to be a solid contribution.

Referee Report

1 major / 3 minor

Summary. The paper determines the asymptotic number of linear r-uniform hypergraphs on n vertices with m edges for m = o(r^{-3} n^{3/2}), proving an explicit formula for |L_r(n,m)|. The proof applies the switching method after showing that almost all r-graphs belong to a restricted class H^+ (and H^{++}) satisfying structural properties. The authors then analyze four types of switchings to compute the ratios between classes with different numbers of overlapping-edge clusters and use summation lemmas from previous work. Applications include the probability that a random hypergraph is linear and the probability that a random linear hypergraph contains a given subhypergraph.

Significance. If the proof is completed, this gives the first asymptotic enumeration of linear hypergraphs by number of edges, with an explicit error term. The method extends the switching approach for sparse matrices and graphs to hypergraphs and yields applications of independent interest. The paper is carefully structured, and the derivations are parameter-free, with the constants arising from combinatorial counts rather than fitted values.

major comments (1)

[Section 3, Theorem 3.2, property (f)] The proof that P[E_1] = 1 - O(r^6 m^2 / n^3) is incomplete. The authors bound the expected number of sets of l_1 vertex-disjoint Type-1 clusters and then assert that, assuming property (d), this implies the desired probability bound. However, property (d) only forces the intersection graph of Type-1 clusters to be a matching; a configuration with M_1+1 Type-1 clusters arranged in floor((M_1+1)/2) disjoint pairs sharing one vertex satisfies (d) and has no set of l_1 vertex-disjoint clusters when l_1 > ceil((M_1+1)/2). With the definitions in (3.1), l_1 = ceil(log(r^{-2}n) + 34 r^8 m^3/(4 n^4)) + 1 and M_1 = ceil(log(r^{-2}n) + 34 r^8 m^3/(2 n^4)), so l_1 is strictly larger than ceil((M_1+1)/2) for all sufficiently large log(r^{-2}n). Thus the event C > M_1 does not imply the existence of l_1 vertex-disjoint clusters, and the expectation estimate does not control the probability of violating (f). The same gap affects the analogous claims for Type-2 and Type-3 clusters. Since Theorem 3.2 is the structural gate through which every subsequent switching ratio passes, this leaves a gap in the proof of the main theorem. The issue appears repairable, for example by redefining the thresholds M_i so that M_i/2 >= l_i + O(1), but the required changes to the later error estimates are not supplied in the manuscript.

minor comments (3)

[Section 3, Eq. (3.4)] The first term on the right-hand side of the displayed estimate in (3.4) contains an extra factor n; the expression should read O(r^3(m-xi) log(r^{-2}n) + r^5(m-xi)^2/n) to be consistent with the final error term in Lemma 3.4.
[Proof of Theorem 1.1] In the sentence "when log(r^{-2}n) <= m = O(r^{-2}m)", the final m should be n; the intended condition is m = O(r^{-2}n).
[Proof of Lemma 6.6] In the final paragraph of the proof, the term O((2e/34)^{M_3}) should be O((2e/34)^{M_4}), since the summation is over h_4 up to M_4.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the final constants arise from direct switching counts and independent summation lemmas.

full rationale

The derivation of Theorem 1.1 is self-contained and does not fit any parameter or import the target formula. The paper reduces |L_r(n,m)| to binom(N,m) Pr(n,m), then computes Pr(n,m) by classifying forbidden configurations (Type-1..4 clusters) and performing direct switches (Sections 5-6). All constants in (1.1) are produced by combinatorial counts such as the ratios in Corollaries 5.4, 5.8, 5.12, 5.16, not by fitting. The thresholds M_i and M_i^* in (3.1) are proof devices whose 34r^... terms cancel into the quoted error O(r^6m^2/n^3). The summation lemmas 6.1 and 6.2 are cited from [8]; although McKay is a co-author, these are general recurrence-summation results whose assumptions do not include linear hypergraphs or the target count, so they are independent support under the review rules. Applications (Theorems 1.2 and 1.4) use Theorem 1.1 and standard binomial/total-probability estimates, not the desired conclusions. The skeptical concern about the proof of property (f) in Theorem 3.2 is a proof-technical gap (the implication from 'more than M1 clusters' to 'ell_1 vertex-disjoint clusters' is not immediate), not an input-output equivalence; no equation of the final formula is assumed in deriving it. Hence circularity score is 0.

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

No data are fitted and no entities are postulated. The proof imports standard analytic tools and two summation lemmas from [8]; auxiliary thresholds M_i with constant 34 are chosen to make error terms converge and cancel out of the final formula.

assumptions (4)

standard math Stirling's formula and the Chernoff bound for binomial tails are used in the proof of Theorem 1.2 (Section 9).
These are standard analytic tools imported without proof and used for binomial asymptotics in the random hypergraph application.
standard math Lemmas 6.1 and 6.2, imported from Greenhill, McKay and Wang [8], bound sums of recurrence ratios of the form n_i/n_{i-1}=A(i)(1-(i-1)B(i))/i.
These external summation results are stated in full and used to evaluate the sums over cluster counts in Section 6.
domain assumption For the assumed m range, r=o(n^{1/2}), so binomial ratios such as binom(n-2,t-2)/binom(n,t)=O(r^2/n^2) are valid.
This condition follows from m=o(r^{-3}n^{3/2}) and is used throughout the switching estimates; it is not an extra restriction on the theorem.
ad hoc to paper The constant 34 in (3.1) is sufficiently large that (2e/34)^{M_i}=O(r^6/n^3) for the thresholds M_i.
The value 34 is chosen by hand to make auxiliary error terms vanish. It cancels from the final asymptotic formula, so it is a proof device rather than a fitted parameter.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Asymptotic enumeration of linear hypergraphs with given number of vertices and edges." pith.science (2026). https://pith.science/paper/IE2NQYYD

@misc{pith2026190806333,
  author       = {Pith},
  title        = {Pith review of: Asymptotic enumeration of linear hypergraphs with given number of vertices and edges},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IE2NQYYD}},
  note         = {Machine review of arXiv:1908.06333}
}

abstract

For $n\geq 3$, let $r=r(n)\geq 3$ be an integer. A hypergraph is $r$-uniform if each edge is a set of $r$ vertices, and is said to be linear if two edges intersect in at most one vertex. In this paper, the number of linear $r$-uniform hypergraphs on $n\to\infty$ vertices is determined asymptotically when the number of edges is $m(n)=o(r^{-3}n^{ \frac32})$. As one application, we find the probability of linearity for the independent-edge model of random $r$-uniform hypergraph when the expected number of edges is $o(r^{-3}n^{ \frac32})$. We also find the probability that a random $r$-uniform linear hypergraph with a given number of edges contains a given subhypergraph.

Figures

Figures reproduced from arXiv: 1908.06333 by the authors.

**Figure 1.** The four types of clusters allowed in H ∈ H+ r (n, m). exactly one common vertex, then any other Type-1, Type-2 or Type-3 clusters of H must be vertex-disjoint from them.) (e) Any three distinct Type-4 clusters involve at least 6r − 8 vertices. (Together with (c), this implies that if a pair of Type-4 clusters of H have exactly one common vertex, then any other Type-4 cluster of H shares at most one vertex with them… view at source ↗

**Figure 2.** An example of a Type-1 switching between [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗

**Figure 3.** (2r − 2)-subset in the reverse Type-4 switching Firstly, by Lemma 3.4, there are n 2r − 2 − r 2 m n − 2 2r − 4 1 + O r 6mn log(r −2n) + r 8m2 n4 ways to choose a (2r − 2)-set T from [n] such that no two vertices belong to the same edge of H00. For every such T, there are 1 2 [PITH_FULL_IMAGE:figures/full_fig_p020_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

[8]

Greenhill, B

C. Greenhill, B. D. McKay and X. Wang, Asymptotic enumeration of sparse 0−1 matrices with irregular row and column sums. J. Comb. Theory A , 113 (2006), 291-324

work page 2006
[1]

A. S. Asratian and N. N. Kuzjurin, On the number of partial Steiner systems. J. Comb. Des., 81(5) (2000), 347-352. 41

work page 2000
[2]

On the number of linear hypergraphs of large girth

J. Balogh and L. Li, On the number of linear hypergraphs of large girth. arXiv:1709.04079

work page Pith review arXiv
[3]

Blinovsky and C

V. Blinovsky and C. Greenhill, Asymptotic enumeration of sparse uniform hypergraphs with given degrees. Eur. J. Combin. , 51 (2016), 287-296

work page 2016
[4]

Blinovsky and C

V. Blinovsky and C. Greenhill, Asymptotic enumeration of sparse uniform linear hyper- graphs with given degrees. Electron. J. Comb., 23(3) (2016), P3.17

work page 2016
[5]

Chernoﬀ, A measure of asymptotic eﬃciency for tests of a hypothesis bases on the sum of observations

H. Chernoﬀ, A measure of asymptotic eﬃciency for tests of a hypothesis bases on the sum of observations. Annals of Mathematical Statistics. , 23 (1952), 493-507

work page 1952
[6]

Dudek, A

A. Dudek, A. Frieze, A. Ruci´ nski and M. ˇSileikis, Approximate counting of regular hy- pergraphs. Inform. Process. Lett., 113 (2013), 785-788

work page 2013
[7]

D. A. Grable and K. T. Phelps, Random methods in design theory: a survey. J. Comb. Des., 4(4) (1996), 255-273

work page 1996

Show all 11 references

[9]

Greenhill and B

C. Greenhill and B. D. McKay, Asymptotic enumeration of sparse nonnegative integer matrices with speciﬁed row and column sums. Adv. Appl. Math. , 41 (2008), 459-481

2008
[10]

Greenhill and B

C. Greenhill and B. D. McKay, Asymptotic enumeration of sparse multigraphs with given degrees. SIAM J. Discrete Math. , 27 (2013), 2064-2089

2013
[11]

R¨ odl, On a packing and covering problem,Eur

V. R¨ odl, On a packing and covering problem,Eur. J. Combin. , 5 (1985), 69-78. 42

1985

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [8]

Greenhill, B

C. Greenhill, B. D. McKay and X. Wang, Asymptotic enumeration of sparse 0−1 matrices with irregular row and column sums. J. Comb. Theory A , 113 (2006), 291-324

work page 2006

[2] [1]

A. S. Asratian and N. N. Kuzjurin, On the number of partial Steiner systems. J. Comb. Des., 81(5) (2000), 347-352. 41

work page 2000

[3] [2]

On the number of linear hypergraphs of large girth

J. Balogh and L. Li, On the number of linear hypergraphs of large girth. arXiv:1709.04079

work page Pith review arXiv

[4] [3]

Blinovsky and C

V. Blinovsky and C. Greenhill, Asymptotic enumeration of sparse uniform hypergraphs with given degrees. Eur. J. Combin. , 51 (2016), 287-296

work page 2016

[5] [4]

Blinovsky and C

V. Blinovsky and C. Greenhill, Asymptotic enumeration of sparse uniform linear hyper- graphs with given degrees. Electron. J. Comb., 23(3) (2016), P3.17

work page 2016

[6] [5]

Chernoﬀ, A measure of asymptotic eﬃciency for tests of a hypothesis bases on the sum of observations

H. Chernoﬀ, A measure of asymptotic eﬃciency for tests of a hypothesis bases on the sum of observations. Annals of Mathematical Statistics. , 23 (1952), 493-507

work page 1952

[7] [6]

Dudek, A

A. Dudek, A. Frieze, A. Ruci´ nski and M. ˇSileikis, Approximate counting of regular hy- pergraphs. Inform. Process. Lett., 113 (2013), 785-788

work page 2013

[8] [7]

D. A. Grable and K. T. Phelps, Random methods in design theory: a survey. J. Comb. Des., 4(4) (1996), 255-273

work page 1996