 |
|
(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 {${ \textrm{disc}(\Delta ^{d} \mathcal{H},2) {\leq}\textrm{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 {${ \textrm{disc}(\Delta ^{d} \mathcal{H},c) = \Omega_{d}(\textrm{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 {${ \textrm{disc}(\mathcal{H}^{d},c) = O_{c,d}(\textrm{disc}(\mathcal{H},c)^{d}) }$}. |
URL for the Abstract: |
http://www.dmtcs.org/proceedings/abstracts/dmAE0163.abs.html |
Keywords: |
Discrepancy, Hypergraphs, Ramsey Theory |
|
|
|
|
Download
Access Level: |
Public |
|