Abstract
Abstract. We prove a 'resilience' version of Dirac's theorem in the setting of random regular graphs. More precisely, we show that, whenever d is sufficiently large compared to ε > 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 + ε)d. Then G ′ is Hamiltonian. This proves a conjecture of Ben-Shimon, Krivelevich and Sudakov. Our result is best possible: firstly, the condition that d is large cannot be omitted, and secondly, the minimum degree bound cannot be improved.
Introduction
The study of Hamiltonicity has been at the core of graph theory for the past few decades. A graph G is said to be Hamiltonian if it contains a cycle which covers all of the vertices of G, and this is called a Hamilton cycle. It is well-known that the problem of determining whether a graph is Hamiltonian is NP-complete, and thus most results about Hamiltonicity deal with sufficient conditions which guarantee this property. One of the most well-known examples is due to Dirac, who proved that any graph G on n ≥ 3 vertices with minimum degree at least n/2 is Hamiltonian.
1.1.
Hamilton cycles in random graphs. The search for Hamilton cycles in various models of random graphs has also been a driving force in the development of this theory. The classical binomial model G n,p , in which each possible edge is added to an n-vertex graph with probability p independently of the other edges, has seen many results in this direction. In particular, Komlós and Szemerédi [23] showed that p = log n/n is the 'sharp' threshold for the existence of a Hamilton cycle. This can be strengthened to obtain the following hitting time result. Consider a random graph process as follows: given a set of n vertices, add each of the n 2 possible edges, one by one, by choosing the next edge uniformly at random among those that have not been added yet. In this setting, Ajtai, Komlós and Szemerédi [1] and Bollobás [10] independently proved that a.a.s. the resulting graph becomes Hamiltonian as soon as its minimum degree is at least 2.
The search for Hamilton cycles in other random graph models has proven more difficult. In this paper we will deal with random regular graphs: given n, d ∈ N such that d < n and nd is even, G n,d is chosen uniformly at random from the set of all d-regular graphs on n vertices. The study of this model is often more challenging than that of G n,p due to the fact that the presence and absence of edges in G n,d are correlated. Several different techniques have been developed to deal with this model, such as the configuration model (see Section 3.3) or edgeswitching techniques. Robinson and Wormald [33] proved that G n,3 is a.a.s. Hamiltonian, and later extended this result to G n,d for any fixed d ≥ 3 [34] . This is in contrast to G n,p , where the average degree must be logarithmic in n to ensure Hamiltonicity. These results were later generalised by Cooper, Frieze and Reed [14] and Krivelevich, Sudakov, Vu and Wormald [26] for the case when d is allowed to grow with n, up to d ≤ n − 1. Many further results can be found in the recent survey of Frieze [16] .
Local resilience.
More recently, several extremal results have been translated to random graphs via the concept of local resilience. The local resilience of a graph G with respect to some property P is the maximum number r ∈ N such that, for all H ⊆ G with ∆(H) < r, the graph G \ H satisfies P. We say that G is r-resilient with respect to a property P if the local resilience of G is greater than r. The systematic study of local resilience was initiated by Sudakov and Vu [36] , and the subject has seen a lot of research since.
Note that Dirac's theorem can be restated in this terminology to say that the local resilience of the complete graph K n with respect to Hamiltonicity is ⌊n/2⌋. This concept of local resilience then naturally suggests a generalisation of Dirac's theorem to random graphs. In the binomial model, Lee and Sudakov [27] showed that, for any constant ε > 0, if p ≥ C log n/n and C is sufficiently large, then a.a.s. G n,p is (1/2 − ε)np-resilient with respect to Hamiltonicity. This improved on earlier bounds [7, 8, 17, 36] . Very recently, Montgomery [30] and independently Nenadov, Steger and Trujić [32] , proved a hitting time result for the local resilience of G n,p with respect to Hamiltonicity. In a different direction, Condon, Espuny Díaz, Kim, Kühn and Osthus [12] considered 'resilient' versions of Pósa's theorem and Chvátal's theorem for G n,p .
The resilience of random regular graphs with respect to Hamiltonicity is less understood. Ben-Shimon, Krivelevich and Sudakov [7] proved that, for large (but constant) d, a.a.s. G n,d is (1 − ε)d/6-resilient with respect to Hamiltonicity. They conjectured that the true value should be closer to d/2. Conjecture 1.1 (Ben-Shimon, Krivelevich and Sudakov [7] ). For every ε > 0 there exists an integer D = D(ε) > 0 such that, for every fixed integer d > D, the local resilience of G n,d with respect to Hamiltonicity a.a.s. lies in the interval
They also suggested to study the same problem when d is allowed to grow with n. In this direction, Sudakov and Vu [36] showed that, for any fixed ε > 0, and for any (n, d, λ)-graph G (that is, a d-regular graph on n vertices whose second largest eigenvalue in absolute value is at most λ) with d/λ > log 2 n, we have that G is (1/2 − ε)d-resilient with respect to Hamiltonicity. This, together with a result of Krivelevich, Sudakov, Vu and Wormald [26] and recent results of Cook, Goldstein and Johnson [13] and Tikhomirov and Youssef [37] about the spectral gap of random regular graphs, implies that, for log 4 n ≪ d ≤ n − 1, a.a.s. G n,d is (1/2 − ε)d-resilient with respect to Hamiltonicity. One can extend this to d ≫ log n by combining a result of Kim and Vu [22] on joint distributions of binomial random graphs and random regular graphs with the result of Lee and Sudakov [27] about the resilience of G n,p with respect to Hamiltonicity.
The study of local resilience has not been restricted to Hamiltonicity. Other properties that have been considered include the containment of perfect matchings [12, 32] , directed Hamilton cycles [15, 18, 31] , cycles of all possible lengths [25] , k-th powers of cycles [35] , bounded degree trees [5] , triangle factors [6] , and bounded degree graphs [2, 20] .
1.3. New results. In this paper, we completely resolve Conjecture 1.1, as well as its extension to d growing slowly with n (recall that the case when d ≫ log n is covered by earlier results). This can be seen as a version of Dirac's theorem for random regular graphs. Our main result gives the lower bound in Conjecture 1.1. While we do not try to optimise the dependency of D on ε, we remark that D in Theorem 1.2 can be taken to be polynomial in ε −1 . This is essentially best possible in the sense that Theorem 1.2 fails if d ≤ (2ε) −1 . Our proof also shows that G n,d is not a.a.s. (d−1)/2-resilient with respect to the containment of a perfect matching. Moreover, one can adapt the proof of Theorem 1.3 to show that, for every even d, the random graph G n,d is not a.a.s. d/2-resilient with respect to Hamiltonicity (or the containment of a perfect matching). It would also be interesting to obtain bounds on the resilience for small d. In particular, here are some questions: i) Given any fixed even d, determine whether the graph G n,d is a.a.s. (d/2 − 1)-resilient with respect to Hamiltonicity. ii) What is the likely resilience of G n,4 with respect to Hamiltonicity or the containment of perfect matchings? Is a graph obtained from G n,4 by removing any matching a.a.s. Hamiltonian? Finally, we observe (as is well known) that the upper bound of (1/2 + ε)d in Conjecture 1.1 follows easily from edge distribution properties of random regular graphs. Indeed, we note that for every ε > 0 there exists a constant D such that for every D ≤ d ≤ log 2 n, a.a.s. the graph G = G n,d has the property that between any two disjoint sets A, B of size ⌊n/2⌋ and ⌈n/2⌉, respectively, the number of edges in G[A, B] is a.a.s. bounded from above by (1/2 + ε/2)nd/2 (see Proposition 4.4). Now let A, B be a maximum cut in G. Thus e G (a, B) ≥ d/2 for all a ∈ A, and similarly for all b ∈ B. If |A| = |B|, then by deleting the edges in
, the remaining graph is not Hamiltonian since it forms an unbalanced bipartite graph. If |A| = |B|, then by the above property, there must exist a vertex x ∈ A such that e G (x, B) ≤ (1/2 + ε/2)d. Let A ′ := A \ {x} and B ′ := B ∪ {x}. As before, by deleting the edges in
, we obtain a graph which is not Hamiltonian.
1.4.
Organisation of the paper. The remainder of the paper is organised as follows. In Section 2 we give a sketch of the proof of Theorem 1.2. In Section 3 we collect notation, some probabilistic tools, and observations about the configuration model. Section 4 is devoted to proving different edge-distribution and expansion properties of random regular graphs and their subgraphs, and the proof of Theorem 1.2 is given in Section 5, using all the techniques that have been introduced before. Finally, we prove Theorem 1.3 in Section 6.
2.
Outline of the proof of Theorem 1.2
We will prove that G ′ contains a 'sparse' spanning subgraph R which has strong edge expansion properties. These properties will then be used to provide a lower bound on the number of edges in G whose addition would make R Hamiltonian, or increase the length of a longest path in R (such edges are commonly called 'boosters', see e.g. [24] ). We then argue that some of these edges must in fact be retained when passing to G ′ . We then add such edges to R and iterate the above process (at most n times) until R becomes Hamiltonian.
More specifically, as a preliminary step we 'thin' the graph G ′ , that is, we take a subgraph R ⊆ G ′ with ∆(R) ≤ δd, for some δ ≪ ε. As described above, we consider a longest path in R and then argue that it can be extended via edges in G ′ \ R. The fact that R is relatively 'sparse' with respect to G ′ will be important when calculating union bounds over all graphs R of this type, at a later stage in the proof.
Given many paths of maximum length and with different endpoints in R, it follows that there will be many edges whose addition will increase the length of a longest path (or make R Hamiltonian). A theorem of Pósa implies that graphs with strong expansion properties will indeed contain many of such paths. These expansion properties are captured by the notion of a 3-expander (see Definition 4.1). Therefore, we wish to show that our thinned graph R can be chosen to be a 3-expander. This is one point where working with the random graph G n,d proves more difficult than working with G n,p , due to the fact that the appearance of edges in G n,d is correlated.
The next step is to provide a lower bound on the number of edges whose addition to R would increase the length of a longest path (or make R Hamiltonian). Here we further develop an approach of Montgomery [30] who, instead of considering single edges that would bring R closer to being Hamiltonian, considered 'booster' edge pairs whose addition would yield the same result. For example, if R is connected and P is a longest path in R with endpoints x and y, and ab is an edge of P (with b closer to y on P ), then {ya, xb} is a booster pair. The main advantage of considering such pairs of edges is that it results in a much larger set of boosters for R. More precisely, we show the existence of another thinned graph F ⊆ G ′ \ R for which each booster we consider is of the form {e, e ′ }, where e ∈ E(F ) and e ′ ∈ E(G ′ ) (see Corollary 5.6).
Finally, we can complete the proof of the main theorem by iteratively adding booster pairs to the thinned graph R, increasing the length of a maximum path in each step until R becomes Hamiltonian. Two points are important here as to why we can iterate this process. First, proving the existence of boosters (see Lemma 5.7) involves a union bound over all pairs of thinned graphs R and F. To bound this efficiently, we need that both R and F are relatively 'sparse' with respect to G ′ . But in each step we only add two booster edges to R, so it remains sparse. Secondly, we take special care to ensure that no vertex is contained in too many of the boosters we add to R, ensuring that its degree in successive iterations remains small. This process terminates after at most n iterations, resulting in a graph R ′ ⊆ G ′ which is Hamiltonian.
3. Preliminaries 3.1. Notation. For n ∈ N, we denote [n] := {1, . . . , n}. Given any set S, we denote S (2) := {{s 1 , s 2 } : s 1 , s 2 ∈ S, s 1 = s 2 }. The parameters which appear in hierarchies are chosen from right to left. That is, whenever we claim that a result holds for 0 < a ≪ b ≤ 1, we mean that there exists a non-decreasing function f : [0, 1) → [0, 1) such that the result holds for all a > 0 and all b ≤ 1 with a ≤ f (b). We will not compute these functions explicitly.
Throughout this paper, the word graph will refer to a simple, undirected graph. Whenever the graphs are allowed to have parallel edges or loops, we will refer to these as multigraphs. Given any (multi)graph G = (V, E) and sets A, B ⊆ V , we will denote the (multi)set of edges of G spanned by A as E G (A), and the (multi)set of edges of G having one endpoint in A and one endpoint in B as E G (A, B) . The number of such edges will be denoted by e G (A) and e G (A, B), respectively. We will also write e(G) for e G (V ). Given two (multi)graphs G 1 and G 2 on the same vertex set V , we write
, where the union represents set union for graphs and multiset union for multigraphs. When G 1 and G 2 are graphs, we write
. Given any vertex v ∈ V , we will denote the set of vertices which
is called graphic if there exists a graph on n vertices with degree sequence d (note that, as long as n i=1 d i is even, there is always a multigraph with degree sequence d). Given a graph G and a real number α > 0, let
We will use G n,d to denote the set of all d-regular graphs on vertex set [n], and G n,d will denote a graph chosen from G n,d james88@example.com. Whenever we use this notation, we implicitly assume that nd is even. In more generality, given a graphic degree sequence d = (d 1 , . . . , d n ), we will denote the collection of all graphs on vertex set [n] with degree sequence d by G n,d , and G n,d will denote a graph chosen from G n,d james88@example.com.
We use a.a.s. as an abbreviation for asymptotically almost surely. Given a sequence of events {E n } n∈N , whenever we claim that E n holds a.a.s., we mean that the probability that E n holds tends to 1 as n tends to infinity. For the purpose of clarity, we will ignore rounding issues when dealing with asymptotic statements. By abusing notation, given p ≥ 0 and n ∈ N, we write Bin(n, p) for the binomial distribution with parameters n and min{p, 1}.
Probabilistic tools. We will need the following Chernoff bound (see e.g. [21, Corollary 2.3]).
Lemma 3.1. Let X be the sum of n independent Bernoulli random variables and let µ :
The following bound will also be used repeatedly (see e.g. [3, Theorem A.1.12]).
Given any sequence of random variables X = (X 1 , . . . , X n ) taking values in a set A and a function f :
The sequence Y 0 , . . . , Y n is called the Doob martingale for f . All the martingales that appear in this paper will be of this form. To deal with them, we will need the following version of the well-known Azuma-Hoeffding inequality.
Lemma 3.3 (Azuma's inequality [4, 19] ). Let X 0 , X 1 , . . . be a martingale and suppose that
Finally, the Lóvasz local lemma will come in useful.
We will use the following version of the local lemma (it follows e.g. from [3, Lemma 5.
1.1]).
Lemma 3.4 (Lóvasz local lemma). Let E := {E 1 , E 2 , . . . , E m } be a collection of events and let H be a dependency graph for E.
3.3. The configuration model. We will work with the configuration model introduced by Bollobás [9] , which can be used to sample d-regular graphs james88@example.com. In more generality, it can be used to produce graphs with any given graphic degree sequence d. The process to generate such graphs is as follows. Given n ∈ N and a degree sequence
Choose uniformly at random a perfect matching M covering the expanded set of [n] . Then, obtain a multigraph ϕ(M ) = ([n], E) by letting E be the following multiset: for each edge e ∈ M , consider its endpoints e = x ij x kℓ , for some i, k
and add ik to E (if i = k, this adds a loop to E).
When we consider a multigraph G obtained via this configuration model, this will be denoted by G ∼ C n,d . In particular, when we obtain a d-regular multigraph via the configuration model, we will denote this by G ∼ C n,d . We refer to the possible perfect matchings on the expanded set of [n] as configurations, and we will denote a configuration obtained uniformly at random by M ∼ C * n,d . By abusing notation, we will sometimes also use C * n,d to denote the set of all configurations with parameters n and d. In order to easily distinguish the setting of graphs from that of configurations, we will call the elements of the expanded sets points, and each element in a configuration will be called a pairing.
The above process may produce a multigraph with loops and/or multiple edges. However, if d is a graphic degree sequence, then, when conditioning on the resulting multigraph being simple, the configuration model yields a graph G ∈ G n,d chosen james88@example.com. The following proposition bounds the probability that this happens, and can be proved similarly to (part of) a result of Cooper, Frieze and Reed [14, Lemma 7] (see [11] for details). It will be useful when analysing the distribution of edges in G n,d via the configuration model. 
Note that, by choosing R to be the empty graph on n vertices, we obtain a lower bound on the probability that the multigraph obtained by a random configuration is simple.
When studying the configuration model, it will be useful to consider the following process to 
uniformly at random and define M i := M i−1 ∪ {ij}. We sometimes refer to M i as the i-th partial configuration. Finally, let M := M m . It is clear that the resulting configuration M is generated uniformly at random, independently of the labelling of the expanded set of [n].
We will often be interested in bounding the number of edges in G n,d between two sets of vertices. For this, it will be useful to consider binomial random variables that stochastically dominate the number of edges. We formalise this via the following lemma.
Lemma 3.6. Let n, d ∈ N with d < n, and let δ ∈ [0, 1).
Proof. Let t := a∈A d a . Let X , A ′ and B ′ be the expanded sets of [n], A and B, respectively. Label the points of X so that all the points in A ′ come first, that is,
is the number of pairings in M with one endpoint in A ′ and the other in B ′ , and we will estimate the probability that each pairing added to M contributes to e G (A, B).
First, note that all pairings added after M t do not contribute to e G (A, B), as they do not have an endpoint in A ′ . For each i ∈ [t], define an indicator random variable X i which takes value 1 if M i = M i−1 and e = x i y ∈ M i \ M i−1 is such that y ∈ B ′ , and 0 otherwise, so that e G (A, B) = i∈[t] X i . Observe that, in the above process, the bound
holds for all i ∈ [t] since at every step of the process there are at most |B|d points available in B ′ and at least (1 − δ)nd − 2|A|d points available in X \ (V (M i−1 ) ∪ {x i }). On the other hand, In order to give bounds on the distribution of edges in G n,d we will use an edge-switching technique, first introduced by McKay and Wormald [29] . We will consider the following switching.
Definition 4.2. Let G = (V, E) and G ′ = (V, E ′ ) be two multigraphs on the same vertex set such that |E| = |E ′ |. We write
The following lemma bounds the probability that certain variables on configurations deviate from their expectation. 
We will now show that the differences of this martingale are bounded by c.
For
. Using this, it is easy to conclude that
The statement now follows by Lemma 3.3.
The following proposition implies that the distribution of edges in G n,d behaves roughly as in a binomial random graph G n,d/n , even after conditioning on the containment of some 'sparse' subgraph. and, for each a ∈ A, let Z a ⊆ [n] (2) \ E(R) be a collection of edges incident to a such that z := a∈A |Z a | satisfies z > εn 2 . Then,
. Therefore, we can apply Lemma 4.3 to obtain
By definition, the same bound holds for Z(F ). It now follows from Proposition 3.5 that
By a similar argument we can show that
The result follows by combining (4.1) and (4.2).
Lemma 4.5. For every 0 < δ < 10 −5 there exists D ∈ N such that for any D < d ≤ log 2 n we have that a.a.s. the random graph G n,d satisfies the following properties.
(i) For every S ⊆ [n] with δ 2 d ≤ |S| ≤ 5δ 2 n, we have e G n,d (S) ≤ δd|S|/25.
(ii) For every S ⊆ [n] with 5δ 2 n ≤ |S| ≤ n/100, we have e G n,d (S) ≤ d|S|/25.
such that δ 2 d ≤ |S| ≤ 5δ 2 n and any multigraph F on [n], let g(S, F ) be the event that e F (S) ≤ δd|S|/25. It follows by Lemma 3.6 that the variable e G (S) is stochastically dominated by Y ∼ Bin(d|S|, 5|S|/(4n)). We denote byP the probability measure associated with the configuration model and let P be the measure associated with the space of (simple) d-regular graphs. Therefore, by Lemma 3.2 we havê
It follows by Proposition 3.5 that
Thus, property (i) in the statement holds with probability 1 − o(1). Similarly, we can show that property (ii) also holds with probability 1 − o(1). Proposition 4.6. For every 0 < δ < 10 −5 there exists D ∈ N such that for any D < d ≤ log 2 n we have that a.a.s. the random graph G = G n,d satisfies the following properties.
(i) Let R ⊆ G be a spanning subgraph with δ(R) > δd. Then, for every S ⊆ [n] with |S| ≤ δ 2 n, we have
Proof. Let 1/D ≪ δ and condition on the statement of Lemma 4.5 holding, which occurs a.a.s. We first prove (i). For each S ⊆ [n] such that |S| < δ 2 d, the fact that every vertex has degree at least δd ensures that
In order to prove (ii), let S ⊆ [n] with δ 2 n ≤ |S| ≤ n/400. Suppose there exists S ′ ⊆ [n] with |S| ≤ |S ′ | ≤ 3|S| and such that e G (S, S ′ ) > d|S|/5. We have by Lemma 4.5 that
a contradiction. The result follows.
Proposition 4.7. For every 0 < δ < 10 −5 there exists D ∈ N such that for any D < d ≤ log 2 n we have that a.a.s. the random graph G = G n,d has the following property. Let H ∈ H 1/2 (G) and let G ′ := G \ H. Then, there exists a spanning graph R ⊆ G ′ such that ∆(R) < δd and, for every S ⊆ [n] with |S| ≤ n/400, we have that |N R (S)| ≥ 3|S|.
Proof. Let 1/D ≪ δ and letδ := δ/8. Condition on the event that the statements of Lemma 4.5 and Proposition 4.6 hold withδ playing the role of δ, which happens a.a.s. Suppose G satisfies these events and H ∈ H 1/2 (G), and let G ′ := G \ H. We now construct a suitable R for this G ′ . Consider a random subgraph R of G ′ where each edge is chosen independently and uniformly at random with probability 4δ. Consider the following events.
(G1) For all v ∈ [n] we haveδd < d R (v) < 8δd. (G2) For every S ⊆ [n] with |S| ≤ n/400, we have |N R (S)| ≥ 3|S|.
Note that, if both (G1) and (G2) hold, then R is a subgraph which satisfies the properties in the statement of the lemma.
For each v ∈ [n], let A v be the event that d R (v) / ∈ (δd, 8δd). By Lemma 3.1, we have
for all v ∈ [n]. Observe that G ′ is itself a dependency graph for {A v } v∈ [n] , and it has degree at most d. By Lemma 3.4, it follows that
Next, for S, S ′ ⊆ [n], let g(S, S ′ ) be the event that N R (S) ⊆ S ′ . Let (G3) be the event that for no pair of subsets S, S ′ ⊆ [n] with S ′ ⊆ N G ′ (S) andδ 2 n ≤ |S| ≤ |S ′ | ≤ 3|S| ≤ 3n/400 the event g(S, S ′ ) occurs. We have by Proposition 4.6(ii) and Lemma 4.5 that
Therefore, we have
A union bound implies that P[R fails to satisfy (G3)] ≤ 2 2n 2 −4n < 2 −n . Therefore, there exists an instance of R which satisfies both (G1) and (G3) simultaneously. Furthermore, since R satisfies (G1), it follows by Proposition 4.6(i) that for every S ⊆ [n] with |S| ≤δ 2 n we have that |N R (S)| ≥ 3|S|. Combining this with (G3) we see that R also satisfies (G2). Thus, R is a subgraph of the desired form.
Proposition 4.8. For every ε > 0 there exists D > 0 such that for any D < d ≤ log n 2 we have that a.a.s. the random graph G = G n,d has the following property. Let H ∈ H 1/2−ε (G) and let G ′ := G \ H. Let R ⊆ G ′ be a spanning graph such that for every S ⊆ [n] with |S| ≤ n/400, we have |N R (S)| ≥ 3|S|. Then, there exists a spanning 3-expander R ′ ⊆ G ′ with e(R ′ ) ≤ e(R)+400.
Proof. Let 1/D ≪ ε. We first note that a.a.s., for any A, B ⊆ [n] with |A| = n/400 and |B| = (1/2 − ε/10)n, we have a∈A e G (a, B) > (1/2 − ε/5)|A|d. Indeed, this follows by an application of Proposition 4.4 with R := ∅ and Z a being the star with centre a whose leaves are all the vertices in B \ {a}. We now claim that for any A ⊆ [n] with |A| ≥ n/400 we have that Finally, note that R consists of at most 400 components, since each connected component has order at least n/400. Since G ′ is connected, we may choose a set E ⊆ E(G ′ ) with |E| ≤ 400 such that the graph R ′ := ([n], E(R) ∪ E) is connected, and thus is a spanning 3-expander. Proof. Let 1/D ≪ δ, ε and condition on the statements of Propositions 4.7 and 4.8 both holding with δ/2 playing the role of δ, which happens a.a.s. By Proposition 4.7 we may find a spanning subgraph R ′ ⊆ G ′ with ∆(R ′ ) < δd/2 and such that, for all S ⊆ [n] with |S| ≤ n/400, we have |N R ′ (S)| ≥ 3|S|. Then, by Proposition 4.8 we may find a spanning 3-expander R ⊆ G ′ with ∆(R) < ∆(R ′ ) + 400 < δd.
Finding many boosters
The following proposition provides an upper bound on the expected number of 'thin' subgraphs that G n,d contains.
Proposition 5.1. Let 1/n ≪ 1/d, δ ≪ 1, where n, d ∈ N, and let G = G n,d . Let R be a family of graphs R on vertex set [n] with e(R) ≤ δdn for all R ∈ R. Then,
Proof. For each R ∈ R, let X R be an indicator random variable where X R (G) = 1 if and only if
Moreover, note that we always have
≤ e 2δdn log(1/δ) and, therefore,
The following result can easily be proved using "Pósa rotations" (see e.g. [24] ).
Lemma 5.2. Let R be a 3-expander and let P be a longest path in R, with endpoint v. Then, there exists a set A ⊆ V (P ) with |A| > n/10 4 such that for each a ∈ A there exists a path P a in R with endpoints v and a, and such that V (P a ) = V (P ).
Definition 5.3 (Booster)
. Let H be a graph and let E ⊆ V (H) (2) . Let F := (V (H), E). We call E a booster for H if the graph H + F contains a longer path that H does, or if H + F is Hamiltonian.
We will often be interested in the case where E consists of a single edge e / ∈ E(H). In this case we refer to e as a booster for H.
Given any path P with endpoints u and v, assume an orientation on its edges (say, from u to v). Given any vertex x ∈ V (P ) \ {v}, we call the vertex that follows x in this orientation its successor, and we denote this by suc P (x).
Lemma 5.4. For all 0 < ε < 1/10 5 there exist δ, D > 0 such that for D ≤ d ≤ log 2 n the random graph G = G n,d a.a.s. satisfies the following.
Let H ∈ H 1/2−ε (G) and let G ′ := G \ H. Let R ⊆ G ′ be a spanning 3-expander with ∆(R) ≤ 2δd, and let S ⊆ [n] with |S| ≤ δn. Then, there exists a set V R ⊆ [n] with |V R | ≥ n/10 4 with the following property: for each v ∈ V R , there exists a set U v ⊆ [n] with |U v | ≥ (1/2 + ε/8)n such that, for each u ∈ U v , there exists a set E v,u as follows:
Proof. Let 1/D ≪ δ ≪ ε < 1/10 5 . Let R be the set of all n-vertex 3-expander graphs R on [n] with ∆(R) ≤ 2δd. It follows by Lemma 5.2 that for each R ∈ R there exists a set V R ⊆ [n] of size |V R | ≥ n/10 4 such that for every v ∈ V R there exists a longest path in R terminating at v. For each R ∈ R, v ∈ V R and S ⊆ [n] with |S| ≤ δn, let f (R, S, v) be the event that, for every H ∈ H 1/2−ε (G) such that R ⊆ G ′ , there exists a set of vertices U v ⊆ [n] with |U v | ≥ (1/2+ε/8)n and such that for each u ∈ U v there exists a set E v,u satisfying (a)-(c). With this definition, the probability p * that the assertion in the lemma fails is bounded by
For fixed R ∈ R, v ∈ V R and S ⊆ [n] with |S| ≤ δn, we shall now estimate P[f (R, S, v) | R ⊆ G]. Let P be a longest path in R with endpoint v. As R is a 3-expander, by Lemma 5.2 there must exist a set A ⊆ V (P ) \ S of size |A| = εn/20 such that for each a ∈ A, there is a longest path P a in R starting at v and ending at a with V (P a ) = V (P ) (if there is more than one such path, fix one arbitrarily). Assume that each P a is oriented from v to a. Let B := [n] \ (A ∪ S ∪ {v}). For each u ∈ B ∩ V (P ), let X u := {ab : a ∈ A, b ∈ B, u = suc Pa (b)}. Observe that {uv, ab} is a booster for R for any ab ∈ X u . Clearly, |X u | ≤ |A| and X u ∩ X u ′ = ∅ for all distinct u, u ′ ∈ B ∩ V (P ). Furthermore, for each u ∈ B \ V (P ), let X u := {au : a ∈ A}. Note that au ∈ X u is a booster since its inclusion would result in a longer path in R. We shall now show that, for most vertices u ∈ B, there is a 'large' set of boosters, that is, X u is 'large'. We will then use this to show that many of these boosters must lie in G ′ \ R.
For every a ∈ A, there are at least |V (P )| − 2|A| − 2|S| − 2 vertices b ∈ V (P ) such that neither b nor its successor on P a belong to A ∪ S ∪ {v}. It follows that | u∈B∩V (P ) X u | ≥ |A|(|V (P )| − 2|A| − 2|S| − 2). We also have that | u∈B\V (P ) X u | = |A|(n − |V (P ) ∪ S|). Therefore, the following holds:
For each a ∈ A, let Z a be the set of edges in u∈B Y u with a as an endpoint. It is easy to see
Consider now the following events:
From two applications of Proposition 4.4 we obtain that P[
To finish the proof we must show that if F 1 ∧ F 2 holds, then f (R, S, v) also holds. Consider any G ∈ G n,d which satisfies both F 1 and F 2 and such that R ⊆ G. Fix any
As we have seen above, for each e ∈ E u , the set {uv, e} is a booster for R. Furthermore, none of the endvertices of e lies in S, by construction. Let U ⊆ B be the set of vertices u ∈ B for which |E u | ≥ 50/(εδ). Observe that, by
Hence, by F 2 we have that |U | ≥ (1/2 + ε/8)n, as we wanted to show. Since H was arbitrary, it follows that f (R, S, v) holds. Thus,
We can now use this bound in equation (5.1) to obtain
where the second inequality follows from Proposition 5.1. This shows the statement in the lemma holds a.a.s.
Definition 5.5. Given graphs H and
we say H has ε-many boosters with help from H ′ if there are at least ε|V | vertices v ∈ V for which there exists a set U v ⊆ V \ {v} of size at least (1/2 + ε)|V | with the property that for every u ∈ U v there exists e ∈ E(H ′ ) so that {uv, e} is a booster for H. We call uv the primary edge and we call e the secondary edge.
Corollary 5.6. For all 0 < ε < 1/10 5 there exist δ, D > 0 such that for D ≤ d ≤ log 2 n the random graph G = G n,d a.a.s. satisfies the following.
Let H ∈ H 1/2−ε (G) and let G ′ := G \ H. Let R ⊆ G ′ be a spanning 3-expander with ∆(R) ≤ 2δd, and let S ⊆ [n] with |S| ≤ δn. Then, there exists some subgraph F ⊆ G ′ \ R satisfying ∆(F ) ≤ 2δd, such that R has ε/16-many boosters with help from F , with the property that the set of secondary edges is vertex-disjoint from S. 
with |E v,u | ≥ 50/(εδ) and such that, for every e ∈ E v,u , {uv, e} is a booster for R, and such that E v,u 1 ∩ E v,u 2 = ∅ for all u 1 = u 2 . Note that each such edge e is vertex-disjoint from S, by construction.
Let F be a random subgraph of G ′ \ R where every edge in G ′ \ R is chosen independently at random with probability δ/2. For each v ∈ V R , let U ′ v ⊆ U v be the set of vertices u ∈ U v for which E v,u ∩ E(F ) = ∅. For every u ∈ U v , we have that
Let A be the event that |U ′ v | ≥ (1/2 + ε/16)n for every v ∈ V R . Since for different u ∈ U v the sets E v,u are disjoint, by Lemma 3.1 we have
for each v ∈ V R . Therefore,
for all v ∈ [n]. Now observe that G ′ \ R is itself a dependency graph for {B v } v∈ [n] , and every vertex in this graph has degree at most d. It follows by Lemma 3.4 that
Therefore, the probability both events A and B occur is strictly positive, implying that there exists some F ⊆ G ′ \ R satisfying the required properties.
We have now shown that a.a.s. if the random graph G n,d contains a sparse 3-expander subgraph R after deleting some H ∈ H 1/2−ε (G n,d ), then G ′ = G n,d \ H must also have a sparse subgraph F with the property that R has 'many' boosters with help from F . Our next goal is to prove that some primary edge of these boosters must actually be present in G ′ .
Lemma 5.7. For all 0 < ε < 1/10 5 there exist δ, D > 0 such that for D ≤ d ≤ log 2 n the random graph G = G n,d satisfies the following a.a.s. Let S ⊆ [n] with |S| ≤ δn and let R, F ⊆ G be two spanning edge-disjoint subgraphs such that (P1) ∆(R), ∆(F ) ≤ 2δd, (P2) R has ε-many boosters with help from F , such that every secondary edge is vertex-disjoint from S. Then, for any H ∈ H 1/2 (G), the graph G ′ := G\H contains an edge e for which there exists some edge e ′ ∈ E(F ) with the property that {e, e ′ } is a booster for R, and such that V ({e, e ′ })∩ S = ∅.
Proof. Let 1/D ≪ δ ≪ ε < 1/10 5 . Let P be the set of all triples (R, F, S) where R and F are edge-disjoint graphs on [n] which satisfy (P1) and (P2) and S ⊆ [n] with |S| ≤ δn.
Fix a triple (R, F, S) ∈ P. For every x ∈ [n], let V x be the set of vertices v ∈ [n] \ (S ∪ {x}) for which there exists some edge e ∈ E(F ) such that none of the endvertices of e lies in S and {xv, e} is a booster for R. Let X ′ := {x ∈ [n] : |V x | ≥ (1/2 + 3ε/4)n}. By assumption on the triple (R, F, S) and using Definition 5.5, we must have that |X ′ | ≥ εn.
Let X := X ′ \ S. Let f (R, F, S) be the event that x∈X e G\(R+F ) (x, V x ) ≥ (1 + ε)d|X|/2. It follows by Proposition 4.4 that
It follows that the probability that (R + F ⊆ G) ∧ f (R, F, S) for some triple (R, F, S) ∈ P is at most
where the second inequality follows by Proposition 5.1. We conclude that a.a.s. for all (R, F, S) ∈ P with R + F ⊆ G we have
Hence, there must exist some x ∈ X with e G\(R+F ) (x,
By the definition of V x , there is some e ∈ E(F ) such that {xv, e} is a booster for R. Furthermore, by construction, we have V ({xv, e}) ∩ S = ∅, and this completes the proof of the lemma.
Armed with the previous lemmas, we are now in a position to complete the proof of Theorem 1.2.
Proof of Theorem 1.2. Let 1/D ≪ δ ≪ ε < 1/10 5 be such that Corollary 5.6 holds for ε, Lemma 5.7 holds for ε/16 and Lemma 4.9 holds for ε. Condition on each of these holding.
Let H ∈ H 1/2−ε (G) and let G ′ := G \ H. By Lemma 4.9, there exists a subgraph R ⊆ G ′ which is a spanning 3-expander with ∆(R) ≤ δd.
Let R 0 := R. We now proceed recursively as follows: for each i ∈ [n], choose e i,1 , e i,2 ∈ E(G ′ ) such that {e i,1 , e i,2 } is a booster for R i−1 , and let R i := R i−1 + e i,1 + e i,2 . In order to show that there exist such e i,1 , e i,2 for all i ∈ [n], consider the following. Assume that
we have |S i | ≤ 2e(R i−1 \R 0 )/(δd−1) ≤ 4n/(δd−1) < δn. By applying Corollary 5.6 with S i , R i−1 playing the roles of S and R, respectively, there exists some subgraph F i ⊆ G ′ \ R i−1 such that R i−1 has (ε/16)-many boosters with help from F i , where each secondary edge is vertex-disjoint from S i . Furthermore, we have ∆(F i ) ≤ 2δd. Therefore, by applying Lemma 5.7, there are some e i,1 , e i,2 ∈ E(G ′ ) such that {e i,1 , e i,2 } is a booster for R i−1 and where V ({e i,1 , e i,2 }) ∩ S i = ∅. It follows that ∆(R i ) ≤ 2δd.
By the end of this process, we have added n boosters to R to obtain R n ⊆ G ′ . Therefore R n , and hence G ′ , is Hamiltonian.
Graphs of small degree with low resilience
In this section we prove Theorem 1.3. For this, we will require a crude bound on the number of edges spanned by any set of n/2 vertices in G n,d . To achieve this, we shall make use of the following result, which follows from a theorem of McKay [28] (see e.g. [38] ). We denote by α(G) the size of a maximum independent set in G. Proof. By Theorem 6.1, every set of size n/2 must span at least n/100 edges, as otherwise it would contain an independent set of size n/2 − n/50 > 0.46n.
Alternatively, this lemma can be proved directly using a switching argument. In order to prove Theorem 1.3 we will use a switching argument. Given a graph G ∈ G n,d and any integer ℓ ∈ [d], let u ∈ [n] and let Λ + u,ℓ = (e 1 , . . . , e ℓ , f 1 , . . . , f ℓ ) be an ordered set of 2ℓ edges from E(G) such that e i = uv i with v i = v j for all i = j, and {f i : i ∈ [ℓ]} is a set of independent edges such that, for each i ∈ [ℓ], the distance between f i and e i is at least 2. We call Λ satisfies that {e 1 , . . . , e D } = E M G (x, B G ) and {f 1 , . . . , f D } ⊆ E G (A G ). We say that any G ′ ∈ G n,d which can be obtained from G by such an x-switching of type D, is obtained by an outswitching from G, and we call Λ + x,D an out-switching configuration. Let Ω ′ denote the set of all graphs G ′ ∈ G n,d which can be obtained by out-switchings from some graph G ∈ Ω. In particular, note that for each G ′ obtained from G by an out-switching we may define A ′ := A G \ {x} and B ′ := [n] \ A ′ , so that |A ′ | < |B ′ |, e G ′ (u, B ′ ) > d/2 for all u ∈ A ′ , and e G ′ (v, A ′ ) > d/2 for all v ∈ B ′ , which means, as observed previously, that G ′ is not (d − 1)/2-resilient with respect to Hamiltonicity. Therefore, Ω ′ ⊆ (G n,d \Ĝ n,d ) ∪ G ′ n,d and Ω ∩ Ω ′ = ∅. To show that Ω ′ is large, we consider an auxiliary bipartite graph Γ with parts Ω and Ω ′ . We place an edge between G ∈ Ω and G ′ ∈ Ω ′ if G ′ is obtained from G by an out-switching. First, let G ∈ Ω. We will now provide a lower bound on the number of out-switchings from G. Since G ∈ Ω, by construction there are at least n/(2d) vertices x ∈ A G be such that d M G (x) = D. For each such x, the number of out-switching configurations is given by the different choices for the edges in (e 1 , . . . , e D , f 1 , . . . , f D ), chosen sequentially. There are D! choices for (e 1 , . . . , e D ). For all i ∈ [D], as each of the f i has to be independent from the previously chosen edges, at distance at least 2 from e i , and spanned by A G , by Lemma 6.2 we conclude that the number of choices for f i is at least n/100 − 4d 2 . Finally, once the out-switching configuration is given, there are Now consider any G ′ ∈ Ω ′ . It is easy to see that
Therefore, by double-counting the edges in Γ, from (6.1) and (6.2) we have that
It follows that there exists a constant p which does not depend on n for which a p fraction of the graphs inĜ n,d are not (d − 1)/2-resilient with respect to Hamiltonicity. The result follows.

{'paper_id': '119142201', 'title': "Dirac's theorem for random regular graphs", 's2_url': 'https://api.semanticscholar.org/CorpusID:119142201', 'source': 'S2ORC'}