Deviation probabilities for arithmetic progressions and irregular discrete structures

DOI10.1214/23-EJP1012arXiv2012.09280MaRDI QIDQ6136819FDOQ6136819

Christoph Koch, Simon Griffiths, Matheus Secco

Publication date: 17 January 2024

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

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.

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)

Cites Work

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

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)