hide
Free keywords:
-
Abstract:
For a hypergraph {${\mathcal{H} = (V,\mathcal{E})}$}, its {${d}$}--fold
symmetric product is {${ \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 {${ \textrm{disc}(\Delta ^{d} \mathcal{H},2)
{\leq}\textrm{disc}(\mathcal{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 {${ \textrm{disc}(\Delta ^{d}
\mathcal{H},c) = \Omega_{d}(\textrm{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 {${ \textrm{disc}(\mathcal{H}^{d},c) =
O_{c,d}(\textrm{disc}(\mathcal{H},c)^{d}) }$}.
