Skip to Main content Skip to Navigation
Conference papers

Discrepancy of 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 $\textrm{disc}(\Delta^d \mathcal{H},2) \leq \textrm{disc}(\mathcal{H},2)$ proven for all $d$ in [B. Doerr, A. Srivastav, and P. Wehr, Discrepancy of Cartesian 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 $\textrm{disc}(\Delta^d \mathcal{H},c) = \Omega_d(\textrm{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 $\textrm{disc}(\mathcal{H}^d,c) = O_{c,d}(\textrm{disc}(\mathcal{H},c)^d)$.
Complete list of metadata

Cited literature [3 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 2:59:39 PM
Last modification on : Friday, January 7, 2022 - 3:14:02 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:14:36 AM


Publisher files allowed on an open archive




Benjamin Doerr, Michael Gnewuch, Nils Hebbinghaus. Discrepancy of Products of Hypergraphs. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.323-328, ⟨10.46298/dmtcs.3463⟩. ⟨hal-01184452⟩



Record views


Files downloads