Journal of Combinatorics

Volume 9 (2018)

Number 4

On sequences covering all rainbow $k$-progressions

Pages: 739 – 745

DOI: https://dx.doi.org/10.4310/JOC.2018.v9.n4.a9

Authors

Leonardo Alese (Institute of Geometry, Graz University of Technology, Graz, Austria)

Stefan Lendl (Institute of Discrete Mathematics, Graz University of Technology, Graz, Austria)

Paul Tabatabai (Graz University of Technology, Graz, Austria)

Abstract

Let $ac(n, k)$ denote the smallest positive integer with the property that there exists an $n$-colouring $f$ of $\{ 1, \dotsc , ac(n, k) \}$ such that for every $k$-subset $R \subseteq \{ 1, \dotsc , n \}$ there exists an (arithmetic) $k$-progression $A$ in $\{ 1, \dotsc, ac(n, k) \}$ with $\{ f(a) : a \subset A \} = R$.

Determining the behaviour of the function $ac(n, k)$ is a previously unstudied problem. We use the first moment method to give an asymptotic upper bound for $ac(n, k)$ for the case $k = o(n^{1/5})$.

Keywords

rainbow arithmetic progression, colouring, covering, arithmetic progression, probabilistic method, universal sequence

Full Text (PDF format)

Leonardo Alese and Stefan Lendl acknowledge the support of the Austrian Science Fund (FWF): W1230, Doctoral Program “Discrete Mathematics”.

Stefan Lendl acknowledges the support of SFB-Transregio 109 “Discretization in Geometry & Dynamics” funded by DFG and FWF (I 2978).

Received 15 February 2018

Published 7 December 2018