**Memoirs of the American Mathematical Society**

2016;
164 pp;
Softcover

MSC: Primary 05;

Print ISBN: 978-1-4704-2025-3

Product Code: MEMO/244/1154

List Price: $90.00

AMS Member Price: $54.00

MAA Member Price: $81.00

**Electronic ISBN: 978-1-4704-3508-0
Product Code: MEMO/244/1154.E**

List Price: $90.00

AMS Member Price: $54.00

MAA Member Price: $81.00

# Proof of the 1-Factorization and Hamilton Decomposition Conjectures

Share this page
*Béla Csaba; Daniela Kühn; Allan Lo; Deryk Osthus; Andrew Treglown*

In this paper the authors prove the following results (via a
unified approach) for all sufficiently large \(n\):

(i) [\(1\)-factorization conjecture] Suppose
that \(n\) is even and \(D\geq 2\lceil n/4\rceil -1\).
Then every \(D\)-regular graph \(G\) on \(n\)
vertices has a decomposition into perfect matchings. Equivalently,
\(\chi'(G)=D\).

(ii) [Hamilton decomposition conjecture] Suppose that
\(D \ge \lfloor n/2 \rfloor \). Then every
\(D\)-regular graph \(G\) on \(n\) vertices has a
decomposition into Hamilton cycles and at most one perfect matching.

(iii) [Optimal packings of Hamilton cycles] Suppose that \(G\) is a graph on \(n\) vertices with
minimum degree \(\delta\ge n/2\).
Then \(G\) contains at least \({\rm reg}_{\rm even}(n,\delta)/2 \ge (n-2)/8\) edge-disjoint Hamilton cycles.
Here \({\rm reg}_{\rm even}(n,\delta)\) denotes the degree of the
largest even-regular spanning subgraph one can guarantee in a graph on \(n\) vertices
with minimum degree \(\delta\).

(i) was first explicitly stated by Chetwynd and Hilton. (ii) and
the special case \(\delta= \lceil n/2 \rceil\) of (iii) answer
questions of Nash-Williams from 1970. All of the above bounds are
best possible.

#### Table of Contents

# Table of Contents

## Proof of the 1-Factorization and Hamilton Decomposition Conjectures

- Cover Cover11
- Title page i2
- Chapter 1. Introduction 18
- Chapter 2. The two cliques case 1522
- 2.1. Overview of the Proofs of Theorems 1.3.3 and 1.3.9 1522
- 2.2. Partitions and Frameworks 1825
- 2.3. Exceptional Systems and (𝐾,𝑚,\eps₀)-Partitions 2128
- 2.4. Schemes and Exceptional Schemes 2431
- 2.5. Proof of Theorem 1.3.9 2734
- 2.6. Eliminating the Edges inside 𝐴₀ and 𝐵₀ 3239
- 2.7. Constructing Localized Exceptional Systems 3845
- 2.8. Special Factors and Exceptional Factors 4249
- 2.9. The Robust Decomposition Lemma 5057
- 2.10. Proof of Theorem 1.3.3 5663

- Chapter 3. Exceptional systems for the two cliques case 6976
- Chapter 4. The bipartite case 95102
- 4.1. Overview of the Proofs of Theorems 1.3.5 and 1.3.8 95102
- 4.2. Eliminating Edges between the Exceptional Sets 98105
- 4.3. Finding Path Systems which Cover All the Edges within the Classes 106113
- 4.4. Special Factors and Balanced Exceptional Factors 121128
- 4.5. The Robust Decomposition Lemma 129136
- 4.6. Proof of Theorem 1.3.8 134141
- 4.7. Proof of Theorem 1.3.5 136143

- Chapter 5. Approximate decompositions 143150
- Bibliography 163170
- Back Cover Back Cover1176