← All papers
First page of Asymptotic equivalence and exact values for second-order Zarankiewicz numbers

Asymptotic equivalence and exact values for second-order Zarankiewicz numbers

Nikita Lebedev

math.CO Oct 4, 2026 · v1
Lean sources with pinned Mathlib formalize the coefficient/graph equivalence of Theorem 5.4 and the ungrounded bipartite component criterion for nonzero product relations.
The recursive-line and signed Zarankiewicz numbers maximize the number of squares in augmentations of a maximum $C_4$-free base, subject to two sufficient irreducibility criteria. The count includes one square per base cell and one per selected pair of unused cells. We compare these parameters with the second-order number, which uses irreducibility itself. Every maximum $m\times n$ base admits a recursive-line augmentation with at least $mn/2-C\max(m,n)$ squares, for an absolute constant $C$. Combining this bound with a two-column extension of known fixed-width families, we show that all three parameters are asymptotically equivalent, uniformly as the larger dimension tends to infinity. For individual displays, a transfer graph shows that once the signed closure identifies every selected pair, the signed criterion is equivalent to irreducibility. We determine the second-order number for every six-column rectangle and give eventual exact formulas for all three numbers at widths seven, nine and eleven. We also prove signed and recursive-line equality at $8\times7$ and, together with earlier values, whenever the shorter side is at most six, except possibly at $14\times4$. The exact-value results are computer-assisted, using exhaustive enumeration, checked propositional refutations and symbolic certificates with a proved lifting argument for arbitrary lengths.

The work studies second-order Zarankiewicz numbers z_2 and their sufficient-criterion variants z_RL (recursive-line) and z_SL (signed). These count the maximum number of squares in irreducible augmentations of maximum C4-free bases by pairs of unused cells. It asks how these parameters compare asymptotically and what their exact values are at small widths.

A column-fan gluing lemma, combined with a rainbow matching in a linear set system, gives a uniform half-density lower bound for every maximum base. A universal two-column path extension is added to known fixed-width families. A transfer graph shows that the signed criterion is equivalent to irreducibility once all selected pairs are identified, and part of this equivalence is formalized in Lean with a pinned Mathlib. The exact values are computer-assisted, using exhaustive enumeration, checked propositional refutations, and symbolic certificates with a proved lifting lemma for arbitrary lengths.

Every maximum m×n base admits a recursive-line augmentation with at least mn/2 − C·max(m,n) squares, so all three parameters are asymptotically equivalent. z_2 is determined for every six-column rectangle, and eventual exact formulas are given at widths 7, 9 and 11 (e.g. 4m+10 for n=7, m≥19). Signed and recursive-line numbers are equal at 8×7, and whenever the shorter side is at most six, except possibly at 14×4.

nrow rangevalue
5m ≥ 123m+5
7m ≥ 194m+10
9m ≥ 365m+18
11m ≥ 536m+27
Eventual exact values z_RL = z_SL = z_2 at odd widths