Combinatorics Seminar

When: Sunday, October 31, 10am
Where: Schreiber 309
Speaker: Wojciech Samotij, Tel Aviv University
Title: Resilience of random graphs


Let P be a graph property and let G be a graph having P. One can ask the question, "How strongly does G posses P?" A natural way to interpret and answer this question is to compute the minimum number of edges one has to delete from G (or at some vertex of G) in order to destroy P. We call this quantity the resilience of G with respect to the property P.

Since many classical results in extremal graph theory, such as the famous theorems of Turan and Dirac, can be stated using the resilience terminology, one might say that the concept of resilience has been (implicitly) present in the literature for more than 50 years. Nevertheless, only recently it has been given a more systematic treatment. Three years ago, Sudakov and Vu initiated a systematic study of resilience of random graphs with respect to various graph properties. Since then, several interesting results have been obtained by various researchers.

In this talk, we will first survey some of the recent developments in the area. Then, we will discuss in more depth the resilience of random graphs with respect to two particular graph properties - pancyclicity and the property of containing all almost spanning trees with bounded degree.

The last part of the talk is based on joint work with Jozsef Balogh, Bela Csaba, and Choongbum Lee.