A note on the discrepancy of matrices with bounded row and column sums
From MaRDI portal
Publication:488272
DOI10.1016/J.DISC.2014.11.020zbMATH Open1305.05169arXiv1307.2159OpenAlexW2078116611MaRDI QIDQ488272FDOQ488272
Authors: Nicholas J. A. Harvey 
Publication date: 23 January 2015
Published in: Discrete Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1307.2159
Recommendations
[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Lov%EF%BF%BD%EF%BF%BDsz+local+lemma&go=Go Lov��sz local lemma]discrepancy theory
Cites Work
- Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Title not available (Why is that?)
- Six Standard Deviations Suffice
- Graph colouring and the probabilistic method
- A constructive proof of the general Lovász local lemma
- Cover-Decomposition and Polychromatic Numbers
- ``Integer-making theorems
- Title not available (Why is that?)
Cited In (4)
- Partial Resampling to Approximate Covering Integer Programs
- On the upper bounds of the minimum number of rows of disjunct matrices
- \(\ell_1\)-sparsity approximation bounds for packing integer programs
- Short proofs of the Gale \& Ryser and Ford \& Fulkerson characterizations of the row and column sum vectors of (0, 1)-matrices
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)
