Pith. sign in

REVIEW

On the probability of nonexistence in binomial subsets

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1711.06216 v2 pith:MLSRSHPD submitted 2017-11-16 math.CO math.PR

On the probability of nonexistence in binomial subsets

classification math.CO math.PR
keywords omegaprobabilityrandommathbfboundsgammalowerquestion
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Given a hypergraph $\Gamma=(\Omega,\mathcal{X})$ and a sequence $\mathbf{p} = (p_\omega)_{\omega\in \Omega}$ of values in $(0,1)$, let $\Omega_{\mathbf{p}}$ be the random subset of $\Omega$ obtained by keeping every vertex $\omega$ independently with probability $p_\omega$. We investigate the general question of deriving fine (asymptotic) estimates for the probability that $\Omega_{\mathbf{p}}$ is an independent set in $\Gamma$, which is an omnipresent problem in probabilistic combinatorics. Our main result provides a sequence of upper and lower bounds on this probability, each of which can be evaluated explicitly in terms of the joint cumulants of small sets of edge indicator random variables. Under certain natural conditions, these upper and lower bounds coincide asymptotically, thus giving the precise asymptotics of the probability in question. We demonstrate the applicability of our results with two concrete examples: subgraph containment in random (hyper)graphs and arithmetic progressions in random subsets of the integers.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.