On the discrepancy of strongly unimodular matrices Academic Article uri icon

abstract

  • A (0, 1) matrix A is strongly unimodular if A is totally unimodular and every matrix obtained from A by setting a non-zero entry to 0 is also totally unimodular. Here we consider the linear discrepancy of strongly unimodular matrices. It was proved by Lovz et al. (J. Combin. 7 (1986) 151-160) that for any matrix A, lindisc(A)herdisc(A). (1) When A is the incidence matrix of a set-system, a stronger inequality holds: For any family script H sign of subsets of {1,2,...,n}, lindisc(script H sign)(1 - tn)herdisc(script H sign), where tn2-2n (Spencer, Ten Lectures on the Probabilistric Method, 2nd Edition, CBMS-NSF Regional Conferences Series in Applied Mathematics, 1994). In this paper we prove that the constant tn can be improved to 3-(n+1)/2 for strongly unimodular matrices. 2000 Elsevier Science B.V. All rights reserved.

published proceedings

  • Discrete Mathematics

author list (cited authors)

  • Peng, H., & Yan, C. H.

citation count

  • 0

complete list of authors

  • Peng, Hua||Yan, Catherine Huafei

publication date

  • January 2000