Discrepancy of symmetric products of hypergraphs (Q2500959)

Summary: For a hypergraph \({\mathcal H} = (V,{\mathcal E})\), its \(d\)-fold symmetric product is defined to be \(\Delta^d {\mathcal H} = (V^d,\{E^d |E \in {\mathcal E}\})\). We give several upper and lower bounds for the \(c\)-color discrepancy of such products. In particular, we show that the bound \(\text{disc}(\Delta^d {\mathcal H},2) \leq \text{disc}({\mathcal H},2)\) proven for all \(d\) in [\textit{B. Doerr, A. Srivastav} and \textit{P. Wehr}, Discrepancy of Cartesian products of arithmetic progressions, Electron. J. Combin. 11, Research Paper 5, 16 pp. (2004; Zbl 1045.11007)] 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 \(\text{disc}(\Delta^d {\mathcal H},c) = \Omega_d(\text{disc}({\mathcal 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 \({\mathcal H}^d\), which satisfies \(\text{disc}({\mathcal H}^d,c) = O_{c,d}(\text{disc}({\mathcal H},c)^d)\).