AnLpVersion of the Beck–Fiala Conjecture

Beck and Fiala conjectured in 1981 that for any set system S of maximum degreeton a finite ground setX, a coloring χ:X → {−1,+1} exists such that ∣χ(S)∣ = O(t) holds for allS∈ S , where χ(S) = ∑x∈Sχ(x). We prove a weaker statement, namely that for any fixedp ≥ 1, a coloring χ exists such that thepth degree average of ∣χ(S)∣ overS∈S isO(t) . The result also holds if each set is assigned a nonnegative real weight and thepth degree average is taken with these weights (with χ depending on the weights).