The Zarankiewicz number z(33;2) equals 195

The Zarankiewicz number z(n;2) is the largest number of ones in an n x n zero-one matrix with no 2 x 2 all-ones submatrix, equivalently the largest number of edges of a C4-free bipartite graph with n vertices in each part. Collins, Riasanovsky, Wallace and Radziszowski (2016) tabulated its values through n=31, and their bound z(32;2) <= 190 gives 189 <= z(33;2) <= 202. We prove that z(33;2) = 195; together with z(32;2) = 189, this determines z(n;2) for every n <= 33. The lower bound is a matrix obtained from the projective plane of order 5. For the upper bound we exclude matrices with 197 and with 196 ones; both parts use the value z(32;2) = 189. For 197 ones, the structure of the unique row and column of degree 5 reduces the problem to seven cases, which are excluded by hand and by exhaustive enumeration of the remaining free part followed by satisfiability computations. For 196 ones, degree lemmas and exact linear screens reduce the pairs of row and column degree profiles to 48 ordered pairs. These are excluded by hand arguments, by an analysis of the Gram matrix of the rows through the graph of disjoint pairs of rows, including the Matrix-Tree theorem and a positive-semidefiniteness bound, and by satisfiability computations. Every unsatisfiability verdict is backed by a proof checked by an independent proof checker. This record contains the manuscript (PDF) and the supplementary archive, split into five parts (join them as described in JOIN.txt): the code, the extremal matrix and its 720 variants, the enumeration and sieve outputs, the exact certificates, the formulas or their generators with digests, the deposited LRAT proofs and the case ledger, with a SHA-256 manifest and instructions for reproducing every computation. MSC2020: 05C35 (primary); 05C38, 05C85, 68R10 (secondary)

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-10-15
DOI
https://doi.org/10.5281/zenodo.23334625
Primary Topic
Limits and Structures in Graph Theory
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

The Zarankiewicz number z(33;2) equals 195

Yancun Yan
Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
preprint

The Zarankiewicz number z(33;2) equals 195

Yancun Yan
preprint en

Abstract

The Zarankiewicz number z(n;2) is the largest number of ones in an n x n zero-one matrix with no 2 x 2 all-ones submatrix, equivalently the largest number of edges of a C4-free bipartite graph with n vertices in each part. Collins, Riasanovsky, Wallace and Radziszowski (2016) tabulated its values through n=31, and their bound z(32;2) <= 190 gives 189 <= z(33;2) <= 202. We prove that z(33;2) = 195; together with z(32;2) = 189, this determines z(n;2) for every n <= 33. The lower bound is a matrix obtained from the projective plane of order 5. For the upper bound we exclude matrices with 197 and with 196 ones; both parts use the value z(32;2) = 189. For 197 ones, the structure of the unique row and column of degree 5 reduces the problem to seven cases, which are excluded by hand and by exhaustive enumeration of the remaining free part followed by satisfiability computations. For 196 ones, degree lemmas and exact linear screens reduce the pairs of row and column degree profiles to 48 ordered pairs. These are excluded by hand arguments, by an analysis of the Gram matrix of the rows through the graph of disjoint pairs of rows, including the Matrix-Tree theorem and a positive-semidefiniteness bound, and by satisfiability computations. Every unsatisfiability verdict is backed by a proof checked by an independent proof checker. This record contains the manuscript (PDF) and the supplementary archive, split into five parts (join them as described in JOIN.txt): the code, the extremal matrix and its 720 variants, the enumeration and sieve outputs, the exact certificates, the formulas or their generators with digests, the deposited LRAT proofs and the case ledger, with a SHA-256 manifest and instructions for reproducing every computation. MSC2020: 05C35 (primary); 05C38, 05C85, 68R10 (secondary)

Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.