The Existence of Designs Via Iterative Absorption : Hypergraph -Designs for Arbitrary / Stefan Glock, Daniela Kühn, and Allan Lo.

Format:

Book

Author/Creator:

Glock, Stefan, author.

Kühn, Daniela, author.

Lo, Allan, 1983- author.

Series:

Memoirs of the American Mathematical Society ; Volume 284.

Memoirs of the American Mathematical Society Series ; Volume 284

Language:

English

Subjects (All):

Combinatorial packing and covering.

Decomposition (Mathematics).

Block designs.

Physical Description:

1 online resource (144 pages)

Edition:

First edition.

Place of Publication:

Providence, RI : American Mathematical Society, [2023]

Summary:

"We solve the existence problem for F-designs for arbitrary r-uniform hypergraphs F. This implies that given any r-uniform hypergraph F, the trivially necessary divisibility conditions are sufficient to guarantee a decomposition of any sufficiently large complete r-uniform hypergraph into edge-disjoint copies of F, which answers a question asked e.g. by Keevash. The graph case r [equals] 2 was proved by Wilson in 1975 and forms one of the cornerstones of design theory. The case when F is complete corresponds to the existence of block designs, a problem going back to the 19th century, which was recently settled by Keevash. In particular, our argument provides a new proof of the existence of block designs, based on iterative absorption (which employs purely probabilistic and combinatorial methods). Our main result concerns decompositions of hypergraphs whose clique distribution fulfills certain regularity constraints. Our argument allows us to employ a 'regularity boosting' process which frequently enables us to satisfy these constraints even if the clique distribution of the original hypergraph does not satisfy them. This enables us to go significantly beyond the setting of quasirandom hypergraphs considered by Keevash. In particular, we obtain a resilience version and a decomposition result for hypergraphs of large minimum degree"-- Provided by publisher.

Contents:

Cover

Title page

Chapter 1. Introduction

1.1. Background

1.2. -designs in quasirandom hypergraphs

1.3. -designs in hypergraphs of large minimum degree

1.4. Varying block sizes

1.5. Matchings and further results

1.6. Counting

1.7. Outline of the paper

Acknowledgments

Chapter 2. Notation

2.1. Basic terminology

2.2. Hypergraphs and complexes

Chapter 3. Outline of the methods

3.1. Iterative absorption

3.2. The Cover down lemma

3.3. Transformers and absorbers

Chapter 4. Decompositions of supercomplexes

4.1. Supercomplexes

4.2. The main complex decomposition theorem

4.3. Applications

4.4. Disjoint decompositions and designs

Chapter 5. Tools

5.1. Basic tools

5.2. Some properties of supercomplexes

5.3. Probabilistic tools

5.4. Random subsets and subgraphs

5.5. Rooted Embeddings

Chapter 6. Nibbles, boosting and greedy covers

6.1. The nibble

6.2. The Boost lemma

6.3. Approximate -decompositions

6.4. Greedy coverings and divisibility

Chapter 7. Vortices

7.1. The Cover down lemma

7.2. Existence of vortices

7.3. Existence of cleaners

7.4. Obtaining a near-optimal packing

Chapter 8. Absorbers

8.1. Transformers

8.2. Canonical multi- -graphs

8.3. Proof of the Absorbing lemma

Chapter 9. Proof of the main theorems

9.1. Main complex decomposition theorem

9.2. Resolvable partite designs

9.3. Proofs of Theorems 1.1, 1.2, 1.4, 1.6 and 1.7

Chapter 10. Covering down

10.1. Systems and focuses

10.2. Partition pairs

10.3. Partition regularity

10.4. Proof of the Cover down lemma

Chapter 11. Achieving divisibility

11.1. Degree shifters

11.2. Shifting procedure

11.3. Proof of Lemma 9.4

Chapter 12. Recent developments

Bibliography

Back Cover.

Notes:

Includes bibliographical references.

Description based on print version record.

Other Format:

Print version: Glock, Stefan The Existence of Designs Via Iterative Absorption: Hypergraph - Designs for Arbitrary

ISBN:

9781470474447

1470474441