EE Student Information

EE Student Information, Spring Quarter 19-20: FAQs and Updated EE Course List.

Updates will be posted on this page, as well as emailed to the EE student mail list.

Please see Stanford University Health Alerts for course and travel updates.

As always, use your best judgement and consider your own and others' well-being at all times.

Probability Seminar presents "Induced subgraphs with prescribed degrees mod q"

Topic: 
Induced subgraphs with prescribed degrees mod q
Monday, May 18, 2020 - 4:00pm
Venue: 
Zoom ID: 917 2019 2125 (meeting locked 10 min. after start)
Speaker: 
Asaf Ferber (UC Irvine)
Abstract / Description: 

A classical result of Galai asserts that the vertex-set of every graph can be partitioned into two sets such that each induces a graph with all degrees even. Scott studied the (harder) problem of determining for which graphs can we find a partition into arbitrary many parts, each of which induces a graph with all odd degrees. In this talk we discuss various extensions of this problem to arbitrary residues mod $q\geq 3$. Among other results, we show that for every $q$, a typical graph $G(n,1/2)$ can be equi-partitioned (up to divisibility conditions) into $q+1$ sets, each of which spans a graph with a prescribed degree sequence.

A completely unrelated problem: Based on the same approach we obtained a non-trivial bound (but weaker than known results) on the singularity probability of a random symmetric Bernoulli matrix. The new argument avoids both decoupling and distance from random hyperplanes and it turns this problem into a simple and elegant exercise.

This is mostly based on a joint work with Liam Hardiman (UCI) and Michael Krivelevich (Tel Aviv University).