Open Problem Garden

Author(s): Conlon

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$ ?

Keywords: arithmetic progression; rainbow

Posted by vjungic
updated September 1st, 2007

1 comment

Conlon, David

sorting

Theoretical Comp. Sci. » Complexity

Linear-size circuits for stable $0,1 < 2$ sorting? ★★

Author(s): Regan

Problem Can $O(n)$ -size circuits compute the function $f$ on $\{0,1,2\}^*$ defined inductively by $f(\lambda) = \lambda$ , $f(0x) = 0f(x)$ , $f(1x) = 1f(x)$ , and $f(2x) = f(x)2$ ?