Asymptotic normality of the giant component size in a random bipartite graph

Dmitry Shabanov; Pavel Zakharov

REVIEW 3 major objections 3 minor 14 references

Asymptotic normality of the giant component size in a random bipartite graph

T0 review · 3 major / 3 minor · reviewed 2026-08-01 · 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 a central limit theorem for the giant component size in a sparse random bipartite graph, with fluctuations matching two independent one-sided giants.

desk verdict Clean result, honest provenance, but the coupling proof is sketched to the point that the paper's own argument does not establish the theorem. read the letter →

arxiv 2607.15789 v1 pith:ZC2ETIIC submitted 2026-07-17 math.CO

Dmitry Shabanov , Pavel Zakharov This is my paper · ORCID

classification math.CO MSC 05C8060F05

keywords randombipartitegraphgiantcomponentasymptoticnormalitycentrallimittheoremphasetransitionexplorationsparsegraphstwo-type

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 a central limit theorem for the size of the giant component in a random bipartite graph G(n,n,p), where np→c>1. Concretely, it proves that L1(n), the number of vertices in the largest component, satisfies √n(L1/n − 2β) → N(0, 2σ²), with β and σ² explicitly determined by c. The result matters because it upgrades the known law-of-large-numbers phase transition in the bipartite model to a precise fluctuation statement, and it shows the bipartite giant fluctuates exactly like two independent one-sided giants. The key coupling identifies the bipartite component, up to o_P(√n), with the sum of the largest components of two independent copies of the standard one-part random graph.

What carries the argument

The parallel component-exploration process, which maintains one queue of active vertices on each side of the bipartition and reveals edges only between the two sides, is the central object. The load-bearing identity is Lemma 2.1, L1(n)+ξ_n =d C^(1)(n)+C^(2)(n) with ξ_n/√n→0, which transfers a known central limit theorem for one-part random graphs to the bipartite model. The formulas for β and σ² arise from the branching-process phase transition and are inherited unchanged from the one-part model.

What would settle it

For a fixed c>1 (say c=2), generate many samples of G(n,n,p) with n large and compare the empirical distribution of √n(L1/n − 2β) with a normal of variance 2σ²; a statistically significant mismatch would refute Theorem 1.4. A sharper check is to test Proposition 2.6 directly: simulate both the bipartite graph and two independent one-sided graphs and compare L1 with C1+C2; the coupling predicts their normalized difference converges to 0 in probability.

Watch

Extended reading notes

Core claim

Theorem 1.4: if np→c>1, then √n(L1(n)/n − 2β) converges in distribution to a centered normal with variance 2σ², where β is the unique solution in (0,1) of β+e^{−βc}=1 and σ² = β(1−β)/(1−c(1−β))². The proof rests on a coupling: with a negligible error of order o_P(√n), the size of the giant component in G(n,n,p) has the same law as the sum of the giant components of two independent copies of the standard one-part random graph with the same edge probability.

Load-bearing premise

The load-bearing step is Proposition 2.6, which asserts that after an initial warm-up the parallel exploration of the bipartite graph is distributionally equivalent, to within o_P(√n), to exploring two independent one-sided random graphs; the extra O(n^{1/3}) active start vertices are argued to be negligible in a single sentence, and the whole transfer of the normal limit depends on that equivalence.

Editorial extensions

If this is right

The giant component of G(n,n,p) exhibits Gaussian fluctuations of order √n above the phase transition.
The asymptotic variance is exactly twice the one-sided random graph variance, so the bipartite giant behaves like the sum of two independent giants.
The law of large numbers L1/n→2β is strengthened to a full distributional limit.
The limiting parameters β and σ are the same functions of c as in the one-sided model, just doubled in center and variance.

Reading between the lines

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

A natural extension of the same two-sided coupling would give Gaussian fluctuations for the giant component in other two-type random graph models, such as balanced stochastic block models, where the variance would be the sum of the two community contributions.
The coupling strategy is specific to the supercritical regime; extending it to the critical window np−1 = O(n^{−1/3}) would require different rescaling and is left open.
The paper's own remark that a more general recent result implies the theorem indicates the bipartite normal law is not an isolated phenomenon; the value here is an earlier, self-contained proof tailored to the model.

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

Quick take: the theorem is very likely true and already known, and the authors are honest about that. Read it for the coupling strategy, not for a finished proof.

