Linear and hereditary discrepancy (Q2703023)

Consider a hypergraph \(G= (V,E)\) where the hyperedge set \(E\) is a family of subsets of the vertex set \(V\). For every mapping \(\varepsilon: V\to\{1,-1\}\), define \(\varepsilon(e)= \sum_{v\in e}\varepsilon(v)\) for \(e\in E\). The discrepancy of \(G\) is defined by \(\text{disc}(G)= \min_{\varepsilon:V\to \{1,-1\}} \max_{e\in E}|\varepsilon(e)|\). This concept can be generalized to matrices by defining \(\text{disc}(A)= \min_{\varepsilon\in \{1,-1\}^n}\|A\varepsilon\|\), where \(A\) is an \(m\times n\) matrix and the norm is the maximum norm. If \(A\) is the incidence matrix of \(G\), then \(\text{disc}(A)= \text{disc}(G)\). There are two related notions: the linear discrepancy of \(A\) is defined by \(\text{lindisc}(A)= \max_{p\in [1,-1]^n} \min_{\varepsilon\in \{1,-1\}}\|A(p- \varepsilon)\|\), and the hereditary discrepancy is defined by \(\text{herdisc}(A)= \max_{J\subseteq [n]} \text{disc}((a_{ij})_{i\in[m],j\in J})\) where \(A= (a_{ij})\). In this paper, a well-known bound \(\text{lindisc}(A)\leq 2\text{ herdisc}(A)\) is improved to \(\text{lindisc}(A)\leq 2(1- 2^{-q})\text{herdisc}(A)\) where \(q= \lfloor\log_2m\rfloor+ 1\).