Deviation probabilities for arithmetic progressions and irregular discrete structures

DOI10.1214/23-EJP1012MaRDI QIDQ6136819zbMATH OpenFDO

Authors Simon Griffiths, Christoph Koch, Matheus Secco

Publication date 17 January 2024

Published in Electronic Journal of Probability (Search for Journal in Brave)

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

zbMATH Keywords

martingalesmoderate deviationsarithmetic progressionshypergraphsrandom processes

Mathematics Subject Classification ID

Large deviations (60F10) Random graphs (graph-theoretic aspects) (05C80) Martingales with discrete parameter (60G42) Combinatorial probability (60C05) Hypergraphs (05C65) Arithmetic progressions (11B25)

Abstract: Let the random variable $X,:=,e(mathcalH[B])$ count the number of edges of a hypergraph $mathcalH$ induced by a random $m$-element subset $B$ of its vertex set. Focussing on the case that the degrees of vertices in $mathcalH$ vary significantly we prove bounds on the probability that $X$ is far from its mean. It is possible to apply these results to discrete structures such as the set of $k$-term arithmetic progressions in the $1,dots,N$. Furthermore, our main theorem allows us to deduce results for the case $Bsim{B}_p$ is generated by including each vertex independently with probability $p$. In this setting our result on arithmetic progressions extends a result of Bhattacharya, Ganguly, Shao and Zhao cite{BGSZ}. We also mention connections to related central limit theorems.

Recommendations

• Deviation probabilities for arithmetic progressions and other regular discrete structures
• Deviation probabilities for arithmetic progressions and other regular discrete structures
• Upper tails for arithmetic progressions in random subsets
• Upper tail large deviations for arithmetic progressions in a random set
• On the probability of nonexistence in binomial subsets

Cites work

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3405266 (Why is no real title available?)
• scientific article; zbMATH DE number 3198427 (Why is no real title available?)
• Bivariate fluctuations for the number of arithmetic progressions in random sets
• Concentration of multivariate polynomials and its applications
• Deviation probabilities for arithmetic progressions and other regular discrete structures
• Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations
• Martingale Central Limit Theorems
• Moderate deviations of subgraph counts in the Erdős-Rényi random graphs \(G(n,m)\) and \(G(n,p)\)
• Nonlinear large deviations
• On tail probabilities for martingales
• On the Departure from Normality of a Certain Class of Martingales
• On the missing log in upper tail estimates
• On the probability of nonexistence in binomial subsets
• On the rate of convergence in the martingale central limit theorem
• Probability Inequalities for Sums of Bounded Random Variables
• Replica symmetry in upper tails of mean-field hypergraphs
• Some Approximations to the Binomial Distribution Function
• The large deviation principle for the Erdős-Rényi random graph
• The lower tail: Poisson approximation revisited
• Upper tail large deviations for arithmetic progressions in a random set
• Upper tails for arithmetic progressions in random subsets
• Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs
• Upper tails via high moments and entropic stability
• Weighted sums of certain dependent random variables

Cited in

(2)

• Moderate deviations of triangle counts in the Erdős-Rényi random graph G (n, m): the lower tail
• Deviation probabilities for arithmetic progressions and other regular discrete structures

This page was built for publication: Deviation probabilities for arithmetic progressions and irregular discrete structures

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