# Discrepancy of Products of Hypergraphs

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 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 $\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)$.
Keywords :
Type de document :
Communication dans un congrès
Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.323-328, 2005, DMTCS Proceedings
Domaine :

Littérature citée [3 références]

https://hal.inria.fr/hal-01184452
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 14 août 2015 - 14:59:39
Dernière modification le : lundi 20 août 2018 - 09:46:01
Document(s) archivé(s) le : dimanche 15 novembre 2015 - 11:14:36

### Fichier

dmAE0163.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01184452, version 1

### Citation

Benjamin Doerr, Michael Gnewuch, Nils Hebbinghaus. Discrepancy of Products of Hypergraphs. Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.323-328, 2005, DMTCS Proceedings. 〈hal-01184452〉

### Métriques

Consultations de la notice

## 380

Téléchargements de fichiers