Date of Award
1-1-2013
Document Type
Open Access Dissertation
Department
Mathematics
First Advisor
László A Székely
Abstract
The Lovász local lemma is a powerful and well-studied probabilistic technique useful in establishing the possibility of simultaneously avoiding every event in some collection. A principle limitation of the lemma's application is that it requires most events to be independent of one another. The lopsided local lemma relaxes the requirement of independence to negative dependence, which is more general but also more difficult to identify. We will examine general classes of negative dependent events involving maximal matchings of uniform hypergraphs, partitions of sets, and spanning trees of complete graphs. The results on hypergraph matchings (together with the configuration model of Bollobás) yield asymptotically the number of regular, uniform hypergraphs avoiding small cycles. Finally, we work toward a characterization of hypergraphs for which the matching paradigm is guaranteed to generate negative dependent events.
Rights
© 2013, Austin Tyler Mohr
Recommended Citation
Mohr, A. T.(2013). Applications of the Lopsided Lovász Local Lemma Regarding Hypergraphs. (Doctoral dissertation). Retrieved from https://scholarcommons.sc.edu/etd/1606