[theory-seminar] Theory Lunch 03/18: Margalit Glasgow

[David Wajc]

Hi all,

This week's theory lunch will take place Thursday at noon (PDT), at our
gather space:
https://gather.town/app/lR6jRBPK44nZ7V68/StanfordTheory (*password:*
 SongComplexity).
Margalit will tell us about*:* *Invertibility of 3-core of Erdos-Reyni
Graphs*

*Abstract**: *
In this talk, I'll show that in ER graphs with average degree d = omega(1),
with probability 1 - o(1), the adjacency matrix of the 3-core of the graph
has full rank. The key idea is a tight characterization of the
combinatorial structures that cause linear dependencies in sparse random
matrices. This proves a weakened version of a conjecture from Vu, 2014,
which speculates that with high probability, the 3-core of a ER random
graph is invertible for any average degree d > 1.

Cheers,
David

PS
*Pro tip:* To join the talk (at 12:30):
(1) go to the lecture hall,
(2) grab a seat, and
(3)* press X to join the zoom lecture*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20210315/a96ae28d/attachment-0001.html>