PaperlayerView exact revision on arXiv

Source-linked AI summary

Hamilton decompositions of regular expanders: a proof of Kelly's conjecture for large tournaments

Daniela Kühn, Deryk Osthus

arXiv:1202.6219v2math.COcs.DM

TL;DR

Kelly’s conjecture asks whether every regular tournament can be decomposed into edge-disjoint Hamilton cycles, a question with little progress for general graph classes. The paper proves a broader decomposition theorem for regular robust outexpanders, confirming the conjecture for large tournaments and deriving a packing result for almost all tournaments.

  • Problem

    Kelly’s conjecture asks whether every regular tournament has a Hamilton decomposition, while little progress had been made on such decompositions for general graph classes.

    Source: §1.1 · p. 1

  • Method

    The paper proves a Hamilton-decomposition theorem for sufficiently large regular digraphs of linear degree that are robust outexpanders.

    Source: §1.2 · p. 3

  • Results

    Every sufficiently large regular digraph with r ≥ αn that is a robust (ν, τ)-outexpander has a Hamilton decomposition, computable in polynomial time.

    Source: §1.2 · p. 3

  • Takeaways & Limitations

    Almost all tournaments contain δ0(G) = min{δ+(G), δ−(G)} edge-disjoint Hamilton cycles.

    Source: §1.3.2 · pp. 4–5

    Whether the lower bound on r in the oriented-graph theorem is best possible remains unclear.

    Source: §1.1 · p. 2

Abstract

from arXiv · show

A long-standing conjecture of Kelly states that every regular tournament on n vertices can be decomposed into (n-1)/2 edge-disjoint Hamilton cycles. We prove this conjecture for large n. In fact, we prove a far more general result, based on our recent concept of robust expansion and a new method for decomposing graphs. We show that every sufficiently large regular digraph G on n vertices whose degree is linear in n and which is a robust outexpander has a decomposition into edge-disjoint Hamilton cycles. This enables us to obtain numerous further results, e.g. as a special case we confirm a conjecture of Erdos on packing Hamilton cycles in random tournaments. As corollaries to the main result, we also obtain several results on packing Hamilton cycles in undirected graphs, giving e.g. the best known result on a conjecture of Nash-Williams. We also apply our result to solve a problem on the domination ratio of the Asymmetric Travelling Salesman problem, which was raised e.g. by Glover and Punnen as well as Alon, Gutin and Krivelevich.

1. Introduction

The paper proves Kelly’s conjecture for large regular tournaments through a broader Hamilton-decomposition theorem for regular robust outexpanders. It also derives applications to dense regular digraphs, random tournaments, undirected graphs, and graph decomposition problems.

1. Introduction.

  • The decomposition theorem advances the study of Hamilton decompositions, a classical problem exemplified by Walecki’s result for complete graphs of odd order.Tillson solved the corresponding complete-digraph problem, with exceptions at orders 4 and 6.Source: §1.1 · p. 1

1.1. Kelly’s conjecture.

  • For r-regular oriented graphs with r ≥ 3n/8 + εn, the theorem gives a Hamilton decomposition, confirming Kelly’s conjecture for large regular tournaments.For even-order tournaments that are as regular as possible, adding a vertex yields a regular tournament whose decomposition gives edge-disjoint Hamilton paths in the original graph.Source: §1.1 · p. 2

1.2. Robust outexpanders.

  • Every sufficiently large regular digraph of linear degree that is a robust outexpander has a Hamilton decomposition, and the decomposition is computable in polynomial time.Robust expansion requires every set S with τn ≤ |S| ≤ (1−τ)n to have a robust outneighbourhood at least |S|+νn.Source: §1.2 · p. 3

1.3. Further applications.

  • Every sufficiently large r-regular digraph with r ≥ (1/2 + ε)n has a Hamilton decomposition that can be found in polynomial time.The paper also connects this result to an ATSP algorithm with domination ratio 1/2 − ε.Source: §1.3.1 · p. 4

1.3.1. Regular digraphs and TSP tour domination.

  • A polynomial-time ATSP algorithm achieves domination ratio 1/2 − ε, addressing a longstanding open problem on constant domination ratios.The motivating problem was whether a polynomial-time algorithm could achieve a constant domination ratio.Source: §1.3.1 · p. 4

