Balanced two-colorings of finite sets in the cube (Q1113937)

Let \(X=\{x_ 1,...x_ p\}\) be an arbitrary finite set and \({\mathcal Y}=\{Y_ 1,...,Y_ q\}\) be an arbitrary family of subsets of X. The author considers the discrepancy \[ disc {\mathcal Y}=disc({\mathcal Y},X)=\min_{f}\max_{Y\in {\mathcal Y}}| \sum_{x\in Y}f(x)|, \] where the minimum is taken over all 2-colourings f: \(X\to \{-1,+1\}\). Suppose that there is a second family \({\mathcal Z}=\{Z_ 1,Z_ 2,...\}\) of subsets of X such that \((i)\quad \max_{x\in X}card\{Y\in {\mathcal Y}:\quad x\in Y\}\leq d;\) (ii) every \(Y\in {\mathcal Y}\) can be represented as the union of at most m disjoint elements of \({\mathcal Z}\). The main result is an upper bound of disc \({\mathcal Y}\) in terms of p,q,d and m. The proof is mainly probabilistic. The result is applied to construct upper bounds in the theory of point distributions.