Printable PDF
Department of Mathematics,
Department of Mathematics,
University of California San Diego
****************************
Math 269 - Combinatorics
Prof. Michael Molloy
University of Toronto
k-regular subgraphs near the k-core threshold of a random graph
Abstract:
We prove that $G_{n,p=c/n}$ whp has a $k$-regular subgraph if $c$ is at least $e^{-\Theta(k)}$ above the threshold for the appearance of a subgraph with minimum degree at least $k$; i.e. an non-empty $k$-core. In particular, this pins down the threshold for the appearance of a $k$-regular subgraph to a window of size $e^{-\Theta(k)}$.
This is a joint work with Dieter Mitsche and Pawel Pralat; see arXiv:1804.04173
February 6, 2024
2:00 PM
APM 7321
Research Areas
Combinatorics****************************