1.3.2. Random tournaments.

  • Almost all tournaments contain δ0(G) = min{δ+(G), δ−(G)} edge-disjoint Hamilton cycles.The proof finds a spanning δ0(G)-regular subdigraph with high probability and applies the tournament decomposition result.Source: §1.3.2 · pp. 4–5

1.3.3. Undirected robust expanders.

  • Every sufficiently large even-regular graph with r ≥ (1/2 + ε)n has a Hamilton decomposition, an approximate form of Nash-Williams’s conjecture.The undirected results also imply decompositions for even-regular dense quasi-random graphs, large Paley graphs, and dense random regular graphs with high probability.Source: §1.3.3 · p. 5

1.3.4. The robust decomposition lemma.

  • The paper’s decomposition methods support later results proving the 1-factorization conjecture and solving Nash-Williams’s Hamilton-decomposition conjecture.The robust decomposition lemma also yields optimal packings of edge-disjoint Hamilton cycles in graphs of large minimum degree.Source: §1.3.4 · pp. 5–6

2. A brief outline of the argument

The proof builds a robustly decomposable subgraph in stages, using successive leftovers to gain structure until the remaining edges can be decomposed into Hamilton cycles. Regularity and three absorber constructions handle the cycle-building process, chord balancing, exceptional vertices, and the final switches.

2.1. The general approach.

  • The proof iteratively combines sparse robustly decomposable subgraphs with increasingly structured leftovers, ending when their union admits a Hamilton decomposition.The robust decomposition lemma packages this process: after an approximate decomposition, the final leftover is combined with the robust subgraph to decompose the original digraph.Source: §2.1 · p. 6
  • To absorb a leftover, the proof splits it into 1-factors, breaks those into small path systems, and extends them into suitable 1-factors using robust-subgraph edges.The resulting cycles cover the previous leftover, leaving a new leftover inside the robust subgraph.Source: §2.1 · pp. 6–7
  • A regularity partition yields a reduced digraph that remains a robust outexpander and therefore contains a Hamilton cycle through the clusters.The clusters along this cycle provide the structure for constructing the robust subgraphs used in the proof.Source: §2.2 · p. 7, §2.1 · p. 7

2.2. The main steps.

  • The preprocessing graph leaves a leftover with no edges incident to the exceptional set; exceptional edges later represent paths through those vertices.The chord absorber compensates for the degree irregularity created by this preprocessing.Source: §2.2 · pp. 8–9
  • The chord absorber uses chord edges to balance leftover path systems before extending them into Hamilton cycles along the cluster cycle.Its universal-walk blow-up can be chosen in advance, without knowing the leftover, and its edges are used up in balancing.Source: §2.2 · p. 8
  • The parity extended cycle absorber turns a 1-factorization into Hamilton cycles by switching edges between factors, with switches using absorber edges rather than leftover edges.A switch can merge two cycles of a 1-factor into one Hamilton cycle.Source: §2.2 · p. 9, Figure 2 · p. 9

3. Notation and probabilistic estimates

The section sets conventions for graphs, digraphs, blow-ups, and asymptotic constant hierarchies. It also introduces probabilistic tools and explains how the existence arguments can be derandomized, while noting that no explicit decomposition runtime is proved.

3.1. Notation.

  • The notation fixes directed neighborhoods, degrees, edge counts between vertex sets, r-factors, and path systems as unions of vertex-disjoint directed paths.Source: §3.1 · p. 10
  • A blow-up replaces cluster vertices with their vertices and cluster edges with oriented bipartite graphs; a graph winds around a cycle when its edges go from each cluster to the next.The bipartite graphs used in blow-ups are usually ε-regular or superregular.Source: §3.1 · pp. 10–11
  • The constant hierarchy 1/n ≪ a ≪ b ≪ c means choosing constants successively small enough for the result, without divisibility assumptions on n.The functions governing the hierarchy are not calculated explicitly.Source: §3.1 · p. 11

3.2. Probabilistic estimates, derandomization and algorithmic aspects.

  • A Chernoff-type bound supplies probabilistic estimates, and the method of conditional probabilities derandomizes polynomially many applications to find the desired structure.The paper claims polynomial-time algorithms for the decomposition but gives no explicit runtime bound beyond polynomiality in n.Source: §3.2 · pp. 11–12

4. Regularity

This section develops regularity tools for partitioning and refining digraphs into regular cluster pairs, including sparse pairs, and for extracting structured subgraphs and matchings. It also uses the Blow-up Lemma to embed bounded-degree graphs and link prescribed endpoints.

