Paper Image

Asymptotic normality of the matching number in sparse random graphs

Published on:

8 February 2024

Primary Category:

Combinatorics

Paper Authors:

Margalit Glasgow,

Matthew Kwan,

Ashwin Sah,

Mehtaab Sawhney

Bullets

Key Details

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

AI generated summary

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.

Answers from this paper

Comments

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

Sign up to comment on this paper

Sign Up