Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDeviation probabilities for arithmetic progressions and other regular discrete structures
79
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let the random variable $X, :=, e(mathcal{H}[B])$ count the number of edges of a hypergraph $mathcal{H}$ induced by a random $m$ element subset $B$ of its vertex set. Focussing on the case that $mathcal{H}$ satisfies some regularity condition 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 cyclic group $mathbb{Z}_N$. Furthermore, we show that our main theorem is essentially best possible and we deduce results for the case $Bsim B_p$ is generated by including each vertex independently with probability $p$.
rate research
Read More
Celebrated theorems of Roth and of Matouv{s}ek and Spencer together show that the discrepancy of arithmetic progressions in the first $n$ positive integers is $Theta(n^{1/4})$. We study the analogous problem in the $mathbb{Z}_n$ setting. We asymptotically determine the logarithm of the discrepancy of arithmetic progressions in $mathbb{Z}_n$ for all positive integer $n$. We further determine up to a constant factor the discrepancy of arithmetic progressions in $mathbb{Z}_n$ for many $n$. For example, if $n=p^k$ is a prime power, then the discrepancy of arithmetic progressions in $mathbb{Z}_n$ is $Theta(n^{1/3+r_k/(6k)})$, where $r_k in {0,1,2}$ is the remainder when $k$ is divided by $3$. This solves a problem of Hebbinghaus and Srivastav.
In this paper, we investigate the anti-Ramsey (more precisely, anti-van der Waerden) properties of arithmetic progressions. For positive integers $n$ and $k$, the expression $aw([n],k)$ denotes the smallest number of colors with which the integers ${1,ldots,n}$ can be colored and still guarantee there is a rainbow arithmetic progression of length $k$. We establish that $aw([n],3)=Theta(log n)$ and $aw([n],k)=n^{1-o(1)}$ for $kgeq 4$. For positive integers $n$ and $k$, the expression $aw(Z_n,k)$ denotes the smallest number of colors with which elements of the cyclic group of order $n$ can be colored and still guarantee there is a rainbow arithmetic progression of length $k$. In this setting, arithmetic progressions can wrap around, and $aw(Z_n,3)$ behaves quite differently from $aw([n],3)$, depending on the divisibility of $n$. As shown in [Jungic et al., textit{Combin. Probab. Comput.}, 2003], $aw(Z_{2^m},3) = 3$ for any positive integer $m$. We establish that $aw(Z_n,3)$ can be computed from knowledge of $aw(Z_p,3)$ for all of the prime factors $p$ of $n$. However, for $kgeq 4$, the behavior is similar to the previous case, that is, $aw(Z_n,k)=n^{1-o(1)}$.
In this note we are interested in the problem of whether or not every increasing sequence of positive integers $x_1x_2x_3...$ with bounded gaps must contain a double 3-term arithmetic progression, i.e., three terms $x_i$, $x_j$, and $x_k$ such that $i + k = 2j$ and $x_i + x_k = 2x_j$. We consider a few variations of the problem, discuss some related properties of double arithmetic progressions, and present several results obtained by using RamseyScript, a high-level scripting language.
We show the existence of regular combinatorial objects which previously were not known to exist. Specifically, for a wide range of the underlying parameters, we show the existence of non-trivial orthogonal arrays, t-designs, and t-wise permutations. In all cases, the sizes of the objects are optimal up to polynomial overhead. The proof of existence is probabilistic. We show that a randomly chosen structure has the required properties with positive yet tiny probability. Our method allows also to give rather precise estimates on the number of objects of a given size and this is applied to count the number of orthogonal arrays, t-designs and regular hypergraphs. The main technical ingredient is a special local central limit theorem for suitable lattice random walks with finitely many steps.
We present results on the existence of long arithmetic progressions in the Thue-Morse word and in a class of generalised Thue-Morse words. Our arguments are inspired by van der Waerdens proof for the existence of arbitrary long monochromatic arithmetic progressions in any finite colouring of the (positive) integers.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