4.1. The Regularity Lemma.

  • The digraph regularity lemma gives a bounded partition into equal-sized clusters and a small exceptional set, with a spanning subdigraph whose cluster pairs are empty or regular.Nonempty ordered pairs are ε-regular with density at least d; almost all vertices in an ε-regular pair have the expected degree, and almost all vertex pairs have the expected codegree.Source: §4.1 · pp. 12–13

4.2. Uniform refinements.

  • An ε-uniform refinement splits each cluster into equal subclusters while distributing every vertex’s in- and out-neighbourhoods approximately evenly.Such refinements exist, and inherited pairs remain superregular or regular with a relaxed parameter ε′.Source: §4.2 · p. 15

4.3. A sparse notion of ε-regularity.

  • Sparse (ε,d,c)-regularity allows d<ε and guarantees robust expansion for sets smaller than εm; ordinary (ε,≥d)-regularity guarantees it for sets between εm and (1−ε)m.Suppose 1/m ≪ ε, d ≤ 1/C ≤ 1, and ε ≪ 1/C; all but εm vertices in V have degree at least (1−ε)dm, every distinct pair in V has at most Cd²m common neighbours, and at most εm² distinct pairs in V are bad. Then G is {ε^(1/6), d}-regular.Source: §4.3 · pp. 16–17
  • An ε-regular or superregular bipartite graph contains spanning sparse subgraphs with controlled regularity and degree parameters.The lemma gives regular and superregular variants; in one variant, vertices whose original degree is (d ± ε)m have degree (d′ ± √ε)m in the subgraph.Source: §4.3 · p. 18
  • For τm ≤ |A| ≤ (1−τ)m, at least |A| + νm vertices of the opposite class have at least νm neighbours in A.The lemma also establishes a robust-neighbourhood lower bound for sets of size at least τm/2.Source: §4.3 · p. 20
  • An (ε,d′/k,d′/dk)-regular bipartite graph has a matching of size at least (1−ε)m, while an (ε,d′,ζd′,d′/d)-superregular one has a perfect matching.These guarantees follow under the parameter hierarchy stated in Lemma 4.12.Source: §4.3 · p. 21

4.4. The Blow-up Lemma.

  • Any graph of maximum degree at most Δ that embeds into the complete blow-up of a reduced graph also embeds into its corresponding (ε,d)-superregular blow-up, under the stated parameter conditions.The vertex classes have equal size m, and each reduced-graph edge is replaced by a superregular pair.Source: §4.4 · p. 22
  • An (ε,d)-superregular bipartite graph with equal-sized vertex classes contains a perfect matching.This is stated for 0 < 1/m ≪ ε ≪ d ≤ 1.Source: §4.4 · p. 22
  • For q ≥ 4 superregular pairs arranged along a path, the graph contains m vertex-disjoint paths connecting each prescribed vertex in the first class to its paired endpoint in the last class.The endpoint pairings may be any enumeration of the two classes.Source: §4.4 · p. 22

5. Robust Outexpanders

Robust outexpansion is preserved when passing to reduced digraphs and blow-ups. The section also develops a flow approach to finding spanning submultidigraphs with prescribed degrees.

5. Robust Outexpanders

  • A reduced digraph R of a robust (ν,τ)-outexpander G is a robust (ν/2,2τ)-outexpander with δ0(R)≥α|R|/2.The inheritance result requires G to be a robust outexpander, not merely an outexpander.Source: §5 · pp. 22–23
  • A robust outexpander supports a spanning submultidigraph with a prescribed degree sequence when requested degrees are not too large or too uneven.The stated degree-sequence result is formulated for a multidigraph Q containing at least q copies of every edge of G.Source: §5 · p. 23
  • The degree-sequence argument encodes the target submultidigraph as an integer flow and reduces existence to showing every cut has capacity at least rn.An integer-valued rn-flow corresponds to the desired spanning submultidigraph.Source: §5 · p. 23
  • For r≥3, the r-fold blow-up of a robust (ν,τ)-outexpander is a robust (ν^3,2τ)-outexpander.The blow-up replaces each vertex by r vertices and each directed edge by a complete bipartite digraph oriented toward the destination cluster.Source: §5 · p. 24

6. Tools for finding Hamilton cycles

The section assembles tools for finding Hamilton cycles, including a Hamiltonicity theorem for robust outexpanders and methods for turning regular factors into cycles. It also records related factorization and cycle-power results.

