Combinatorics Seminar
Jacques Verstraete
UC San Diego and NSF
Full subgraphs
Abstract: Let $G=(V,E)$ be a graph of density $p$ on $n$ vertices. Following Erd\H{o}s, \L uczak and Spencer, an $m$-vertex subgraph $H$ of $G$ is called {\em full} if $H$ has minimum degree at least $p(m - 1)$. We determine for infinitely many $p$ the smallest possible order of a full subgraph of an $n$-vertex graph of density $p$ up to an absolute constant factor, answering a question of Erd\H{o}s, \L uczak and Spencer.
In contrast, we show that for any $n$-vertex graph $G$, either $G$ or $G^c$ contains a full subgraph on
$\Omega(\frac{n}{\log n})$ vertices, and we show this is tight up to a factor $O(\log\log n)$. Our proof furthermore gives a generalization of an old result of Erd{\H o}s and Pach on quasi-Ramsey numbers. Finally, we discuss full subgraphs of random and pseudo-random graphs, and several open problems.
Joint work with V. Falgas-Ravry and K. Markstr\”{o}m.
Monday October 10, 2016 at 2:00 PM in SEO 612