Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 59 min ago
PreprintCC BY 4.0arXiv

Density and separation for augmented Zarankiewicz numbers

  • Nikita Lebedev
Open at sourcePDFDOICite

Abstract

We study the augmented Zarankiewicz problem, in which disjoint pairs of cells are added to a binary matrix with no all-one 2×2 submatrix. The pairs must satisfy compatibility conditions, and the objective counts each original occupied cell and each added pair once. We show that starting with a maximum C4-free matrix can lower the final optimum, answering a question of Qi, Cui, and Xu. Let zA(m,n) be the optimum over all C4-free initial matrices, and zL(m,n) the optimum when the initial matrix must have the maximum number of occupied cells. As n→∞ with n≤ m=o(n2), we prove zA(m,n)−zL(m,n)≥(1/30−o(1))mn and determine the sharp second-order term: zA(m,n)=mn/3+(1/√6+o(1))n√m. An explicit construction gives a separation at m=n=1893. We also find a sharp density threshold: when n→∞ and m/n2→ c>0, the limited density zL(m,n)/(mn) tends to 1/3 if and only if c≥1/12. The proofs combine density and stability estimates, combinatorial constructions, and an exact polynomial certificate.

Related

  1. The Second-Order Augmented Zarankiewicz Number
    Liqun Qi, Chunfeng Cui
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. New Bounds for Limited Zarankiewicz Numbers from K5t Blocks
    Hanxin Liu, Yisheng Song
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  3. A Twelve-Row Seed and a One-Row Extension for Five-Column Recursive-Line Zarankiewicz Numbers
    Min Xi, Jingya Chang
    arXivPreprintarXiv licenceFull textAnalysis & PDEsCombinatorics & discrete mathematicsarXiv
  4. Asymptotic equivalence and exact values for second-order Zarankiewicz numbers
    Nikita Lebedev
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Recursive-Line Zarankiewicz Numbers with Four Columns
    Zhiwei Chen, Yannan Chen
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{lebedev2026density,
  title = {{Density and separation for augmented Zarankiewicz numbers}},
  author = {Nikita Lebedev},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.16555},
  eprint = {2609.16555},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.16555},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Density and separation for augmented Zarankiewicz numbers
AU  - Nikita Lebedev
PY  - 2026
DA  - 2026/09/15
PB  - arXiv
DO  - 10.48550/arxiv.2609.16555
UR  - https://arxiv.org/abs/2609.16555
AB  - We study the augmented Zarankiewicz problem, in which disjoint pairs of cells are added to a binary matrix with no all-one 2×2 submatrix. The pairs must satisfy compatibility conditions, and the objective counts each original occupied cell and each added pair once. We show that starting with a maximum C_4-free matrix can lower the final optimum, answering a question of Qi, Cui, and Xu. Let z_A(m,n) be the optimum over all C_4-free initial matrices, and z_L(m,n) the optimum when the initial matrix must have the maximum number of occupied cells. As n→∞ with n≤ m=o(n^2), we prove z_A(m,n)−z_L(m,n)≥(1/30−o(1))mn and determine the sharp second-order term: z_A(m,n)=mn/3+(1/√6+o(1))n√m. An explicit construction gives a separation at m=n=1893. We also find a sharp density threshold: when n→∞ and m/n^2→ c>0, the limited density z_L(m,n)/(mn) tends to 1/3 if and only if c≥1/12. The proofs combine density and stability estimates, combinatorial constructions, and an exact polynomial certificate.
ER  -