Factorization

  • Every regular multidigraph has a 1-factorization into edge-disjoint 1-factors.The proof forms a regular bipartite multigraph and applies Hall’s theorem to decompose it into perfect matchings.Source: §6 · p. 25

Hamilton cycle in robust outexpanders

  • Every digraph with minimum semidegree at least αn that is a robust (ν,τ)-outexpander contains a Hamilton cycle.The cited result also has a polynomial-time algorithmic version.Source: §6 · p. 25

Cycle-power result

  • Minimum degree 10n/11 guarantees that a sufficiently large graph contains the 10th power of a Hamilton cycle.The cited result is used in a bounded-size graph, and a bound of the form (1−ε)n would suffice for the proof.Source: §6 · p. 25

Turning factors into cycles

  • In a blow-up of a directed cycle with superregular successive cluster pairs, suitable edge replacements can turn a winding 1-regular digraph into a Hamilton cycle.The replacement uses edges between clusters to replace selected edges of the 1-regular digraph.Source: §6 · pp. 26–27

Matching replacement

  • Replacing a cluster-pair perfect matching can place all vertices of that pair on one common cycle while preserving pairs already sharing a cycle.The proof constructs an auxiliary robust outexpander and uses the Hamilton-cycle theorem to find the replacement matching.Source: §6 · p. 26

Regularity variant

  • The usual ε-regularity version of the cycle-conversion lemma applies when J=E(C) without its path condition (iii).The paper uses both versions only in this special case.Source: §6 · p. 27

7. Schemes, consistent systems, chord sequences, and exceptional factors

This section develops reduced-graph structures and balancing tools for incorporating exceptional vertices into Hamilton-cycle constructions. It shows how consistent systems and superregular pairs support the construction of many edge-disjoint exceptional factors by routing those vertices through refined clusters.

7.1. Schemes and consistent systems.

  • A consistent system couples robust outexpanders and nested partitions with compatible reduced-graph Hamilton cycles, while a scheme requires regular pairs and superregular pairs along its cycle.The refined reduced digraph is an ℓ∗-fold blow-up of the coarser one.Source: §7.1 · pp. 28–29

7.2. Shifted walks and chord sequences.

  • A chord sequence of at most 3/ν edges connects any two reduced-graph vertices while avoiding a set of at most ν|R|/4 vertices, and can balance an added edge through equal residual cluster sizes.When the chord edges form a matching, the equal sizes permit perfect matchings between consecutive clusters, contributing to a 1-regular digraph that can be transformed into a Hamilton cycle.Source: §7.2 · pp. 30–31

7.3. Complete exceptional sequences and exceptional factors.

  • An exceptional factor is a 1-factor built from KL complete exceptional path systems across intervals, with one system of each refinement style; a basic Hamilton cycle containing exactly one complete exceptional sequence lifts to a Hamilton cycle in G.A complete exceptional sequence is a matching containing precisely one exceptional edge associated with each exceptional vertex.Source: §7.3 · pp. 32–33

7.4. Finding exceptional factors in a consistent system.

  • Under its consistent-system and refinement hypotheses, Lemma 7.5 begins by guaranteeing each exceptional vertex a pair of distinct vertices x− and x+.The supplied passage gives only the start of this conclusion.Source: §7.4 · pp. 33–34
  • The construction assigns exceptional vertices distinct endpoint pairs, routes them with short chord sequences, and replaces the routes by pairwise vertex-disjoint matchings while preserving superregular cluster pairs.Each chord sequence uses at most 3/ν^3 edges, and each cluster pair along C is [ε′, ≥d]-superregular.Source: §7.4 · pp. 34, 36
  • A consistent system with an ε-uniform K-refinement admits r0 exceptional factors with parameters (K, L), whose original versions are pairwise edge-disjoint.The construction builds each factor from complete exceptional path systems spanning intervals of the cluster cycle.Source: §7.4 · pp. 37–38
  • For each interval and subcluster, matchings complete the exceptional paths; transforming the resulting path system into a Hamilton cycle yields the required exceptional factor.The construction uses superregular consecutive cluster pairs to find perfect matchings, then modifies those matchings to eliminate cycles in the path system.Source: §7.4 · pp. 37–38

8. The preprocessing step