What's actually new: the paper offers a proof of asymptotic normality for the bipartite giant component size by coupling the exploration process with two independent Erdős–Rényi graphs. The strategy is elegant and plausible: run the explorations in parallel, show they match independent ER explorations up to o_P(√n) errors, then transfer Stepanov's CLT. The structure is clear, and Remark 1.5 explicitly acknowledges that the same result follows from Clancy's more general stochastic block model, noting that the Russian version of this paper appeared earlier. That is honest and earns credit.

Soft spots, in proportion:

1. Proposition 2.6 is the load-bearing coupling, and its proof is literally one sentence: the O(n^{1/3}) initial active sets are said not to change the limiting distribution because Stepanov's theorem holds for any np→c. That is not a proof. One must show that a perturbation of this size, propagated through the exploration, changes the stopping time and active-vertex count by o_P(√n). Plausible via contraction of the active-frontier ODE, but not demonstrated.

2. The final step of Lemma 2.1, where Y_n/(1−c(1−β)) is identified with |C1−C2|, is attributed to the proof of Proposition 2.5, but that proof nowhere states or proves it. It is a separate claim and it is simply missing.

3. Minor: Proposition 2.2's proof asserts that the conditional probability of starting the giant component is β(1+o(1)) regardless of the past, without argument. Probably fixable.

The theorem itself is externally supported by Clancy [13], so the main claim is almost certainly true. But this paper's own derivation does not establish it as written. The proof needs to be completed before the paper is rigorous.

Verdict: it deserves a serious referee, with the expectation of major revision. The result is worth having, and the coupling method, once fully written, could be a useful alternative path. I would not cite this as a proof yet; I would cite Clancy for the theorem.

Referee Report

3 major / 3 minor

Summary. The paper proves a central limit theorem for the size L_1(n) of the largest component of the sparse random bipartite graph G(n,n,p) when np→c>1: √n(L_1(n)/n − 2β) ⇒ N(0, 2σ²), with β and σ defined as in the Erdős–Rényi giant component. The proof strategy is to reduce the bipartite problem to the classical Stepanov CLT for G(n,p) by showing (Lemma 2.1) that L_1(n) is equal in distribution to C_1(n)+C_2(n)+o_P(√n), where C_1,C_2 are the largest component sizes of two independent Erdős–Rényi graphs. The argument uses a parallel exploration process on the two parts of the bipartite graph, introduces a stopping time τ_n when one side has no active vertices, and claims (Propositions 2.5 and 2.6) that the bipartite exploration is, up to o_P(√n) errors, the same as the simultaneous exploration of two independent G(n,p) graphs. The final theorem then follows from the classical CLT and the decomposition |C_1−C_2| + 2min(C_1,C_2) = C_1+C_2. The paper is written as a proof sketch: the key coupling statement and one residual identity are asserted rather than proved.

Significance. If fully established, Theorem 1.4 would be a clean extension of a classical result to the bipartite model, with the attractive feature of a coupling proof that reduces the bipartite CLT to the Erdős–Rényi one. The result itself is plausible and, as the authors note, also follows from the recent general stochastic block model CLT [13]; the present contribution is intended to provide a more elementary, self-contained route. That motivation is reasonable. The manuscript does not contain machine-checked proofs or code, and the theoretical argument is explicitly a sketch. The main claims are clearly stated and externally testable, but the proof as written leaves load-bearing steps in Propositions 2.5 and 2.6 without rigorous support.

major comments (3)

[§2.3, Prop. 2.6] The proof of Proposition 2.6 is a single sentence. It asserts that after t0 the parallel process is identical to the simultaneous exploration of two independent G(n,p), and that the O(n^{1/3}) extra starting active vertices do not change the limiting distribution because the CLT holds at the √n scale. This is not automatic: τ_n and Z_n are functionals of a stochastic process with √n fluctuations, so one must show that an n^{1/3} perturbation of the initial state changes these functionals by o_P(√n). The manuscript supplies no quantitative argument, e.g., via contraction of the deterministic active-frontier equations or a coupling that absorbs the extra vertices as additional seeds. This step is load-bearing for Lemma 2.1.
[§2.2, Lemma 2.1 proof] The final step of the proof of Lemma 2.1 states that 'from the proof of Proposition 2.5' the identity Y_n/(1−c(1−β)) = |C^(1)(n) − C^(2)(n)| + o_P(√n) follows. The proof of Proposition 2.5, however, contains no such statement; it only treats σ_n and Z_n in the bipartite process. The analogous relation for two independent Erdős–Rényi explorations—that the active-set size at the completion time of the smaller giant component is proportional to |C_1−C_2|—is a separate claim and is not proven. This identity is essential for converting the coupling into L_1(n)+ξ_n = C_1(n)+C_2(n).
[§2.3, Prop. 2.5] The proof writes σ_n = Σ_{j=1}^{Z_n} ξ_j(n), treating the subcritical explorations launched from distinct active vertices as disjoint. In a subcritical random graph, two such explorations can collide and merge; the expected number of collisions is O(Z_n^2 (log n)^2 / n), which is o_P(1) when Z_n = O_P(√n), but this estimate is not supplied. The asserted independence of Z_n and the ξ_j(n) also needs a careful conditional statement on the state at time τ_n. These omissions affect the derivation of Proposition 2.5 and hence of Lemma 2.1.

