Combinatorics Seminar
When: Sunday, May 31, 10am
Where: Schreiber 309
Speaker: Sonny Ben-Shimon, Tel Aviv U.
Title:
On the local resilience of random regular graphs
Abstract:
For a graph property P, the global resilience of a graph G with respect
to P is the minimal number of additions and removals of edges from G such
that the resulting graph does not posses P. For some graph properties
this quantity does not seem to convey what one would expect from such
a notion of ``distance''. For example, if P represents Hamiltonicity,
then the global resilience of any graph G with respect to P is at most
delta(G), as it is clear that the removal of all edges incident to
some vertex will create a non-Hamiltonian graph. Consider now the local
resilience of a graph G with respect to P, where there is an additional
constraint of a bounded number of editions done on edges incident to
a single vertex. This notion, which was implicitly studied for some
ad-hoc properties, was recently treated in a more systematic way in a
paper by Sudakov and Vu. Most research conducted with respect to local
resilience was focused on the random graph G(n,p) and some families of
pseudo-random graphs with respect to several graph properties such as
containing a perfect matching, containing long cycles (i.e. linear in the
number of vertices), and being Hamiltonian. In this talk we continue to
explore the local resilience notion, but turn our attention to random and
pseudo-random regular graphs of constant degree. In particular we focus
on the local resilience with respect to edge and vertex connectivity,
containing a perfect matching, and being Hamiltonian (with a slight
detour back to the G(n,p) case).
Joint work with M. Krivelevich and B. Sudakov.