Finding Patterns Avoiding Many Monochromatic Constellations

Abstract

Given fixed 0 = q ₀ < q ₁ < q ₂ < … < q_k = 1, a constellation in [n] is a scaled translated realization of the q_i with all elements in [n], i.e.,

p, p + q ₁ d, p + q ₂ d, …, p + q _k–1 d, p + d.

We consider the problem of minimizing the number of monochromatic constellations in a two-coloring of [n]. We show how, given a coloring based on a block pattern, to find the number of monochromatic solutions to a lower-order term, and also how experimentally we might find an optimal block pattern. We also show for the case k = 2 that there is always a block pattern that beats random coloring.

Keywords:

• Constellations
• arithmetic progressions
• coloring
• monochromatic solutions
• blocks