minor comments (3)

[§2.1, inline claim] The sentence 'Thus for t∈(t0,τ_n) our process looks like a parallel exploration of two random graphs G(n,p)' is stated before Proposition 2.6 and effectively duplicates it; a formal coupling is not given there.
[§2.3, Prop. 2.2] The phrase 'the conditional probability ... equals β(1+o(1)) regardless of the past' is imprecise; the uniformity of the o(1) error over the relevant events should be stated explicitly, although the conclusion is plausible.
[References] Reference [10] is a Master's thesis; if a published version exists, it would be preferable to cite it. Remark 1.5 could also be more precise about the overlap with [13].

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation reduces the bipartite CLT to the external Stepanov CLT; the cited self-priority remark is not load-bearing.

full rationale

The paper's main theorem is deduced from Lemma 2.1, which states that the bipartite giant component is, up to o_P(sqrt n), distributed as the sum of two independent Erdős–Rényi giant components. The subsequent appeal to Stepanov's theorem (Theorem 1.2) is an external, independently established result, not a restatement of the present paper's conclusion. Lemma 2.1 is then supported by the exploration-process coupling; Proposition 2.6 is the load-bearing step claiming that after time t_0 the bipartite process is distributionally close to two independent G(n,p) explorations. This is not an input fitted to the target output, nor a self-citation masquerading as proof. The only self-citation, [14], is used solely to assert priority in Remark 1.5 and does not carry the mathematical argument; reference [13] is an external more-general result and is not used as a premise. The one-sentence justification of Proposition 2.6 and the missing derivation of the residual identity for Y_n are genuine write-up gaps that could make the proof incomplete, but they are not instances of self-definition, fitted prediction, or self-citation chain. A proof gap is not the same as circularity under the stated criteria, so no circular step is identified.

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

The proof imports two prior theorems (Stepanov, Johansson) and relies on two ad hoc approximations about the exploration process that are sketched but not fully proved. No parameters are fitted to data, and no new entities are introduced.

assumptions (5)

domain assumption Stepanov's CLT for the giant component of G(n,p) (Theorem 1.2)
Used as the external limit theorem whose two independent copies give the target normal distribution after coupling.
domain assumption Johansson's law of large numbers for G(n,n,p) (Theorem 1.3)
Used in Propositions 2.2 and 2.5 to bound times and to assert subcritical components after τ_n.
domain assumption Each vertex belongs to the giant component with probability β(1+o(1))
Used in the proof of Proposition 2.2 to estimate the chance of starting the giant component.
ad hoc to paper The parallel exploration process from t0 is distributionally equivalent to two independent G(n,p) explorations (Prop 2.6)
Asserted rather than proved; the key coupling assumption.
ad hoc to paper After time τ_n, the remaining unexplored graph is subcritical with mean offspring c(1−β)<1, and the components are approximately independent (Prop 2.5)
Used to compute the mean residual σ_n.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Asymptotic normality of the giant component size in a random bipartite graph." pith.science (2026). https://pith.science/paper/ZC2ETIIC

@misc{pith2026260715789,
  author       = {Pith},
  title        = {Pith review of: Asymptotic normality of the giant component size in a random bipartite graph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZC2ETIIC}},
  note         = {Machine review of arXiv:2607.15789}
}

abstract

This paper studies the giant component of the sparse random bipartite graph $G(n, n, p)$, where $p = c/n$ for a fixed constant $c > 1$. We prove that its size is asymptotically normal.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 1 linked inside Pith

[13]

Clancy Jr.: A central limit theorem for the giant in a stochastic block model

D. Clancy Jr.: A central limit theorem for the giant in a stochastic block model. arXiv:2501.01351 (2025)

arXiv 2025
[1]

Erd˝ os, A

P . Erd˝ os, A. Rényi: On the Evolution of Random Graphs. Publication of the Mathematical Institute of the Hungarian Acad- emy of Sciences5(1960) 17–61

