99-29   Berichtsreihe des Mathematischen Seminars der Universität Kiel

Geir Agnarsson, Benjamin Doerr, Tomasz Schoen:

Coloring t-dimensional m-Boxes

Call the set $S_1 \times \cdots \times S_t$ $t$--dimensional $m$--box if $S_i=m$ for every $i=1,\dots,t$. Let $R_t(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 $R_t(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 $2$--dimensional $m$--boxes in $[R] \times [R]$ is equal to $\Theta (R^{\frac32})$ for $m$ a constant fraction (less than $\frac{1}{2}$) of $R$.

Mathematics Subject Classification (1991): 05C65, 05D10, 11K38

Bibliographical note: Discrete Mathematics 226, pp. 21-33, 2001

Keywords: Discrepancy, Hypergraphs, Ramsey-Theory

Mail an Jens Burmeister
[Thu Feb 19 18:56:35 2009]
Impressum