This section describes how a preprocessing graph and path-system extenders turn the sparse regular leftover into a structure whose edges can be covered by edge-disjoint Hamilton cycles. It also explains how path systems yield Hamilton cycles and gives a matching decomposition of 1-regular digraphs by size, vertex-disjointness, and double-type.

8. The preprocessing step

  • The preprocessing graph combines exceptional factors with a path system extender, enabling Hamilton cycles to cover the leftover while leaving exceptional vertices isolated in the replacement leftover.The extender is spanning on the non-exceptional vertices; additional exceptional-factor edges compensate for the resulting imbalance and are designed to be absorbed later.Source: §8 · pp. 38–39, §8.1 · p. 41

8.1. Cycle breaking.

  • Lemma 8.1 decomposes H ∪ CBorig into s edge-disjoint path systems, each with one exceptional cover, style size 5, and at most 1230n/s edges.Splitting the exceptional cover breaks cycles that would prevent extension to a Hamilton cycle.Source: §8.1 · p. 39

8.2. Extending path systems into Hamilton cycles.

  • Lemma 8.2 guarantees a path system extender under the stated parameter hierarchy; its small maximum degree is needed to cover its leftover edges during chord-absorption.The extender uses a technical regularity condition to keep its maximum degree small relative to εm.Source: §8.2 · p. 41
  • Lemma 8.3 extends each eligible path system Q into a Hamilton cycle D with Q ⊆ D ⊆ PE ∪ Q.Q must be edge-disjoint from PE, contain exactly one exceptional cover and no other original exceptional edges, have style size 5, and have at most 1230n/s edges; the proof adds edges to make Q locally balanced before extending it.Source: §8.2 · p. 42
  • Lemma 8.4 produces sr edge-disjoint Hamilton cycles that together cover all edges of H ∪ CBorig.Its hypotheses include pairwise edge-disjointness of H, the path system extender, and the original exceptional factors.Source: §8.2 · p. 44

8.3. The preprocessing graph.

  • A preprocessing graph combines a path system extender and exceptional factors with a spanning subgraph that complements the extender’s degree sequence; Lemma 8.6 guarantees such a graph in a consistent system.This regularizes the leftover on V(G) \ V0 while excluding exceptional edges.Source: §8.3 · pp. 44–46
  • Corollary 8.5 yields rs edge-disjoint Hamilton cycles covering H, each contained in H ∪ PGorig, with V0 isolated in the leftover and every other vertex having degree r′′ − (s − 1)r.This applies when H and the original preprocessing graph are edge-disjoint; the leftover has the stated in- and outdegree at each vertex outside V0.Source: §8.3 · p. 45
  • Lemma 8.7 decomposes a 1-regular digraph into q* matchings, each with at most 2g²km/q* edges, with nearby indices vertex-disjoint and each matching of one double-type.These matching decompositions are used to split the preprocessing graph’s leftover into path systems for later extension into Hamilton cycles.Source: §8.3 · pp. 46–47

9. The chord absorbing step

This section develops chord absorption to incorporate leftover edges into structured path systems within a blown-up Hamilton cycle. It constructs edge-disjoint absorbers and extends the resulting systems to Hamilton cycles, including a parity-based analogue for bipartite setups.

9. The chord absorbing step

  • The chord absorber lets the leftover digraph’s edges be covered by Hamilton cycles while the unused absorber remains a blow-up of the cluster cycle.The construction also ensures that each cycle contains exactly one complete exceptional sequence, so its original version corresponds to a Hamilton cycle in G.Source: §9 · p. 47

9.1. Universal walks, setups and chord absorbers.

  • The compressed universal walk retains the needed chord edges while visiting each cluster only ℓ′ times; Lemma 9.1 gives ℓ′ = 36/ν^2 under robust-expansion and minimum-degree conditions.This avoids the excessive walk length of the natural construction, which visits each cluster more than k times.Source: §9 · p. 48, §9.1 · p. 49

9.2. Bi-universal walks, bi-setups and chord absorbers.

  • The bi-universal variant partitions walk edges into odd and even parts to support absorption of bipartite edge sets, but the text says it is used only in, not this paper.Its chord sequences connect clusters of the same parity, with each part balanced across all clusters.Source: §9.2 · p. 51

