de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Discrepancy of Products of Hypergraphs

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44338

Doerr,  Benjamin
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44598

Hebbinghaus,  Nils
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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