On the probability of nonexistence in binomial subsets

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 investig...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-04
Main Authors: Mousset, Frank, Noever, Andreas, Panagiotou, Konstantinos, Samotij, Wojciech
Format: Article
Language:English
Subjects:
Asymptotic properties
Colon
Combinatorial analysis
Containment
Graph theory
Integers
Progressions
Random variables
Statistical analysis
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422