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

Font Size:
DMTCS Conference vol AE (2005), pp. 323-328

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

### DMTCS Conference Volume AE (2005), pp. 323-328

author: Benjamin Doerr, Michael Gnewuch and Nils Hebbinghaus Discrepancy of Products of Hypergraphs discrepancy, hypergraphs, Ramsey theory For a hypergraph H = (V, E ) , its d --fold symmetric product is Δ d H = (V d ,{ E d | 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 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 (Δ 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 H d , which satisfies disc ( H d ,c) = O c,d ( disc ( H ,c) d ) . If your browser does not display the abstract correctly (because of the different mathematical symbols) you may look it up in the PostScript or PDF files. Benjamin Doerr and Michael Gnewuch and Nils Hebbinghaus (2005), Discrepancy of Products of Hypergraphs, in 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), Stefan Felsner (ed.), Discrete Mathematics and Theoretical Computer Science Proceedings AE, pp. 323-328 For a corresponding BibTeX entry, please consider our BibTeX-file. dmAE0163.ps.gz (64 K) dmAE0163.ps (151 K) dmAE0163.pdf (149 K)