BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Mehtaab Sawhney (MIT)
DTSTART:20220818T141500Z
DTEND:20220818T160000Z
DTSTAMP:20260422T065511Z
UID:CJCS/77
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/CJCS/77/">On
  low-degree dependencies for sparse random graphs</a>\nby Mehtaab Sawhney 
 (MIT) as part of Copenhagen-Jerusalem Combinatorics Seminar\n\n\nAbstract\
 nVery sparse random graphs are known to typically be singular (i.e.\, have
  singular adjacency matrix)\, due to the presence of "low-degree dependenc
 ies" such as isolated vertices and pairs of degree-1 vertices with the sam
 e neighborhood. We prove that these kinds of dependencies are in some sens
 e 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 combina
 torial 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 t
 o "boost" the rank\, starting from approximate rank bounds obtainable from
  (non-quantitative) spectral convergence machinery due to Bordenave\, Lela
 rge and Salez.\n\nThis talk is based on joint works with Asaf Ferber\, Mar
 galit Glasgow\, Matthew Kwan\, and Ashwin Sah.\n
LOCATION:https://researchseminars.org/talk/CJCS/77/
END:VEVENT
END:VCALENDAR