Locally nearly perfect packings Público
Martin, Daniel M. (2009)
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 Dissertation
| School | |
|---|---|
| Department | |
| Degree | |
| Submission | |
| Language |
|
| Research Field | |
| Palabra Clave | |
| Committee Chair / Thesis Advisor | |
| Committee Members |
Primary PDF
| Thumbnail | Title | Date Uploaded | Actions |
|---|---|---|---|
|
|
Locally nearly perfect packings () | 2018-08-28 10:53:29 -0400 |
|
Supplemental Files
| Thumbnail | Title | Date Uploaded | Actions |
|---|