hide
Free keywords:
-
Abstract:
For a hypergraph ${\mathcal H} = (V,{\mathcal E})$, its $d$--fold symmetric
product is $\Delta^d {\mathcal H} = (V^d,\{E^d |E \in {\mathcal E}\})$. We give
several upper and lower bounds for the $c$-color discrepancy of such products.
In particular, we show that the bound ${disc}(\Delta^d {\mathcal H},2) \le
{disc}({\mathcal H},2)$ proven for all $d$ in [B. Doerr, A. Srivastav, and P.
Wehr, Discrepancy of {C}artesian products of arithmetic progressions, Electron.
J. Combin. 11(2004), Research Paper 5, 16 pp.] cannot be extended to more than
$c = 2$ colors. In fact, for any $c$ and $d$ such that $c$ does not divide
$d!$, there are hypergraphs having arbitrary large discrepancy and
${disc}(\Delta^d {\mathcal H},c) = \Omega_d({disc}({\mathcal H},c)^d)$. Apart
from constant factors (depending on $c$ and $d$), in these cases the symmetric
product behaves no better than the general direct product ${\mathcal H}^d$,
which satisfies ${disc}({\mathcal H}^d,c) = O_{c,d}({disc}({\mathcal H},c)^d)$.
