Linear versus hereditary discrepancy (Q2567408)

The linear discrepancy of an \(m \times n\) matrix \(A\) is \(\max_{p \in [0,1]^n} \min_{q \in \{0,1\}^n} \| A(p-q)\| _\infty\). The authors show that the linear discrepancy of a totally unimodular matrix having \(n\) columns is at most \(\frac n {n+1}\). This result has been independently obtained by \textit{B. Dörr} [Lattice approximation and linear discrepancy of totally unimodular matrices, Proc. 12th annual ACM-SIAM Symp. on discrete algorithms, 119--125 (2001; Zbl 1018.90026) and Combinatorica 24, No. 1, 117--125 (2004; Zbl 1049.11087)]. Some possible extensions of this result are discussed, and the following is proven: The hypergraph of all disjoint unions of at most \(d\) intervals in \(\{1, \ldots, n\}\) has linear discrepancy \((1 - \frac d {n+1}) d\) (the linear discrepancy of a hypergraph is the one of its incidence matrix).