1960
[2]

Stepanov: On the Probability of Connectedness of a Random GraphGm(t)

V .E. Stepanov: On the Probability of Connectedness of a Random GraphGm(t). Theory Probab. Appl.15(1970) 55–67

1970
[3]

Bollobás, O

B. Bollobás, O. Riordan: Asymptotic normality of the size of the giant component via a random walk. Journal of Combina- torial Theory, Series B102(2012) 53–61

2012
[4]

Aldous: Brownian excursions, critical random graphs and the multiplicative coalescent

D. Aldous: Brownian excursions, critical random graphs and the multiplicative coalescent. The Annals of Probability25 (1997) 812–854

1997
[5]

Schmidt-Pruzan, E

J. Schmidt-Pruzan, E. Shamir: Component structures in the evolution of random hypergraphs. Combinatorica5(1985) 81–94

1985
[6]

Frieze, M

A. Frieze, M. Krivelevich, R. Martin: The emergence of a giant component in random subgraphs of pseudo-random graphs. Random Structures and Algorithms24(2004) 42–50

2004
[7]

Ajtai, J

M. Ajtai, J. Komlós, E. Szemerédi: Largest random component of ak-cube. Combinatorica2(1982) 1–7

1982

Show all 14 references

[8]

Behrisch, A

M. Behrisch, A. Coja-Oghlan, M. Kang: The order of the giant component of random hypergraphs. Random Structures and Algorithms36(2010) 149–184

2010
[9]

Bollobás, O

B. Bollobás, O. Riordan: Asymptotic Normality of the Size of the Giant Component in a Random Hypergraph. Random Structures and Algorithms41(2012) 441–450

2012
[10]

Johansson: The giant component of the random bipartite graph

T . Johansson: The giant component of the random bipartite graph. Master thesis in Engineering and Computational Sci- ence (2012). 7

2012
[11]

T .A. Do, J. Erde, M. Kang, M. Missethan: Component behaviour and excess of random bipartite graphs near the critical point. Electron. J. Comb.30 (3)(2023)

2023
[12]

Wang: Large random intersection graphs inside the critical window and triangle counts

M. Wang: Large random intersection graphs inside the critical window and triangle counts. Electron. J. Probab.30(2025) 1–63

2025
[14]

Zakharov, D

P . Zakharov, D. Shabanov: Asymptotic normality of the giant component size in a random bipartite graph. Trudy MIPT15 (2023) 23–32 (in Russian). DMITRYSHABANOV, LABORATORY OFCOMBINATORIAL ANDGEOMETRICSTRUCTURES, MOSCOWINSTITUTE OFPHYSICS AND TECHNOLOGY, RUSSIA PAVELZAKHAROV, D...

2023

Pith tools

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

[1] [13]

Clancy Jr.: A central limit theorem for the giant in a stochastic block model

D. Clancy Jr.: A central limit theorem for the giant in a stochastic block model. arXiv:2501.01351 (2025)

arXiv 2025

[2] [1]

Erd˝ os, A

P . Erd˝ os, A. Rényi: On the Evolution of Random Graphs. Publication of the Mathematical Institute of the Hungarian Acad- emy of Sciences5(1960) 17–61

1960

[3] [2]

Stepanov: On the Probability of Connectedness of a Random GraphGm(t)

V .E. Stepanov: On the Probability of Connectedness of a Random GraphGm(t). Theory Probab. Appl.15(1970) 55–67

1970

[4] [3]

Bollobás, O

B. Bollobás, O. Riordan: Asymptotic normality of the size of the giant component via a random walk. Journal of Combina- torial Theory, Series B102(2012) 53–61

2012

[5] [4]

Aldous: Brownian excursions, critical random graphs and the multiplicative coalescent

D. Aldous: Brownian excursions, critical random graphs and the multiplicative coalescent. The Annals of Probability25 (1997) 812–854

1997

[6] [5]

Schmidt-Pruzan, E

J. Schmidt-Pruzan, E. Shamir: Component structures in the evolution of random hypergraphs. Combinatorica5(1985) 81–94

1985

[7] [6]

Frieze, M

A. Frieze, M. Krivelevich, R. Martin: The emergence of a giant component in random subgraphs of pseudo-random graphs. Random Structures and Algorithms24(2004) 42–50

2004

[8] [7]

Ajtai, J

M. Ajtai, J. Komlós, E. Szemerédi: Largest random component of ak-cube. Combinatorica2(1982) 1–7

1982