On the discrepancy of strongly unimodular matrices
type: Item
instance of: scholarly article
title: On the discrepancy of strongly unimodular matrices
zbMATH Open document ID: 0951.05016
DOI: 10.1016/S0012-365X(99)00345-3
author: Hua Peng
author: Catherine Yan
published in: Discrete Mathematics
publication date: 2000-11-29T00:00:00Z
review text: 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.…
reviewed by: Philippe Elbaz-Vincent
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 15B36
zbMATH DE Number: 1462330
zbMATH Keywords: discrepancy
zbMATH Keywords: Spencer's conjecture
zbMATH Keywords: linear discrepancy
zbMATH Keywords: hereditary discrepancy
zbMATH Keywords: totally unimodular matrix
zbMATH Keywords: strongly unimodular matrix
zbMATH Keywords: coloring
zbMATH Keywords: incidence matrix
MaRDI profile type: Publication
full work available at URL: s0012-365x(99)00345-3
OpenAlex ID: W2011745869
description: scientific article; zbMATH DE number 1462330