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.

Included in

Mathematics Commons

Share

COinS