The set system discrepancy of a finite family 
of subsets
of a finite set 
is the smallest possible maximum absolute imbalance obtained
by assigning a sign 
to each element 
. For 
, it is
 |
The discrepancy of the empty family is defined to be zero. Equivalently, this is the discrepancy of a hypergraph
with vertex set 
and hyperedges 
(Beck and Fiala 1981, Spencer 1985).
Index the elements as 
and the subsets as
. With rows indexed by the subsets
and columns by the elements, the incidence
matrix 
has 
when 
and zero otherwise. The same quantity is
 |
where 
and 
is the infinity norm. The Beck-Fiala
conjecture concerns families in which each element
occurs in at most a prescribed number of subsets. six
standard deviations suffice theorem concerns 
subsets of an 
-element set.
