Threshold progressions in covering and packing contexts

Abstract

Using standard methods (due to Janson, Stein–Chen, and Talagrand) from probabilistic combinatorics, we explore the following general theme: As one progresses from each member of a family of objects A being “covered” by at most one object in a random collection C, to being covered at most λ times, to being covered at least once, to being covered at least λ times, a hierarchy of thresholds emerge. We will use examples from extremal set theory, combinatorics, and additive number theory to see how these results vary according to the context, and level of dependence introduced.