A note on the discrepancy of matrices with bounded row and column sums

DOI10.1016/J.DISC.2014.11.020MaRDI QIDQ488272zbMATH OpenOpenAlexFDO

Authors Nicholas J. A. Harvey

Publication date 23 January 2015

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.2159

zbMATH Keywords

discrepancy theoryLovász local lemma

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Hypergraphs (05C65)

Abstract: A folklore result uses the Lovasz local lemma to analyze the discrepancy of hypergraphs with bounded degree and edge size. We generalize this result to the context of real matrices with bounded row and column sums.

Recommendations

• On the discrepancy of random matrices with many columns
• The determinant bound for discrepancy is almost tight
• Linear and hereditary discrepancy
• On the discrepancy of random low degree set systems
• scientific article; zbMATH DE number 4195999

Cites work

• ``Integer-making theorems
• A constructive proof of the general Lovász local lemma
• Graph colouring and the probabilistic method
• scientific article; zbMATH DE number 863495 (Why is no real title available?)
• scientific article; zbMATH DE number 6472647 (Why is no real title available?)
• Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
• Six Standard Deviations Suffice
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(4)

• On the upper bounds of the minimum number of rows of disjunct matrices
• Short proofs of the Gale \& Ryser and Ford \& Fulkerson characterizations of the row and column sum vectors of (0, 1)-matrices
• On the discrepancy of random matrices with many columns
• \(\ell_1\)-sparsity approximation bounds for packing integer programs

This page was built for publication: A note on the discrepancy of matrices with bounded row and column sums

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q488272)