
arXiv: math/0604438
For a hypergraph ${\cal H} = (V,{\cal E})$, its $d$–fold symmetric product is defined to be $\Delta^d {\cal H} = (V^d,\{E^d |E \in {\cal E}\})$. We give several upper and lower bounds for the $c$-color discrepancy of such products. In particular, we show that the bound ${\rm disc}(\Delta^d {\cal H},2) \le {\rm disc}({\cal H},2)$ proven for all $d$ in [B. Doerr, A. Srivastav, and P. Wehr, Discrepancy of Cartesian 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 ${\rm disc}(\Delta^d {\cal H},c) = \Omega_d({\rm disc}({\cal 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 ${\cal H}^d$, which satisfies ${\rm disc}({\cal H}^d,c) = O_{c,d}({\rm disc}({\cal H},c)^d)$.
Irregularities of distribution, discrepancy, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Hypergraphs, 11K38
Irregularities of distribution, discrepancy, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Hypergraphs, 11K38
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
