1Departament de Matemàtiques, Universitat Politècnica de Catalunya, Barcelona, Spain 2Departamento de Matemàtica, PUC-Rio, Gávea, Rio de Janeiro, Brazil
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 679-683
Citer cet article
Gonzalo Fiz Pontiveros; Simon Griffiths; Matheus Secco; Oriol Serra; Gonzalo Fiz Pontiveros; Simon Griffiths; Matheus Secco; Oriol Serra. Deviation probabilities for arithmetic progressions and other regular discrete structures. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 679-683. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a49/
@article{AMUC_2019_88_3_a49,
author = {Gonzalo Fiz Pontiveros and Simon Griffiths and Matheus Secco and Oriol Serra and Gonzalo Fiz Pontiveros and Simon Griffiths and Matheus Secco and Oriol Serra},
title = { Deviation probabilities for arithmetic progressions and other regular discrete structures},
journal = {Acta mathematica Universitatis Comenianae},
pages = {679--683},
year = {2019},
volume = {88},
number = {3},
url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a49/}
}
TY - JOUR
AU - Gonzalo Fiz Pontiveros
AU - Simon Griffiths
AU - Matheus Secco
AU - Oriol Serra
AU - Gonzalo Fiz Pontiveros
AU - Simon Griffiths
AU - Matheus Secco
AU - Oriol Serra
TI - Deviation probabilities for arithmetic progressions and other regular discrete structures
JO - Acta mathematica Universitatis Comenianae
PY - 2019
SP - 679
EP - 683
VL - 88
IS - 3
UR - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a49/
ID - AMUC_2019_88_3_a49
ER -
%0 Journal Article
%A Gonzalo Fiz Pontiveros
%A Simon Griffiths
%A Matheus Secco
%A Oriol Serra
%A Gonzalo Fiz Pontiveros
%A Simon Griffiths
%A Matheus Secco
%A Oriol Serra
%T Deviation probabilities for arithmetic progressions and other regular discrete structures
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 679-683
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a49/
%F AMUC_2019_88_3_a49
Let $\HH$ be a $k$-uniform hypergraph on a vertex set $V$ and $B_m$ be a uniformly sampled $m$-set from $V$. Set $X$ to be the random variable given by the number of edges induced by the set $B_m$. We provide tight upperbounds (up to a constant in the exponent) for the tail distribution of $X-\exn{}{X}$ for a wide range of deviations, provided some near regularity conditions are satisfied by the hypergraph $\HH$. In particular, the bounds may be applied to the setting of arithmetic progressions and more generally to solutions of linear systems.
