Combinatorics Seminar
When: Sunday, October 31, 10am
Where: Schreiber 309
Speaker: Wojciech Samotij, Tel Aviv University
Title: Resilience of random graphs
Abstract:
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.