2018/02/09 by Alese, Leonardo, Lendl, Stefan, Tabatabai, Paul
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1802.03285
Let ac(n,k) denote the smallest positive integer with the property that there exists an n-colouring f of \1,…,ac(n,k)\ such that for every k-subset R ⊆ \1, …, n\ there exists an (arithmetic) k-progression A in \1,…,ac(n,k)\ with \f(a) : a ∈ 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).