00-27   Berichtsreihe des Mathematischen Seminars der Universität Kiel

Benjamin Doerr:

Discrepancy in Different Numbers of Colors

In this article we investigate the interrelation between the discrepancies of a given hypergraph in different numbers of colors. Being an extreme example we determine the multi-color discrepancies of the $k$--balanced hypergraph $\HH_{nk}$ on partition classes of (equal) size $n$. Let $c,k,n \in \N$. Set $k_0 := k \mod c$ and $b_{nkc} := \left(n-\left\lfloor \frac{n}{\left\lceil \frac{c}{k} \right\rceil}\right\rfloor\right)\frac{k}{c} $. For the discrepancy in $c$ colors we show $$b_{nk_0c} \le \disc(\HH_{nk},c) < b_{nk_0c} + 1,$$ if $k_0 \neq 0$, and $\disc(\HH_{nk},c) = 0$, if $c$ divides $k$. This shows that in general there is little correlation between the discrepancies of $\HH_{nk}$ in different numbers of colors. If $c$ divides $k$ though, $\disc(\HH,c) \le \frac k c \disc(\HH,k)$ holds for any hypergraph $\HH$.

Mathematics Subject Classification (1991): Primary 11K38, Secondary 05C15

Bibliographical note: Discrete Mathematics, 250 (2002), 63-70.

Keywords: Discrepancy, hypergraph coloring

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