Discrepancy of symmetric products of hypergraphs

MaRDI QIDQ2500959zbMATH OpenFDO

Authors Benjamin Doerr, Michael Gnewuch, Nils Hebbinghaus

Publication date 30 August 2006

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0604438, https://eudml.org/doc/130290, http://www.emis.de/journals/EJC/Volume_13/Abstracts/v13i1r40.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Hypergraphs (05C65) Irregularities of distribution, discrepancy (11K38)

Abstract: For a hypergraph $mathcalH=(V,mathcalE)$, its $d$--fold symmetric product is $Delt{a}^{d}mathcalH=(V^d,E^d|EinmathcalE)$. We give several upper and lower bounds for the $c$-color discrepancy of such products. In particular, we show that the bound $disc(Delt{a}^{d}mathcalH,2)ledisc(mathcalH,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(Delt{a}^{d}mathcalH,c)=Omeg{a}_d(disc(mathcalH,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 ${mathcalH}^d$, which satisfies $disc({mathcalH}^d,c)=O_{c,d}(disc(mathcalH,c{)}^d)$.

Review text

Summary: For a hypergraph \({\mathcal H} = (V,{\mathcal E})\), its \(d\)-fold symmetric product is defined to be \(\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 \(\text{disc}(\Delta^d {\mathcal H},2) \leq \text{disc}({\mathcal H},2)\) proven for all \(d\) in [\textit{B. Doerr, A. Srivastav} and \textit{P. Wehr}, Discrepancy of Cartesian products of arithmetic progressions, Electron. J. Combin. 11, Research Paper 5, 16 pp. (2004; Zbl 1045.11007)] 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 \(\text{disc}(\Delta^d {\mathcal H},c) = \Omega_d(\text{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 \(\text{disc}({\mathcal H}^d,c) = O_{c,d}(\text{disc}({\mathcal H},c)^d)\).

Recommendations

• Discrepancy of products of hypergraphs
• Multi-color discrepancies
• Multicolour Discrepancies
• On small \(n\)-uniform hypergraphs with positive discrepancy
• Discrepancy in graphs and hypergraphs

Cited in

(1)

• Discrepancy of products of hypergraphs

This page was built for publication: Discrepancy of symmetric products of hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2500959)