Metraipolis › archive › dc_026ae818bb95

A congruence obstruction to Roman's bound for Zarankiewicz numbers — arXiv:2608.07607

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.07607
License (as archived)
CC0-1.0
Archived
2026-10-19T09:08:45.983Z
SHA-256 of the archived text
bfa07b0afee0a1f8039bc3e90b816488666507d5c92da1f4432bf68231cdfb09
Stable URL of this page
https://metraipolis.com/documento/dc_026ae818bb95

How to cite

A congruence obstruction to Roman's bound for Zarankiewicz numbers — arXiv:2608.07607 — arXiv (en), https://arxiv.org/abs/2608.07607 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_026ae818bb95 (Metraipolis archive dc_026ae818bb95, sha256 bfa07b0afee0a1f8039bc3e90b816488666507d5c92da1f4432bf68231cdfb09)
BibTeX
@misc{dc026ae818bb95,
  title = {A congruence obstruction to Roman's bound for Zarankiewicz numbers — arXiv:2608.07607},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.07607},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_026ae818bb95; sha256 bfa07b0afee0a1f8039bc3e90b816488666507d5c92da1f4432bf68231cdfb09},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.07607. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Let z(m,n;s,t) be the largest number of ones in an m x n zero-one matrix with no s x t all-ones submatrix. Roman's 1975 inequality remains the best general upper bound for s>=3, but it is not attained on a large part of the range just below the design threshold T=(t-1)C(m,s)/(s+1). The proof has two steps. First, for n=T-c with 1<=c<=sT/(s+2), Roman's bound equals the elementary counting bound (s+1)(T-c)+floor(2c/s), adding nothing beyond a budget inequality and convexity. Second, attainment forces all but at most one column to have size s+1 or s+2; each such column has a point lying in a number of s-sets divisible by d=gcd(s,C(s+1,2)), pinning the leftover coverage there to a single residue mu mod d, which a global count rules out. With r=c mod s and slack sigma(r) depending only on s, we prove z(m,T-c;s,t) <= Rom(m,T-c)-1 whenever 1<=sigma(r)<d and m*mu != s*sigma(r), or mu != 0 and m*mu > s*sigma(r). The first case is an odd-s phenomenon confined to one residue class, giving order-m^s values of n; the second needs mu != 0 but covers the whole interval once m exceeds a threshold depending only on s and mu. For s=4, t=2, m=28 it covers all 2730 values of n; when c=(s+1)/2 and an s-(m,s+1,t-1) design exists, z=(s+1)(T-c) exactly. Finally we relate the obstruction to linear programming: the relaxation over all 2^m subset variables collapses, under symmetrisation, to the counting bound, so no linear relaxation of the covering constraints alone can beat the bound of Chen, Horsley, and Mammoliti ( arXiv:2310.12685 , "Zarankiewicz numbers near the triple system threshold"). For the refined program of Davies, Gill, and Horsley, its optimum is still attained at the Roman vertex on an explicit sub-family, and we record where their program does better.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-11 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.07607 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T09:05:33.533Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).