Induced subgraphs with prescribed degrees mod q

Abstract: 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. Switching to a completely unrelated problem: based on idea of the main key lemma of the above results, we give 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. The first part of the talk is based on a joint work with Liam Hardiman (UCI) and Michael Krivelevich (Tel Aviv University).

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).