Search

MiS Preprint Repository

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

Received:
Jan 9, 2006
Published:
Jan 9, 2006
MSC Codes:
11K38
Keywords:
discrepancy, hypergraphs, ramsey theory

Related publications

inJournal
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