Rainbow arithmetic progressions

DOI10.4310/JOC.2016.V7.N4.A3MaRDI QIDQ344442zbMATH OpenFDO

Authors Steve Butler, Craig Erickson, Leslie Hogben, Kirsten Hogenson, Lucas Kramer, Richard L. Kramer, Jephian Chin-Hung Lin, Ryan R. Martin, Derrick Stolee, Nathan Warnberg, Michael Young

Publication date 22 November 2016

Published in Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

anti-Ramseyarithmetic progressionBehrend constructionrainbow coloring

Mathematics Subject Classification ID

Ramsey theory (05D10) Arithmetic progressions (11B25) Inverse problems of additive number theory, including sumsets (11P70)

Abstract: 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(logn)$ and $aw([n],k)=n^{1-o(1)}$ for $kgeq4$. 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 [Jungi'c et al., extit{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 $kgeq4$, the behavior is similar to the previous case, that is, $aw(Z_n,k)=n^{1-o(1)}$.

Recommendations

• Rainbow arithmetic progressions in finite abelian groups
• On rainbow arithmetic progressions
• Rainbow Arithmetic Progressions and Anti-Ramsey Results
• Anti-van der Waerden numbers of 3-term arithmetic progression
• Integer colorings with no rainbow 3-term arithmetic progression

Cited in

(20)

• On rainbow arithmetic progressions
• Rainbow arithmetic progressions in finite abelian groups
• On sequences covering all rainbow k-progressions
• Long rainbow arithmetic progressions
• Arithmetic progressions, quasi progressions, and Gallai-Ramsey colorings
• Integer colorings with no rainbow 3-term arithmetic progression
• Integer colorings with no rainbow \(k\)-term arithmetic progression
• Anti-van der Waerden numbers on graphs
• Anti-van der Waerden numbers of 3-term arithmetic progression
• Rainbow numbers of \([n]\) for \(\sum_{i=1}^{k-1}x_i=x_k\)
• Rainbow Arithmetic Progressions and Anti-Ramsey Results
• scientific article; zbMATH DE number 2124068 (Why is no real title available?)
• Rainbow numbers for \(x_1+x_2=kx_3\) in \(\mathbb{Z}_n\)
• Rainbow numbers of \(\mathbb{Z}_n\) for \(a_1x_1+a_2x_2+a_3x_3 =b\)
• Anti-van der Waerden numbers of graph products
• Anti-van der Waerden numbers of graph products of cycles
• An unsure note on an un-Schur problem
• Rainbow-free colorings and rainbow numbers for x-y=z^k
• Hitting sets and colorings of hypergraphs
• Avoiding arithmetic progressions in cyclic groups

This page was built for publication: Rainbow arithmetic progressions

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