Discrepancy of symmetric products of hypergraphs

Benjamin Doerr ; Michael Gnewuch ; Nils Hebbinghaus

The electronic journal of combinatorics, Tome 13 (2006)

Résumé

For a hypergraph ${\cal H} = (V,{\cal E})$, its $d$–fold symmetric product is defined to be $\Delta^d {\cal H} = (V^d,\{E^d |E \in {\cal E}\})$. We give several upper and lower bounds for the $c$-color discrepancy of such products. In particular, we show that the bound ${\rm disc}(\Delta^d {\cal H},2) \le {\rm disc}({\cal 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 ${\rm disc}(\Delta^d {\cal H},c) = \Omega_d({\rm disc}({\cal 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 ${\cal H}^d$, which satisfies ${\rm disc}({\cal H}^d,c) = O_{c,d}({\rm disc}({\cal H},c)^d)$.

Détail

DOI : 10.37236/1066

Classification : 05C65, 11K38