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

https://hal.inria.fr/hal-01184452
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

File

dmAE0163.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

87

Files downloads

410