ON THE PROBABILITY OF NONEXISTENCE IN BINOMIAL SUBSETS

• 成果类型: Article
• 署名作者: Mousset, Frank; Noever, Andreas; Panagiotou, Konstantinos; Samotij, Wojciech
• 署名单位: Tel Aviv University; Swiss Federal Institutes of Technology Domain; ETH Zurich; University of Munich
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/19-AOP1371
• 发表日期: 2020
• 页码: 493-525
• 关键词: NUMBER; graphs

摘要

Given a hypergraph Gamma = (Omega, chi) and a sequence p = (p(omega))(omega is an element of)(Q) of values in (0, 1), let Omega(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(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.