Benjamin Doerr, Michael Gnewuch, Nils Hebbinghaus:

Discrepancy of Products of Hypergraphs

For a hypergraph $\HH = (V,\EE)$, its $d$--fold symmetric product is $\Delta^d \HH = (V^d,\{E^d ¦ E \in \EE\})$. 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 \HH,2) \le \disc(\HH,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 \HH,c) = \Omega_d(\disc(\HH,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 $\HH^d$, which satisfies $\disc(\HH^d,c) = O_{c,d}(\disc(\HH,c)^d)$.

Mathematics Subject Classification (1991): 11K38

Bibliographical note: Electronic Journal of Combinatorics, Vol. 13, Research Paper 40, April 2006

Keywords: Discrepancy, hypergraph, Ramsey theory

Mail an Jens Burmeister

[Thu Feb 19 18:56:36 2009]

Impressum