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: Goto entry point

 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:

 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},