Balanced two-colorings of finite sets in the cube (Q1113937): Difference between revisions
From MaRDI portal
Latest revision as of 11:08, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Balanced two-colorings of finite sets in the cube |
scientific article |
Statements
Balanced two-colorings of finite sets in the cube (English)
0 references
1989
0 references
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.
0 references
combinatorial discrepancy
0 references
2-colourings
0 references
upper bound
0 references
upper bounds
0 references
point distributions
0 references
0 references