Rainbow AP(4) in an almost equinumerous coloring

Importance: Medium ✭✭
Author(s): Conlon, David
Subject: Combinatorics
Recomm. for undergrads: no
Posted by: vjungic
on: July 20th, 2007
Problem   Do 4-colorings of $ \mathbb{Z}_{p} $, for $ p $ a large prime, always contain a rainbow $ AP(4) $ if each of the color classes is of size of either $ \lfloor p/4\rfloor $ or $ \lceil p/4\rceil $?

It is known that there are equinumerous colorings of $ \mathbb{Z}_{4m} $ (i.e. colorings of $ \mathbb{Z}_{4m} $ for some $ m $ such that each color occurs $ m $ times) within which we cannot find rainbow arithmetic progressions of length $ 4 $. ([CJR])


*[C] David Conlon, Rainbow solutions of linear equations over $ \mathbb{Z}_p $, Discrete Mathematics, 306 (2006) 2056 - 2063.

[CJR] David Conlon, Veselin Jungic, Rados Radoicic, On the existence of rainbow 4-term arithmetic progressions, Graphs and Combinatorics, 23 (2007), 249-254

* indicates original appearance(s) of problem.

Tight hypergraphs

It deservs to be mentioned that in any $ 3 $-colouring of $ {\mathbb Z}_p^*/{\mathbb Z}_3^* $, the equation $ x+y=z $, have an heterochromatic (rainbow) solution; here, $ {\mathbb Z}_p^* $ denotes the multiplicative group of the field $ {\mathbb Z}_p $.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.