Locally nearly perfect packings 公开

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

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	Laney Graduate School
Department	Math and Computer Science
Degree	PhD
Submission	Dissertation
Language	English
Research Field	Computer Science Mathematics
关键词	Erdos-Hanani packing subsets Steiner systems
Committee Chair / Thesis Advisor	Rodl, Vojtech, Emory University
Committee Members	Roth Jr., Robert, Emory University Gould, Ronald J, Emory University

最新修改

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Locally nearly perfect packings ()	2018-08-28 10:53:29 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions