ScholarLens Back to search
2000•Discrete MathematicsOpen access

On the discrepancy of strongly unimodular matrices

Hua Peng, Catherine H. Yan

Open full text 4 citations

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 Lováz et al. (J. Combin. 7 (1986) 151–160) that for any matrix A, (1)lindisc(A)⩽herdisc(A).When A is the incidence matrix of a set-system, a stronger inequality holds: For any family H of subsets of {1,2,…,n},lindisc(H)⩽(1−tn)herdisc(H),where tn⩾2−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.

Open-access reader

About this research paper

What this paper is about

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 Lováz et al. (J. Combin. 7 (1986) 151–160) that for any matrix A, (1)lindisc(A)⩽herdisc(A).When A is the incidence matrix of a set-system, a stronger inequality holds: For any family H of subsets of {1,2,…,n},lindisc(H)⩽(1−tn)herdisc(H),where tn⩾2−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.

Why it matters

OpenAlex reports 4 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available 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 Lováz et al. (J. Combin. 7 (1986) 151–160) that for any matrix A, (1)lindisc(A)⩽herdisc(A).When A is the incidence matrix of a set-system, a stronger inequality holds: For any family H of subsets of {1,2,…,n},lindisc(H)⩽(1−tn)herdisc(H),where tn⩾2−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.

Key concepts: Unimodular matrix, Mathematics, Combinatorics, Matrix (chemical analysis), Incidence matrix, Constant (computer programming), Integer matrix, Zero (linguistics)

Related papers

Related paper 1Related paper 2Related paper 3
Back to paper searchBrowse research topicsOriginal source
On the discrepancy of strongly unimodular matrices — Research Paper | ScholarLens