## EE Student Information

### The Department of Electrical Engineering supports Black Lives Matter. Read more.

• • • • •

EE Student Information, Spring Quarter through Academic Year 2020-2021: 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).