On low-degree dependencies for sparse random graphs

Mehtaab Sawhney (MIT)

18-Aug-2022, 14:15-16:00 (19 months ago)

Abstract: Very sparse random graphs are known to typically be singular (i.e., have singular adjacency matrix), due to the presence of "low-degree dependencies" such as isolated vertices and pairs of degree-1 vertices with the same neighborhood. We prove that these kinds of dependencies are in some sense the only causes of singularity: for constants $k\geq 3$ and $\lambda>0$, an Erdős–Rényi random graph of $n$ vertices and edge probability $\lambda/n$ typically has the property that its $k$-core (largest subgraph with min-degree at least $k$) is nonsingular. This resolves a conjecture of Vu from the 2014 ICM, and adds to a short list of known nonsingularity theorems for "extremely sparse" random matrices with density $O(1/n)$. In subsequent work, we draw on related techniques to give a precise combinatorial characterization of the co-rank of the Erdős–Rényi random graph with density $\lambda/n$ coming from the Karp-Sipser core. A key aspect of our proof is a technique to extract high-degree vertices and use them to "boost" the rank, starting from approximate rank bounds obtainable from (non-quantitative) spectral convergence machinery due to Bordenave, Lelarge and Salez.

This talk is based on joint works with Asaf Ferber, Margalit Glasgow, Matthew Kwan, and Ashwin Sah.

computational geometrydiscrete mathematicscommutative algebracombinatorics

Audience: researchers in the topic


Copenhagen-Jerusalem Combinatorics Seminar

Series comments: There is a mailing list for talk announcements. If you want to receive the announcements, send an e-mail to the organizer to subscribe to the mailing list.

The password for the zoom room is 123456

Organizers: Karim Adiprasito, Arina Voorhaar*
*contact for this listing

Export talk to