Induced subgraphs with prescribed degrees mod q

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).