On the discrepancy of strongly unimodular matrices

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.

authors

• Yan, Catherine

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

publisher

• Elsevier  Publisher

published in

• Discrete Mathematics  Journal

Digital Object Identifier (DOI)

• 10.1016/s0012-365x(99)00345-3

start page

• 223

end page

• 233

volume

• 219

issue

• 1-3

URL

• http://dx.doi.org/10.1016/s0012-365x(99)00345-3