We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.
MiS Preprint
1/2006
Discrepancy of Symmetric Products of Hypergraphs
Benjamin Doerr, Michael Gnewuch and Nils Hebbinghaus
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) \leq 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)$.
