Coloring t-dimensional m-Boxes Original Research Article

Call the set S1×⋯×St t-dimensional m-box if |Si|=m for every i=1,…,t. Let Rt(m,r) be the smallest integer R such that for every r-coloring of t-fold cartesian product of [R], one can find a monochromatic t-dimensional m-box. We give a lower and an upper bound for Rt(m,r). We also consider the discrepancy problem connected to this set-system. Among other bounds, we prove that the discrepancy of the hypergraph of all one-dimensional m-boxes in [R]×[R] is equal to Θ(R3/2) for m a constant fraction (less than 12) of R.