Printable PDF
Department of Mathematics,
University of California San Diego

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

Math 269 - Combinatorics

Choongbum Lee

UCLA

Resilience of Random Graphs

Abstract:

Let $G$ be a graph having property $\mathcal{P}$. We ask the question, ``How strongly does $G$ possess $\mathcal{P}$?''. One way to answer this questions is by computing the number of edges one must delete from $G$ to obtain a graph not having property $\mathcal{P}$. We call this quantity the \textit{resilience} of $G$ with respect to having $\mathcal{P}$. Many classical results such as, Tur\'{a}n's Theorem, Dirac's Theorem and Bondy's Theorem can be understood in the context of resilience of a complete graph. Recently, Sudakov and Vu have initiated the systematic study of the resilience of random graphs by computing the resilience of it with respect to properties such as hamiltonicity, chromatic number, perfect matching and symmetry. Since then, several interesting results have been obtained by various researchers. We will first take a survey on the developments in this area by looking at these results and mentioning related open problems. Then we will discuss in more depth, the resilience of random graphs with respect to two specific properties, pancyclicity and containing an $H$-packing. (A graph $G$ is called pancyclic if it contains a cycle of all possible lengths. And for a fixed graph $H$, $G$ is said to have an $H$-packing if there exists vertex disjoint copies of $H$ covering all the vertices of $G$.) Joint work with Hao Huang, Michael Krivelevich, Wojceich Samotij, and Benny Sudakov

Host: Jozsef Balogh

April 6, 2010

2:00 PM

AP&M 7321

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