Threshold progressions in covering and packing contexts

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 $\mathcal{A}$ being “covered” by at most one object in a random collection $\mathcal{C}$, to being covered at most $\lambda$ times, to being covered at least once, to being covered at least $\lambda$ 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.

Keywords

thresholds, Poisson approximation, covering and packing

2010 Mathematics Subject Classification

Primary 05D40, 60C05. Secondary 05D99, 60F05.

Full Text (PDF format)

The research of all four authors was supported by NSF Grant DMS-1263009.

Notice: This manuscript has been authored in part by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a nonexclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes. The Department of Energy will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/downloads/doe-public-access-plan).

Received 18 July 2018

Accepted 29 March 2021

Published 31 March 2022