# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Discrepancy of Products of Hypergraphs

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Doerr, B., & Hebbinghaus, N. (2005). Discrepancy of Products of Hypergraphs. In
*2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)*
(pp. 323-328). Nancy, France: DMTCS.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2640-C

##### 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}) }$}.