\input zb-basic
\input zb-ioport
\iteman{io-port 05192007}
\itemau{Oh, Jinsoo; Moon, Byung-Ro}
\itemti{On the $L_{2}$-discrepancy.}
\itemso{Discrete Appl. Math. 155, No. 15, 2039-2042 (2007).}
\itemab
In this article, the following problem is considered. Let $\mathcal{S}$ be a family of subsets of a finite set $V$ and let $\chi:V\rightarrow \{-1,1\}$ be a coloring of $V$. For $S_j\in\mathcal{S}$, let $\chi(S_j):=\sum_{v\in S_j}\chi (v)$ and define the $L_2$-discrepancy of $\mathcal{S}$ with respect to $\chi$ as $$\text{disc}_2(\mathcal{S},\chi):=\biggl(\frac{1}{\vert \mathcal{S} \vert}\sum_j \vert\chi (S_j)\vert^2\biggr)^{1/2}.$$ Furthermore, the $L_2$-discrepancy of $\mathcal{S}$ is defined by $$\text{disc}_2 (\mathcal{S}):=\min_\chi \text{disc}_2 (\mathcal{S},\chi),$$ where the minimum is extended over all colorings $\chi$. The authors of this note discuss a relation of the $L_2$-discrepancy problem to the so called MAX-CUT problem and show two main results. Firstly, it is shown that the $L_2$-discrepancy problem is NP-complete. Moreover, the authors show that there exists a coloring $\chi$ such that $$\biggl(\frac{1}{\vert \mathcal{S} \vert}\sum_j \vert\chi (S_j)\vert^2\biggr)^{1/2}\le\sqrt{\vert V\vert}.$$
\itemrv{Peter Kritzer (Salzburg)}
\itemcc{}
\itemut{Coloring; hypergraph; $L_2$-discrepancy; NP-completeness}
\itemli{doi:10.1016/j.dam.2007.04.021}
\end