@article{AMUC_2019_88_3_a30,
author = {Padraig Condon and Alberto Espuny D{\'\i}az and Ant\'onio Gir\~ao and Jaehoon Kim and Daniela K\"uhn and Deryk Osthus and Padraig Condon and Alberto Espuny D{\'\i}az and Ant\'onio Gir\~ao and Jaehoon Kim and Daniela K\"uhn and Deryk Osthus},
title = { Resilience with respect to {Hamiltonicity} in random graphs},
journal = {Acta mathematica Universitatis Comenianae},
pages = {547--551},
year = {2019},
volume = {88},
number = {3},
url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a30/}
}
TY - JOUR
AU - Padraig Condon
AU - Alberto Espuny Díaz
AU - António Girão
AU - Jaehoon Kim
AU - Daniela Kühn
AU - Deryk Osthus
AU - Padraig Condon
AU - Alberto Espuny Díaz
AU - António Girão
AU - Jaehoon Kim
AU - Daniela Kühn
AU - Deryk Osthus
TI - Resilience with respect to Hamiltonicity in random graphs
JO - Acta mathematica Universitatis Comenianae
PY - 2019
SP - 547
EP - 551
VL - 88
IS - 3
UR - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a30/
ID - AMUC_2019_88_3_a30
ER -
%0 Journal Article
%A Padraig Condon
%A Alberto Espuny Díaz
%A António Girão
%A Jaehoon Kim
%A Daniela Kühn
%A Deryk Osthus
%A Padraig Condon
%A Alberto Espuny Díaz
%A António Girão
%A Jaehoon Kim
%A Daniela Kühn
%A Deryk Osthus
%T Resilience with respect to Hamiltonicity in random graphs
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 547-551
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a30/
%F AMUC_2019_88_3_a30
The local resilience of a graph $G$ with respect to a property $\mathcal{P}$ measures how much one has to change $G$ locally in order to destroy $\mathcal{P}$. We prove 'resilience' versions of several classical results about Hamiltonicity for the graph models $G_{n,p}$ and $G_{n,d}$. In the setting of random regular graphs, we prove a resilience version of Dirac's theorem. More precisely, we show that, whenever $d$ is sufficiently large compared to $\varepsilon>0$, a.a.s. the following holds.Let $G'$ be any subgraph of the random $n$-vertex $d$-regular graph $G_{n,d}$ with minimum degree at least $(1/2+\varepsilon)d$.Then $G'$ is Hamiltonian.This proves a conjecture of Ben-Shimon, Krivelevich and Sudakov. For the binomial random graph $G_{n,p}$, we prove a resilience version of Pósa's Hamiltonicity condition, and show that a natural guess for a resilience version of Chvátal's theorem fails to be true.