9.3. Finding chord absorbers.

  • Given suitable pairwise edge-disjoint exceptional factors, a setup contains a chord absorber; deleting at most ε′m in- and outedges per vertex preserves a setup with parameter (ε′)^(1/3).The construction supplies edge-disjoint spanning blow-ups of the cycle C and universal subcluster walk U′ before incorporating the exceptional factors.Source: §9.3 · pp. 52–53
  • After deleting the original exceptional edges, the setup remains valid, allowing Lemma 9.3 to find edge-disjoint B(C)* and B(U′) chord absorbers.The proof establishes this for setups; it states that the bi-setup case is identical.Source: §9.3 · p. 53

9.4. Absorbing chords into a blown-up Hamilton cycle.

  • The chord-absorbing construction uses B′(U′) edges predetermined independently of H, so the leftover after this step lies in B(C).The later covering of the preprocessing graph’s leftover uses all edges of B(U′).Source: §9.4 · p. 54
  • The key lemma constructs edge-disjoint Hamilton cycles that cover the original exceptional path-system edges and B′(U′), with all other cycle edges contained in B(C)*.Each cycle also contains the corresponding original exceptional path system H′i.Source: §9.4 · pp. 54–55
  • Augmented chord sequences make each matching’s edge sequence locally balanced, while their union uses every edge of U and U′ the same number of times.The sequences are extended with copies of U before their U′ edges are replaced by edges in the corresponding bipartite subgraphs; the resulting path systems are then extended to 1-factors and Hamilton cycles.Source: §9.4 · pp. 54–56

9.4. Absorbing chords into a blown-up Hamilton cycle

  • Ordering the edges of S(AB) makes short consecutive blocks matchings and separates edge groups, ensuring W′′′_i minus E(H_i) is a path system.The ordering conditions prevent a cycle from winding around U′.Source: §9.4 · pp. 59–60
  • In batches of ten, a perfect matching in an auxiliary bipartite graph assigns chord edges to the systems while avoiding conflicts with H′.The matching exists because each edge and each placeholder misses at most half of the opposite class; the assigned edges are then added to W′′′_i.Source: §9.4 · pp. 59–60
  • For every i, there is a Hamilton cycle in G containing all edges in the original version of W∗_i.This is Claim 5.Source: §9.4 · p. 61

9.4. Absorbing chords into a blown-up Hamilton cycle.

  • Perfect matchings across consecutive clusters are combined with each reserved path system and adjusted to form Hamilton cycles that are pairwise edge-disjoint.The resulting cycles use the original versions of the path systems.Source: §9.4 · p. 62
  • In the bipartite analogue, W contains every edge of Ueven teven times and every edge of Uodd todd times, with the corresponding multiplicities for U′.The construction separates the even- and odd-indexed cluster classes.Source: §9.4 · pp. 62–63
  • Lemma 9.6 assigns complete exceptional path systems so that each is vertex-disjoint from its Hi, while systems assigned to Hi and Hj are disjoint whenever |i − j| ≤ 10.The assignment applies under the lemma’s interval-occupancy and nearby-disjointness assumptions.Source: §9.4 · pp. 63–65
  • Under Lemma 9.7’s setup, s edge-disjoint Hamilton cycles contain H ∪ B(U′) ∪ (CAexc)orig, leaving an (r1 + r2 + r − (q − 1)s/q)-blow-up of C.All other edges in the cycles lie in B(C)*, and each basic cycle contains one of the complete exceptional path systems.Source: §9.4 · p. 65
  • Each exceptional-factor group supplies q′ complete exceptional path systems, which Lemma 9.6 suitably labels to meet the required disjointness conditions.The resulting systems satisfy (b2) and (b3); conditions (b1) and (b4) follow from the stated path-count and edge-disjointness properties.Source: §9.4 · pp. 66–67
  • Splitting B(U′) into r edge-disjoint r∗-blow-ups allows Lemma 9.5 to be applied successively, producing q′ edge-disjoint Hamilton cycles for each F_i∗.The remaining part of B(C)∗ stays superregular at every step because the total in- and outdegree loss is at most m/f.Source: §9.4 · p. 67
  • The resulting Hamilton cycles are pairwise edge-disjoint and satisfy properties (i)–(iii), with the degree condition verified for vertices outside V0.At each such vertex, the cycles cover all specified outedges in B(U′), (CAexc)orig, and H; the analogous indegree argument completes the verification.Source: §9.4 · pp. 67–68

10. Absorbing a blown-up cycle via switches

This section develops cycle and parity-extended absorbers, using switches and routed path systems to incorporate leftover or prescribed exceptional factors and convert resulting 1-factors or spanning bicycles into Hamilton cycles. The constructions can be repeated while preserving scheme conditions and yield decompositions under stated structural conditions.

