Zero-sum squares in bounded discrepancy \-1,1\-matrices

DOI10.37236/9617MaRDI QIDQ2236819zbMATH OpenOpenAlexFDO

Authors Alma R. Arévalo, Amanda Montejano, Edgardo Roldán-Pensado

Publication date 26 October 2021

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

discrepancy theoryErickson matrixzero-sum matrix

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Ramsey theory (05D10) Other combinatorial number theory (11B75) Matrices of integers (15B36)

Abstract: For $nge5$, we prove that every $nimesn$ matrix $M=(a_{i,j})$ with entries in $-1,1$ and absolute discrepancy $|mathrmdisc(M)|=|sum{a}_{i,j}|len$ contains a zero-sum square except for the split matrix (up to symmetries). Here, a square is a $2imes2$ sub-matrix of $M$ with entries $a_{i,j},a_{i+s,s},a_{i,j+s},a_{i+s,j+s}$ for some $sge1$, and a split matrix is a matrix with all entries above the diagonal equal to $-1$ and all remaining entries equal to $1$. In particular, we show that for $nge5$ every zero-sum $nimesn$ matrix with entries in $-1,1$ contains a zero-sum square.

Review text

Summary: For \(n\geqslant 5\), we prove that every \(n\times n\) matrix \(\mathcal{M}=(a_{i,j})\) with entries in \(\{-1,1\}\) and absolute discrepancy \(\vert\text{disc}(\mathcal{M})\vert=\vert\sum a_{i,j}\vert\leqslant n\) contains a zero-sum square except for the split matrices (up to symmetries). Here, a square is a \(2\times 2\) sub-matrix of \(\mathcal{M}\) with entries \(a_{i,j}\), \(a_{i+s,s}\), \(a_{i,j+s}\), \(a_{i+s,j+s}\) for some \(s\geqslant 1\), and a split matrix is a matrix with all entries above the diagonal equal to \(-1\) and all remaining entries equal to 1. In particular, we show that for \(n\geqslant 5\) every zero-sum \(n\times n\) matrix with entries in \(\{-1,1\}\) contains a zero-sum square.

Recommendations

• Zero-sum squares in \(\{-1, 1\}\)-matrices with low discrepancy
• Zero-sum square matrices
• Sums of square-zero infinite matrices revisited
• (0,1)-matrices and discrepancy
• Discrepancy of matrices of zeros ond ones

Cites work

• A new method to construct lower bounds for van der Waerden numbers
• Ectremal binary matrices without constant 2-squares
• scientific article; zbMATH DE number 1016990 (Why is no real title available?)
• scientific article; zbMATH DE number 1528185 (Why is no real title available?)
• On monochromatic subsets of a rectangular grid
• Patterns and complexity of multiplicative functions
• The Erdös discrepancy problem
• Zero-sum square matrices
• Zero-sum subsequences in bounded-sum \(\{-1,1\}\)-sequences

Cited in

(2)

• On combinatorial rectangles with minimum \(\infty \)-discrepancy
• Zero-sum squares in \(\{-1, 1\}\)-matrices with low discrepancy

This page was built for publication: Zero-sum squares in bounded discrepancy \(\{-1,1\}\)-matrices

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