On combinatorial rectangles with minimum -discrepancy

DOI10.54550/ECA2021V1S1R7MaRDI QIDQ5093423zbMATH OpenOpenAlexFDO

Authors Chunwei Song, Bowen Yao

Publication date 26 July 2022

Published in Enumerative Combinatorics and Applications (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial rectanglemajorization relationmatrix enumerationminimum discrepancy

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Irregularities of distribution, discrepancy (11K38)

Abstract: A combinatorial rectangle may be viewed as a matrix whose entries are all +-1. The discrepancy of an m by n matrix is the maximum among the absolute values of its m row sums and n column sums. In this paper, we investigate combinatorial rectangles with minimum discrepancy (0 or 1 for each line depending on the parity). Specifically, we get explicit formula for the number of matrices with minimum L^infinity-discrepancy up to 4 rows, and establish the order of magnitude of the number of such matrices with m rows and n columns while m is fixed and n approaches infinity. By considering the number of column-good matrices with a fixed row-sum vector, we have developed a theory of decreasing criterion on based row-sum vectors with majorization relation, which turns out to be a helpful tool in the proof of our main theorems.

Recommendations

• Discrepancy of matrices of zeros ond ones
• Zero-sum squares in bounded discrepancy \(\{-1,1\}\)-matrices
• On the discrepancy of combinatorial rectangles
• (0,1)-matrices and discrepancy
• \((0,1)\)-matrices, discrepancy, and preservers. II

Cites work

• A lower bound for the hitting set size for combinatorial rectangles and an application
• An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums
• Discrepancy of set-systems and matrices
• Game theory, maximum entropy, minimum discrepancy and robust Bayesian decision theory
• scientific article; zbMATH DE number 193053 (Why is no real title available?)
• scientific article; zbMATH DE number 3435482 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 3443655 (Why is no real title available?)
• scientific article; zbMATH DE number 863495 (Why is no real title available?)
• Inequalities: theory of majorization and its applications
• On the discrepancy of combinatorial rectangles
• On the enumeration of rectangular (0, 1)-matrices
• Sufficient Dimension Reduction via Inverse Regression
• The enumeration of arrays and a generalization related to contingency tables

Cited in

(7)

• Discrepancy of matrices of zeros ond ones
• On the discrepancy for boxes and polytopes
• Relating multiway discrepancy and singular values of nonnegative rectangular matrices
• The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions
• On the discrepancy of combinatorial rectangles
• (0,1)-matrices and discrepancy
• \((0,1)\)-matrices, discrepancy, and preservers. II

This page was built for publication: On combinatorial rectangles with minimum \(\infty \)-discrepancy

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