10. Absorbing a blown-up cycle via switches

  • The proof removes the cycle absorber before decomposing the original digraph, then combines it with the leftover blow-up of the cycle and switches edges from the absorber into the leftover’s 1-factors.The intended factorization has either half or all edges of each 1-factor coming from the absorber.Source: §10 · p. 68

10.1. Definition of the cycle absorber.

  • The cycle absorber comprises three edge-disjoint 1-regular digraphs winding around the cycle, arranged so switches with two bicycle factors can transform a given winding 1-factor.The absorber includes designated potential switches for attachment to the parity switcher; pairwise switches alone preserve the parity of the number of cycles.Source: §10 · p. 68, §10.1 · pp. 69–70

10.2. Using the cycle absorber.

  • H ∪ CyAorig decomposes into four 1-factors, two Hamilton cycles and two others each a Hamilton cycle or a spanning bicycle.If either of the latter factors is a bicycle, its two cycles contain specified absorber edges used to attach the parity switcher.Source: §10.2 · p. 71
  • Switches between the absorber and a given 1-factor merge its distinct cycles until it becomes Hamilton, while transforming the absorber factor into a Hamilton cycle or bicycle.The proof uses a switch index where consecutive designated vertices lie on different cycles; each switch reduces the number of cycles in the given factor.Source: §10.2 · p. 72
  • Switches preserve specified complete exceptional path systems, allowing the resulting factor F1 to be a Hamilton cycle.The passage also states that the argument for F3 is similar.Source: §10.2 · p. 74

10.3. Finding the cycle absorber.

  • A cycle absorber exists in every stated (k, m, ε, d)-scheme with the specified exceptional factor and canonical seven-interval partition.The construction produces F and S satisfying (CyA0)–(CyA3).Source: §10.3 · pp. 74, 76

10.4. The parity switcher.

  • Three edge-disjoint triply-switchable bicycles can be decomposed either into three edge-disjoint Hamilton cycles or into six cycles, enabling a parity change.A K*2,3-exchange turns each of the three bicycles into a Hamilton cycle.Source: §10.4 · pp. 76–77
  • An s-fold parity-extended cycle absorber is 6s-regular on nonexceptional vertices and contains precisely 7s complete exceptional path systems.Its original version is a spanning subdigraph of G.Source: §10.4 · p. 78
  • H ∪ PCA(s)orig decomposes into 7s edge-disjoint Hamilton cycles when H is an s-factor that is a blow-up of C and is edge-disjoint from the absorber.Each Hamilton cycle contains the original version of one of the 7s complete exceptional path systems in PCA(s)orig.Source: §10.4 · p. 78
  • For s pairwise edge-disjoint exceptional factors, Lemma 10.5 yields an s-fold parity extended cycle absorber containing precisely their 7s complete exceptional path systems.The factors have parameters (1, 7) with respect to C and P.Source: §10.4 · p. 79
  • A single absorber is formed from a cycle absorber and three bicycles, with routed path systems incorporating prescribed switches and exceptional path systems.The bicycles are assembled using matchings and vertex-disjoint paths in the blow-up of C.Source: §10.4 · pp. 79–81
  • The construction is repeated to obtain edge-disjoint absorbers PCA2 through PCAs, since deleting earlier absorbers leaves the residual digraph satisfying the scheme conditions.The proof bounds the per-vertex neighbourhood loss by 7s and applies Lemma 7.1(ii) to retain the scheme.Source: §10.4 · p. 81

11. Proof of Theorem 1.2

This proof section develops a robust-decomposition lemma and a tool for covering edges inside a small exceptional set, then uses robust expansion and successive residual digraphs to construct four edge-disjoint collections of Hamilton cycles whose union decomposes G.

Lemma 11.1

  • A robust outexpander with linear minimum semidegree contains εn edge-disjoint Hamilton cycles that together cover every edge induced by a vertex set of size at most εn.The proof partitions the induced edges into matchings and finds a Hamilton cycle containing each matching.Source: §11 · p. 81

Lemma 11.2

  • Lemma 11.2 constructs a sparse robustly decomposable digraph Grob so that, for an eligible edge-disjoint r-factor H, H ∪ Grob decomposes into edge-disjoint Hamilton cycles.Each cycle’s basic version contains a complete exceptional path system; the lemma also has a bipartite analogue under the stated condition on H.Source: §11 · pp. 81–82

