Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Discrepancy of Symmetric Products of Hypergraphs. | Discrepancy of Symmetric Products of Hypergraphs Benjamin Doerr Michael Gnewuch Nils Hebbinghaus Submitted Dec 15 2005 Accepted Mar 28 2006 Published Apr 24 2006 Mathematics Subject Classification 11K38 Abstract For a hypergraph H V E its d-fold symmetric product is defined to be AdH Vd Ed E 2 Eg . We give several upper and lower bounds for the c-color discrepancy of such products. In particular we show that the bound disc AdH 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 AdH C Qd 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 . 1 Introduction We investigate the discrepancy of certain products of hypergraphs. In 3 Srivastav Wehr and the first author noted the following. For a hypergraph H V E define the d-fold direct product and the d-fold symmetric product by Hd Vd E1 X---X Ed Ei eE AdH Vd Ed E eE Max-Planck-Institut fur Informatik Saarbriicken Germany. hnstitut fur Informatik und Praktische Mathematik Christian-Albrechts-Universitat zu Kiel Germany. Supported by the Deutsche Forschungsgemeinschaft Grant SR7 10-1. Wax-Planck-Institut fur Informatik Stuhlsatzenhausweg 85 66123 Saarbriicken Germany Tel. 49-681 9325-109 E-mail nhebbing@. corresponding author THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R40 1 Then for the two-color discrepancy disc H min max VA -1 1 E2E x v2E we have disc Hd disc AdH disc H d disc H . In this paper we show that the situation is more complicated for discrepancies in more than two colors. In particular it depends highly on the dimension d and the number of colors whether the .
