MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

MiS Preprint

Discrepancy of Symmetric Products of Hypergraphs

Benjamin Doerr, Michael Gnewuch and Nils Hebbinghaus


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)$.

Jan 9, 2006
Jan 9, 2006
MSC Codes:
discrepancy, hypergraphs, ramsey theory

Related publications

2006 Journal Open Access
Benjamin Doerr, Michael Gnewuch and Nils Hebbinghaus

Discrepancy of symmetric products of hypergraphs

In: The electronic journal of combinatorics, 13 (2006) 1, R40