Proof of Theorem 1.2

  • The proof of Theorem 1.2 builds a regularity-based setup, removes preprocessing and absorbing graphs, covers the exceptional-set edges, then decomposes an approximate decomposition’s sparse leftover together with the absorbers.The robustly decomposable graph Grob combines the chord and parity extended cycle absorbers.Source: §11 · p. 84

11. Proof of Theorem 1.2

  • Theorem 1.3 supplies r# − r0 edge-disjoint Hamilton cycles in G#, leaving an r0-regular subdigraph H0 of G0.G# remains a robust (ν/2, τ)-outexpander with minimum semidegree at least αn/2.Source: §11 · p. 87
  • Corollary 8.5 yields r0s edge-disjoint Hamilton cycles C0, and Lemma 11.2(ii)(b) decomposes H1 ∪ Grob into C1.C0 contains all edges of H0; the resulting residual H1 is an r∗-regular subdigraph of G0 − V0.Source: §11 · pp. 87–88
  • C△ ∪ C# ∪ C0 ∪ C1 is a Hamilton decomposition of G.The construction combines cycles obtained from G△, G#, the absorber, and the remaining subdigraph.Source: §11 · p. 88

12. Statement of the robust decomposition lemma for further use

The standalone robust decomposition lemma replaces exceptional edges and path systems with fictive edges and special path systems. This lets it handle edges connecting robust expanders, including small departures from an approximate bipartition, while still producing edge-disjoint Hamilton cycles.

12. Statement of the robust decomposition lemma for further use

  • The standalone lemma uses fictive edges and special path systems to handle edges connecting robust expanders, even when the combined digraph is not itself a robust expander.The same approach can handle edges that do not respect an approximate bipartition.Source: §12 · p. 88
  • A special path system consists of vertex-disjoint paths across an interval, with fictive matching edges and prescribed vertex counts in its clusters.Its non-fictive path edges must belong to G; the fictive edges avoid the interval’s endclusters.Source: §12 · p. 88
  • A special factor is a 1-regular digraph built from K special path systems per interval, with exactly one system of each style on every interval.The factor’s fictive edges are the union of those in its constituent path systems.Source: §12 · p. 88
  • Given the specified setup and edge-disjoint special factors, the lemma constructs spanning subdigraphs and decomposes H + Grob into s′ edge-disjoint Hamilton cycles.Here Grob is formed from CA⋄(r), PCA⋄(r), SF, and SF′; H must be r-regular and edge-disjoint from Grob.Source: §12 · p. 89
  • Each resulting Hamilton cycle contains a special path system; the lemma also has a bipartite version when H has the specified even and odd vertex classes.The fictive edges occur within fixed special path systems and are not modified during the construction.Source: §12 · pp. 89–90

13. Proofs of Theorems 1.1 and 1.4

The section derives robust outexpansion from degree conditions and uses it with Theorem 1.2 in the proofs of Hamilton-decomposition results. It gives separate criteria for oriented graphs and digraphs, with the latter using a minimum-semidegree threshold above n/2.

13. Proofs of Theorems 1.1 and 1.4

  • An oriented graph satisfying δ+(G) + δ−(G) + δ(G) ≥ 3n/2 + εn is a robust (ν, τ)-outexpander under the stated hierarchy of constants.The proof of Theorem 1.1 uses robust outexpansion and Theorem 1.2 to obtain a Hamilton decomposition.Source: §13 · pp. 90–91
  • The oriented-graph criterion is proved by contradiction using a vertex partition and degree bounds on its parts.The argument derives bounds for the in- and outdegrees and total degree, then combines them to contradict the assumed degree-sum threshold.Source: §13 · pp. 90–91
  • A digraph with minimum semidegree δ0(G) ≥ (1/2 + ε)n is a robust (ν, τ)-outexpander when ε ≥ 2ν/τ.The proof of Theorem 1.4 applies Theorem 1.2 with α := 1/2 to obtain a Hamilton decomposition.Source: §13 · p. 91
  • For sets S of size at least n/2, the semidegree condition makes every vertex receive at least εn inneighbours from S; smaller S are handled by bounding edges from S into its robust outneighbourhood.This yields |RN| ≥ |S| + νn for the sets considered in the proof.Source: §13 · p. 91
Loading 1202.6219v2…