Discrepancy of Symmetric Products of Hypergraphs

Details Discrepancy of Symmetric Products of Hypergraphs Discrepancy of Symmetric Products of Hypergraphs

2006-04-20

arxiv.org/abs/math/0604438v1

The Electronic Journal of Combinatorics 13 (2006), #R40

Mathematics

Combinatorics

12 pages, no figures

Scientific paper

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)$.

Affiliated with

Also associated with

No associations

Rating

Discrepancy of Symmetric Products of Hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Discrepancy of Symmetric Products of Hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Discrepancy of Symmetric Products of Hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-67047