Discrepancy of Symmetric Products of Hypergraphs

Benjamin Doerr, Michael Gnewuch, and Nils Hebbinghaus

Contact the author: Please use for correspondence this email.
Submission date: 09. Jan. 2006
Pages: 16
published in: The electronic journal of combinatorics, 13 (2006) 1, art-no. R40 
Bibtex
MSC-Numbers: 11K38
Keywords and phrases: discrepancy, hypergraphs, ramsey theory
Download full preprint: PDF (555 kB), PS ziped (172 kB)

Abstract:
For a hypergraph , its d-fold symmetric product is . We give several upper and lower bounds for the c-color discrepancy of such products. In particular, we show that the bound 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 . Apart from constant factors (depending on c and d), in these cases the symmetric product behaves no better than the general direct product , which satisfies .