ORPP logo
Image from Google Jackets

Proof of the 1-Factorization and Hamilton Decomposition Conjectures.

By: Contributor(s): Material type: TextTextSeries: Memoirs of the American Mathematical Society SeriesPublisher: Providence : American Mathematical Society, 2016Copyright date: ©2016Edition: 1st edDescription: 1 online resource (176 pages)Content type:
  • text
Media type:
  • computer
Carrier type:
  • online resource
ISBN:
  • 9781470435080
Subject(s): Genre/Form: Additional physical formats: Print version:: Proof of the 1-Factorization and Hamilton Decomposition ConjecturesDDC classification:
  • 512.9/23
LOC classification:
  • QA161.F3 C73 2016
Online resources:
Contents:
Cover -- Title page -- Chapter 1. Introduction -- 1.1. Introduction -- 1.2. Notation -- 1.3. Derivation of Theorems 1.1.1, 1.1.3, 1.1.4 from the Main Structural Results -- 1.4. Tools -- Chapter 2. The two cliques case -- 2.1. Overview of the Proofs of Theorems 1.3.3 and 1.3.9 -- 2.2. Partitions and Frameworks -- 2.3. Exceptional Systems and ( , ,\eps₀)-Partitions -- 2.4. Schemes and Exceptional Schemes -- 2.5. Proof of Theorem 1.3.9 -- 2.6. Eliminating the Edges inside ₀ and ₀ -- 2.7. Constructing Localized Exceptional Systems -- 2.8. Special Factors and Exceptional Factors -- 2.9. The Robust Decomposition Lemma -- 2.10. Proof of Theorem 1.3.3 -- Chapter 3. Exceptional systems for the two cliques case -- 3.1. Proof of Lemma 2.7.1 -- 3.2. Non-critical Case with ( ', ')≥ -- 3.3. Critical Case with ( ', ')≥ -- 3.4. The Case when ( ', ')&lt -- -- Chapter 4. The bipartite case -- 4.1. Overview of the Proofs of Theorems 1.3.5 and 1.3.8 -- 4.2. Eliminating Edges between the Exceptional Sets -- 4.3. Finding Path Systems which Cover All the Edges within the Classes -- 4.4. Special Factors and Balanced Exceptional Factors -- 4.5. The Robust Decomposition Lemma -- 4.6. Proof of Theorem 1.3.8 -- 4.7. Proof of Theorem 1.3.5 -- Chapter 5. Approximate decompositions -- 5.1. Useful Results -- 5.2. Systems and Balanced Extensions -- 5.3. Finding Systems and Balanced Extensions for the Two Cliques Case -- 5.4. Constructing Hamilton Cycles via Balanced Extensions -- 5.5. The Bipartite Case -- Acknowledgement -- Bibliography -- Back Cover.
Summary: 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.
Tags from this library: No tags from this library for this title. Log in to add tags.
Star ratings
    Average rating: 0.0 (0 votes)
No physical items for this record

Cover -- Title page -- Chapter 1. Introduction -- 1.1. Introduction -- 1.2. Notation -- 1.3. Derivation of Theorems 1.1.1, 1.1.3, 1.1.4 from the Main Structural Results -- 1.4. Tools -- Chapter 2. The two cliques case -- 2.1. Overview of the Proofs of Theorems 1.3.3 and 1.3.9 -- 2.2. Partitions and Frameworks -- 2.3. Exceptional Systems and ( , ,\eps₀)-Partitions -- 2.4. Schemes and Exceptional Schemes -- 2.5. Proof of Theorem 1.3.9 -- 2.6. Eliminating the Edges inside ₀ and ₀ -- 2.7. Constructing Localized Exceptional Systems -- 2.8. Special Factors and Exceptional Factors -- 2.9. The Robust Decomposition Lemma -- 2.10. Proof of Theorem 1.3.3 -- Chapter 3. Exceptional systems for the two cliques case -- 3.1. Proof of Lemma 2.7.1 -- 3.2. Non-critical Case with ( ', ')≥ -- 3.3. Critical Case with ( ', ')≥ -- 3.4. The Case when ( ', ')&lt -- -- Chapter 4. The bipartite case -- 4.1. Overview of the Proofs of Theorems 1.3.5 and 1.3.8 -- 4.2. Eliminating Edges between the Exceptional Sets -- 4.3. Finding Path Systems which Cover All the Edges within the Classes -- 4.4. Special Factors and Balanced Exceptional Factors -- 4.5. The Robust Decomposition Lemma -- 4.6. Proof of Theorem 1.3.8 -- 4.7. Proof of Theorem 1.3.5 -- Chapter 5. Approximate decompositions -- 5.1. Useful Results -- 5.2. Systems and Balanced Extensions -- 5.3. Finding Systems and Balanced Extensions for the Two Cliques Case -- 5.4. Constructing Hamilton Cycles via Balanced Extensions -- 5.5. The Bipartite Case -- Acknowledgement -- Bibliography -- Back Cover.

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.

Description based on publisher supplied metadata and other sources.

Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2024. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.

There are no comments on this title.

to post a comment.

© 2024 Resource Centre. All rights reserved.