2 added 68 characters in body

Here's another problem that is equivalent to this one (see http://www.cs.huji.ac.il/~nati/PAPERS/gotsman_equivalence.pdf):

Consider a 2-coloring of the vertices of the n-dimensional hypercube. We say that it has a monochromatic k-star if there exists a vertex that is colored by the same color as at least k of its neighbors. Since the Hypercube is bipartite we can have a coloring without even a monochromatic 1-star -- this coloring will be exactly balanced (i.e. exactly half of the vertices get each color). What about non-balanced colorings? Define s(n) to be the largest number so that every non-balanced coloring of the n-dimensional hypercube contains a monochromatic s(n)-star. It turns out that s(n) is equal to the minimum possible sensitivity of a Boolean function of degree exactly n. [The basic idea is to look at the product of the coloring (viewed as {-1,1}) with the parity function on the n bits. The non-balancedness translates to full degree and the k-star translates to sensitivity k.]

A related problem defines r(n) to be the largest number so that every non-balanced coloring of the n-dimensional hypercube contains a r(n)-star of the majority color. This was studied by Chung, Furedi, Graham, and Seymour in 1988 (see http://www.math.ucsd.edu/~sbutler/ron/88_06_induced_cube.pdf ) who give essentially the same bounds as known for s(n). Thus it is known that log n <= r(n) <= s(n) <= sqrt(n), and the conjecture is that both are at least n^a for some a>0.

1

Here's another problem that is equivalent to this one (see http://www.cs.huji.ac.il/~nati/PAPERS/gotsman_equivalence.pdf):

Consider a 2-coloring of the vertices of the n-dimensional hypercube. We say that it has a monochromatic k-star if there exists a vertex that is colored by the same color as at least k of its neighbors. Since the Hypercube is bipartite we can have a coloring without even a monochromatic 1-star -- this coloring will be exactly balanced (i.e. exactly half of the vertices get each color). What about non-balanced colorings? Define s(n) to be the largest number so that every non-balanced coloring of the n-dimensional hypercube contains a monochromatic s(n)-star. It turns out that s(n) is equal to the minimum possible sensitivity of a Boolean function of degree exactly n. [The basic idea is to look at the product of the coloring (viewed as {-1,1}) with the parity function on the n bits. The non-balancedness translates to full degree and the k-star translates to sensitivity k.]

A related problem defines r(n) to be the largest number so that every non-balanced coloring of the n-dimensional hypercube contains a r(n)-star of the majority color. This was studied by Chung, Furedi, Graham, and Seymour in 1988 who give essentially the same bounds as known for s(n). Thus it is known that log n <= r(n) <= s(n) <= sqrt(n), and the conjecture is that both are at least n^a for some a>0.