Electronic Journal Article
@Article
Zeitschriftenartikel in einem e-Journal



Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Doerr, Benjamin
Gnewuch, Michael
Hebbinghaus, Nils

dblp
dblp
dblp

Not MPG Author(s):

Gnewuch, Michael

BibTeX cite key*:

SymHyp2006

Title

Title*:

Discrepancy of Symmetric Products of Hypergraphs


v13i1r40.pdf (119.35 KB)

Journal

Journal Title*:

The Electronic Journal of Combinatorics

Journal's URL:

http://www.combinatorics.org/

Download URL
for the article:

http://arxiv.org/PS_cache/math/pdf/0604/0604438.pdf

Language:

English

Publisher

Publisher's
Name:

International Press

Publisher's URL:


Publisher's
Address:

Somerville

ISSN:

1077-8926

Vol, No, Year, pp.

Volume:

13

Number:


Month:


Year*:

2006

Pages:

1-12

Number of VG Pages:

12

Sequence Number:

40

DOI:


Abstract, Links, (C)

Note:


(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 ${disc}(\Delta^d {\mathcal H},2) \le {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 ${disc}(\Delta^d {\mathcal H},c) = \Omega_d({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 ${disc}({\mathcal H}^d,c) = O_{c,d}({disc}({\mathcal H},c)^d)$.

URL for the Abstract:

http://www.combinatorics.org/Volume_13/Abstracts/v13i1r40.html

Categories / Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


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:

@MISC{SymHyp2006,
AUTHOR = {Doerr, Benjamin and Gnewuch, Michael and Hebbinghaus, Nils},
TITLE = {Discrepancy of Symmetric Products of Hypergraphs},
JOURNAL = {The Electronic Journal of Combinatorics},
PUBLISHER = {International Press},
YEAR = {2006},
VOLUME = {13},
PAGES = {1--12},
ADDRESS = {Somerville},
ISBN = {1077-8926},
}


Entry last modified by Christine Kiesel, 02/14/2007
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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)
Mathias Bader
Created
11/22/2006 05:41:17 PM
Revisions
11.
10.
9.
8.
7.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
14.02.2007 10:07:55
14.02.2007 10:07:10
07.02.2007 09:33:44
07.02.2007 08:42:34
07.02.2007 08:40:51
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
v13i1r40.pdf