Upper tails via high moments and entropic stability

DOI10.1215/00127094-2021-0067MaRDI QIDQ2165741zbMATH OpenOpenAlexFDO

Authors Matan Harel, Frank Mousset, Wojciech Samotij

Publication date 22 August 2022

Published in Duke Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.08212

zbMATH Keywords

arithmetic progressions concentration inequalities nonlinear large deviations random graphs upper tails

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Large deviations (60F10)

Abstract: Suppose that

X

is a bounded-degree polynomial with nonnegative coefficients on the

p

-biased discrete hypercube. Our main result gives sharp estimates on the logarithmic upper tail probability of

X

whenever an associated extremal problem satisfies a certain entropic stability property. We apply this result to solve two long-standing open problems in probabilistic combinatorics: the upper tail problem for the number of arithmetic progressions of a fixed length in the

p

-random subset of the integers and the upper tail problem for the number of cliques of a fixed size in the random graph

G_{n, p}

. We also make significant progress on the upper tail problem for the number of copies of a fixed regular graph

H

in

G_{n, p}

. To accommodate readers who are interested in learning the basic method, we include a short, self-contained solution to the upper tail problem for the number of triangles in

G_{n, p}

for all

p = p (n)

satisfying

n^{- 1} l o g n l l p l l 1

.

Review text

This paper studies upper tail probability related to a bounded-degree polynomial with nonnegative coefficients on the \(p\)-based discrete hypercube. Let \(\Delta\ge 2\) be an integer and \(H\) be a connected non-bipartite and \(\Delta\)-regular graph. Suppose \(X\) is the number of copies of \(H\) in the random graph model \(G_{n,p}\). Let \(v_H\) be the number of vertices in \(H\). For every fixed \(\delta>0\) and \(p=p(n)\) satisfying \(n^{-1}(\ln n)^{\Delta v^2_H}\ll p^{\Delta/2}\ll 1\), it is shown that \(\lim_{n\rightarrow\infty}-\ln P(X\ge(1+\delta)EX)/(n^2p^{\Delta}\ln(1/p))=\delta^{2/v_H}/2\) if \(np^{\Delta}\rightarrow0\) and \(\min\{\delta^{2/v_H}/2,\theta\}\) if \(np^{\Delta}\rightarrow\infty\), where \(\theta\) is the unique positive solution to \(P_H(\theta)=1+\delta\). Here, \(P_H(\theta)=\sum_k i_k(H)\theta^k\), where \(i_k(H)\) is the number of independent sets of \(H\) of size \(k\). If \(H\) is a connected \(\Delta\)-regular graph, then for \(n^{-1}\ll p^{\Delta/2}\ll n^{-1}(\ln n)^{1/v_H^{-2}}\), it is shown that \(\lim_{n\rightarrow\infty}-\ln P(X\ge(1+\delta)EX)/EX=(1+\delta)\ln (1+\delta)-\delta\). Based on the developed techniques, cliques in random graphs and extensions to regular graphs have also be considered.

Recommendations

Cites work

Cited in

(32)

This page was built for publication: Upper tails via high moments and entropic stability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2165741)