DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Discrepancy of Products of Hypergraphs

Benjamin Doerr, Michael Gnewuch, Nils Hebbinghaus

Abstract


For a hypergraph H = (V,E), its d--fold symmetric product is Δd H = (Vd,{ Ed | E ∈E }) . We give several upper and lower bounds for the c-color discrepancy of such products. In particular, we show that the bound disc(Δd H,2) ≤disc(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 disc(Δd H,c) = Ωd(disc(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 Hd, which satisfies disc(Hd,c) = Oc,d(disc(H,c)d) .

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional