An \(L_p\) version of the Beck-Fiala conjecture
\textit{J. Beck} and \textit{P. Fiala} [Discrete Appl. Math. 3, 1--8 (1981; Zbl 0473.05046)] conjectured that for any set system \({\mathcal S}\) of maximum degree \(t\) on a finite ground set \(X\), a coloring \(\chi:X\to\{-1, +1\}\) exists such that \(|\chi(S) |=O(\sqrt t)\) holds for all \(S\in {\mathcal S}\), where \(\chi(S)=\sum_{x\in S}\chi(x)\). The author proves the weaker statement, namely that for any fixed \(p\geq 1\), a coloring exists such that the \(p\)-th degree average of \(|\chi(S)|\) over \(S\in{\mathcal S}\) is \(O(\sqrt t)\).
scientific article; zbMATH DE number 1212319