Locally nearly perfect packings Open Access

Martin, Daniel M. (2009)

Permanent URL: https://etd.library.emory.edu/concern/etds/wh246s31g?locale=en
Published

Abstract

In 1963 P. Erdos and H. Hanani conjectured that for every fixed positive integers l < k, and for every n there exists a family Fn of k-element subsets of {1, 2, . . . , n} with the property that every l-element subset of {1, 2, . . . , n} is contained in at most one member of Fn, and the proportion of l-element subsets which are not contained in any member of Fn tends to 0 as n tends to infinity. The conjecture was solved by V. Rodl in 1985. Since then, many improvements and generalizations followed Rodl's result. Until the present moment all known proofs of the conjecture use the "semi-random method", an iterative process in which the desired set system is build as a successive union of small randomly chosen pieces. In the first part of this dissertation we give an alternative proof of Rodl's result using a somewhat different approach which is elementary and fairly simple. In the second part, we use the semi-random method to show a strengthening of Rodl's result in which the family Fn is also required to satisfy that, for every 0 < j < l and for all j-element subset J in {1, 2, . . . , n}, the proportion of l-element subsets containing J which are not contained in any member of Fn tends to 0 as n tends to infinity. This means that the family Fn is close to being a perfect packing not only globally, but also locally.

Table of Contents

Contents
1 Introduction...1

1.1 A problem on combinations...1

1.1.1 Steiner systems...3
1.1.2 Partial Steiner systems...5

1.2 The conjecture of P. Erdos and H. Hanani...5

1.2.1 A connection with matchings in hypergraphs...7
1.2.2 Exploiting the connection...8

1.3 A result of interest...9
1.4 Main results...12
1.5 A word about packings and coverings...13

2 Probabilistic tools...15

2.1 Basic probability...15

2.1.1 Probability spaces...15
2.1.2 Inclusion-Exclusion...16
2.1.3 Independence...16
2.1.4 Random variables...17

2.2 Concentration...17

2.2.1 Markov's Inequality...17
2.2.2 The Chernoff Bound...18
2.2.3 A martingale inequality...19

3 A simple proof...21

3.1 Introduction...21
3.2 An easy bound...22
3.3 The construction...23
3.4 The analysis...27
3.5 A finer analysis...29

4 Locally quasi-perfect packings...34

4.1 Introduction...34
4.2 Simplifying the problem...34
4.3 Main strategy...35
4.4 Preliminaries...36

4.4.1 Important definitions...36
4.4.2 Random bites...38

4.5 Biting lemma...40

4.5.1 Bounding the wasted l-degree of (l − 1)-sets...42
4.5.2 Bounding the k-degree of l-shadows...44
4.5.3 Bounding the l-degree of (l − 1)-sets...52

4.6 Construction of Ho...54
4.7 Successive bites...55
4.8 Proof of Theorem 4.1...59

Appendix...61
Bibliography...63

About this thesis

Rights statement
  • Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.
School
Department
Degree
Submission
Language
  • English
Research field
Keyword
Committee Chair / Thesis Advisor
Committee Members
Last modified

Primary PDF

Supplemental Files