##### Department of Mathematics,

University of California San Diego

****************************

### Mathematics Colloquium

## Jacques Verstraete

#### McGill University

## Regular subgraphs of random graphs

##### Abstract:

The $k$-core of a graph is the largest subgraph of minimum degree at least $k$. In this talk, we will be discussing the appearance of $k$-regular subgraphs of random graphs in the $Erdos-R \acute e nyi$ model of random graphs. Pittel, Spencer and Wormald determined very precisely when the $k$-core of a random graph appears. The $k$-core of a graph is revealed by performing a greedy vertex-deletion algorithm, whereas no simple algorithm exists for finding $k$-regular subgraphs when $k > 2$. I will present a combination of algebraic, probabilistic and structural techniques which pin down the point of appearance of a $k$-regular subgraph in a random graph with edge-probability $p$ to a window for $p$ of width roughly $2/n$. To introduce these techniques, a more general discussion of degree constrained subgraphs will be given, including a proof of a recent conjecture on generalized factors of graphs. Recently published empirical evidence using statistical physical methods supports our conjecture of a sharp threshold for the appearance of $k$-regular subgraphs of random graphs, while this conjecture, nevertheless, remains open.

Host: Fan Chung Graham

### October 31, 2006

### 1:00 PM

### AP&M 6402

****************************