Combinatorics Seminar
When: Sunday, January 9, 10am
Where: Schreiber 309
Speaker: Sonny Ben-Shimon, Tel Aviv University
Title: Hamiltonicity questions in random graphs and
related problems (PhD defense talk)
Abstract:
A Hamilton cycle in a graph is a simple cycle that traverses all
vertices of the graph. The study whether a graph contains a
Hamilton
cycle, or the Hamiltonicity graph property, became one of the main
themes and most widely studied problem in Graph Theory. Deciding
whether a graph is Hamiltonian was one of the first problems that
were proved to be NP-Complete, giving some insight on its
elusiveness. Although the computational problem of determining in
"reasonable" time whether a graph is Hamiltonian seems hopeless,
the
road does not need to stop there, as there are many other natural
and
interesting questions about this property.
In this talk I will survey some recent results I obtained as part
of
my PhD thesis regarding the Hamiltonicity of a random graph.
First we will consider the Maker-Breaker game played on the edge
set
E as the board of the game. The game is a win for Maker if and
only
if the graph spanned by the edges selected by Maker throughout the
game contains a Hamilton cycle. We prove the following result:
with
high probability the random graph process is such that Maker
wins
the Hamiltonicity game exactly at the moment the minimum degree
becomes 4. This result, which improves on previous known results,
is
clearly optimal.
Next we consider the question of local resilience of a typical
random
graph with respect to the Hamiltonicity property. Given a
Hamiltonian
graph, one can "destroy" this property by removing all edges
incident
to a single vertex. But, how many edges must be removed if there
is a
uniform constraint on the number of allowed deletions of edges
incident to a vertex? We prove that for every \epsilon there is
C>0
such that if p(n)>C\ln n/n, then for the typical random graph in
the
G(n,p) model, if one allows at most (1/3-\epsilon)np edge
deletions
at each vertex, the resulting graph is Hamiltonian. This improves
the
best known bound in this range for the local resilience problem.
Finally, we also show how similar ideas can be applied to prove an
extension of the best known results for optimal packing of
edge-disjoint Hamilton cycles in a random graph.
Based on joint work with A. Ferber, D. Hefetz, M. Krivelevich and
B. Sudakov.