On the discrepancy of strongly unimodular matrices (Q1567675)

Let \(S\) be a set and \(\mathcal{H}\) a family of subsets of \(S\). For a given 2-coloring \(\chi : S \to \{ +1,-1\}\), let \(\text{disc} (\mathcal{H},\chi)=\max_{H\in \mathcal{H}} \{|\sum_{s\in H}\chi (s) |\}\). Then the discrepancy of \(\mathcal H\) is defined as \(\text{disc} (\mathcal{H})=\min_{\chi} \{ \text{disc} (\mathcal{H},\chi)\}\). Intuitively \(\text{disc} (\mathcal{H},\chi)\) measures the uniformity of a given coloring \(\chi\), and the discrepancy of \(\mathcal{H}\) the best achievable uniformity. The discrepancy can also be defined via the incidence matrix. Let \(A=(a_{i,j})\) (\(E_i \in \mathcal{H}\), \(j\in S\)) be the incidence matrix of \(\mathcal H\), i.e. \(a_{i,j}=1\) if \(j\in E_i\) and 0 otherwise. Then we define \(\text{disc} (A)= \text{disc}(\mathcal{H})\). Various discrepancies can be introduced to the set-system which will describe its intrinsic uniformity. For a set-system \((\mathcal{H},S)\) with incidence matrix \(A\), the linear discrepancy is defined by letting \[ \text{lindisc}(\mathcal{H})= \text{lindisc}(A)=\max_{c\in [0,1]^h} \min_{x\in \{0,1\}^n} ||A(x-c)||_\infty . \] In order to get more structural information, we can consider the maximal discrepancy over all the submatrices of \(A\). Let \(T\) be a subset of \(S\). The restriction of \(\mathcal{H}\) to the subset \(T\) is the set-system \(\mathcal{H}_T=\{ H\cap T\mid H \in \mathcal{H}\}\). The incidence matrix \(A_T\) of \(\mathcal{H}_T\) is the submatrix of \(A\) consisting of columns \(j\) where \(j\in T\). The hereditary discrepancy of \(\mathcal{H}\) is then defined by letting \[ \text{herdisc}(\mathcal{H})= \text{herdisc} (A)=\max_{T \subset S} \text{disc}(\mathcal{H}_T). \] A standard problem regarding set-systems is the following: What is the maximal \(t_n\) so that if \(|S|=n\) and \(\mathcal{H}\) is a family of subsets of \(S\), \(\text{lindisc}(\mathcal{H}) \leq (1-t_n) \text{herdisc}(\mathcal{H})?\) The best known result is \(t_n\geq 2^{-2^n}\) given by \textit{J. Spencer} [Ten lectures on the probabilistic method. 2nd ed. (CBMS-NSF Regional Conference Series in Applied Mathematics. 64. Philadelphia, PA: SIAM) (1994; Zbl 0822.05060)], who has also conjectured that \(t_n=1/(n+1)\). In the paper under review the authors prove that \(t_n \geq 3^{-(n+1)/2}\) for strongly unimodular \((0,1)\) matrices (recall that a matrix \(A\) is said to be totally unimodular if the determinant of each square submatrix of \(A\) is 0 or \(\pm 1\), and is said strongly unimodular if \(A\) is totally unimodular and every matrix obtained from \(A\) by setting a \(\pm 1\) entry to 0 is also totally unimodular). Furthermore, they show that if \(A\) is a strongly unimodular \((0,1)\) matrix in which every row has no more than two non-zero entries, then \(\text{lindisc}(A) \leq 1-1/(n+1),\) where \(n\) is the number of columns in the matrix. This last result could be regarded as a test for the validity of Spencer's conjecture (the authors also show that the previous inequality cannot be improved).