Proof of the 1-factorization and Hamilton decomposition conjectures II: the bipartite case

In a sequence of four papers, we 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, $χ'(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 $δ\ge n/2$. Then $G$ contains at least ${\rm reg}_{\rm even}(n,δ)/2 \ge (n-2)/8$ edge-disjoint Hamilton cycles. Here ${\rm reg}_{\rm even}(n,δ)$ denotes the degree of the largest even-regular spanning subgraph one can guarantee in a graph on $n$ vertices with minimum degree $δ$. According to Dirac, (i) was first raised in the 1950s. (ii) and the special case $δ= \lceil n/2 \rceil$ of (iii) answer questions of Nash-Williams from 1970. All of the above bounds are best possible. In the current paper, we prove the above results for the case when $G$ is close to a complete balanced bipartite graph.

No reviews yet.

No comments yet.