Discrepancy of Symmetric Products of Hypergraphs

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

12 pages, no figures

References in corpus (1)

• Ramsey-type results on singletons, co-singletons and monotone sequences in large collections of sets

Cited by in corpus (1)

• A Survey on Hypergraph Products (Erratum)