Digital Commons Network^™

Applications Of The Lopsided Lovász Local Lemma Regarding Hypergraphs, Austin Tyler Mohr

Theses and Dissertations

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 …