MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Doerr, Benjamin
Hebbinghaus, Nils
dblp
dblp
Not MPG Author(s):
Gnewuch, Michael
Editor(s):
Felsner, Stefandblp
Not MPII Editor(s):
Felsner, Stefan
BibTeX cite key*:
Hebbinghaus2005
Title, Booktitle
Title*:
Discrepancy of Products of Hypergraphs
Booktitle*:
2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Event, URLs
Conference URL::
http://www.math.tu-berlin.de/EuroComb05/
Downloading URL:
http://www.dmtcs.org/proceedings/abstracts/dmAE0163.abs.html
Event Address*:
Berlin, Germany
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
5 September 2005
Event End Date:
9 September 2005
Publisher
Name*:
DMTCS
URL:
http://www.dmtcs.org/dmtcs-ojs/
Address*:
Nancy, France
Type:
Vol, No, Year, pp.
Series:
DMTCS Proceedings
Volume:
AE
Number:
Month:
September
Pages:
323-328
Year*:
2005
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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}) }$}.
URL for the Abstract:
http://www.dmtcs.org/proceedings/abstracts/dmAE0163.abs.html
Keywords:
Discrepancy, Hypergraphs, Ramsey Theory
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Hebbinghaus2005,
AUTHOR = {Doerr, Benjamin and Hebbinghaus, Nils},
EDITOR = {Felsner, Stefan},
TITLE = {Discrepancy of Products of Hypergraphs},
BOOKTITLE = {2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
PUBLISHER = {DMTCS},
YEAR = {2005},
VOLUME = {AE},
PAGES = {323--328},
SERIES = {DMTCS Proceedings},
ADDRESS = {Berlin, Germany},
MONTH = {September},
}


Entry last modified by Christine Kiesel, 06/06/2006
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Nils Hebbinghaus
Created
04/06/2006 05:25:16 PM
Revisions
8.
7.
6.
5.
4.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
06.06.2006 10:37:21
02.06.2006 14:11:01
02.06.2006 13:57:27
02.06.2006 13:51:24
02.06.2006 13:50:42