Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInteger colorings with no rainbow 3-term arithmetic progression
368
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper, we study the rainbow ErdH{o}s-Rothschild problem with respect to 3-term arithmetic progressions. We obtain the asymptotic number of $r$-colorings of $[n]$ without rainbow 3-term arithmetic progressions, and we show that the typical colorings with this property are 2-colorings. We also prove that $[n]$ attains the maximum number of rainbow 3-term arithmetic progression-free $r$-colorings among all subsets of $[n]$. Moreover, the exact number of rainbow 3-term arithmetic progression-free $r$-colorings of $mathbb{Z}_p$ is obtained, where $p$ is any prime and $mathbb{Z}_p$ is the cyclic group of order $p$.
rate research
Read More
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 determine primitive solutions to the equation $(x-r)^2 + x^2 + (x+r)^2 = y^n$ for $1 le r le 5,000$, making use of a factorization argument and the Primitive Divisors Theorem due to Bilu, Hanrot and Voutier.
For fixed positive integers $r, k$ and $ell$ with $1 leq ell < r$ and an $r$-uniform hypergraph $H$, let $kappa (H, k,ell)$ denote the number of $k$-colorings of the set of hyperedges of $H$ for which any two hyperedges in the same color class intersect in at least $ell$ elements. Consider the function $KC(n,r,k,ell)=max_{Hin{mathcal H}_{n}} kappa (H, k,ell) $, where the maximum runs over the family ${mathcal H}_n$ of all $r$-uniform hypergraphs on $n$ vertices. In this paper, we determine the asymptotic behavior of the function $KC(n,r,k,ell)$ for every fixed $r$, $k$ and $ell$ and describe the extremal hypergraphs. This variant of a problem of ErdH{o}s and Rothschild, who considered edge colorings of graphs without a monochromatic triangle, is related to the ErdH{o}s--Ko--Rado Theorem on intersecting systems of sets [Intersection Theorems for Systems of Finite Sets, Quarterly Journal of Mathematics, Oxford Series, Series 2, {bf 12} (1961), 313--320].
In Martin Gardners October, 1976 Mathematical Games column in Scientific American, he posed the following problem: What is the smallest number of [queens] you can put on a board of side n such that no [queen] can be added without creating three in a row, a column, or a diagonal? We use the Combinatorial Nullstellensatz to prove that this number is at least n, except in the case when n is congruent to 3 modulo 4, in which case one less may suffice. A second, more elementary proof is also offered in the case that n is even.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
