Published on:

8 February 2024

Primary Category:

Combinatorics

Paper Authors:

Margalit Glasgow,

Matthew Kwan,

Ashwin Sah,

Mehtaab Sawhney

•

Proves a CLT for the matching number in sparse random graphs, strengthening a 1981 result of Karp & Sipser

•

New proof techniques handle degeneracies arising in subcritical and critical regimes

•

Also proves a CLT for the rank of the adjacency matrix of a sparse random graph

•

Techniques lead to a non-constructive characterization of fluctuations around the mean

Asymptotic normality of the matching number in sparse random graphs

This paper proves a central limit theorem for the matching number of sparse Erdős–Rényi random graphs. Specifically, it shows that the fluctuations in the matching number around its mean are asymptotically Gaussian, strengthening a 1981 law of large numbers result of Karp and Sipser. The new contribution is a proof handling certain degeneracies arising in the subcritical and critical regimes, via new non-constructive techniques.

Limit theorems for constrained Mittag-Leffler ensemble

Central limit theorem for random variables associated with the integrated density of states of th...

Central limit theorem for two-timescale stochastic algorithms

A more literal title describing the main contributions

Central limit theorem for periodic Lorentz gas free path length

Strong consistency of rank-constrained total least squares regression

No comments yet, be the first to start the conversation...

Sign up to comment on this paper