MiS Preprint Repository

For a hypergraph $\mathcal{H}=(V,\mathcal{E})$, its $d$--fold symmetric product is ${\mathrm{\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({\mathrm{\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({\mathrm{\Delta }}^d\mathcal{H},c)={\mathrm{\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)$.