# An attack on Zarankiewicz's problem through SAT solving

arXiv: https://arxiv.org/abs/2203.02283 · HTML: https://mlsanity.com/paper/2203.02283/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Mar 2022.

## Built on by (most cited first, 2 of 2)

- [New Bounds for Zarankiewicz Numbers via Reinforced LLM Evolutionary Search](https://mlsanity.com/paper/2605.01120/) (2026)
- [Exact Zarankiewicz Values On Two Finite Frontier Slices](https://mlsanity.com/paper/2608.08154/) (2026)

## Abstract (arXiv)

The Zarankiewicz function gives, for a chosen matrix and minor size, the maximum number of ones in a binary matrix not containing an all-one minor. Tables of this function for small arguments have been compiled, but errors are known in them. We both correct the errors and extend these tables in the case of square minors by expressing the problem of finding the value at a specific point as a series of Boolean satisfiability problems, exploiting permutation symmetries for a significant reduction in the work needed. When the ambient matrix is also square we also give all non-isomorphic examples of matrices attaining the maximum, up to the aforementioned symmetries; it is found that most maximal matrices have some form of symmetry.