# ZarankiewiczDB,

an online database of Zarankiewicz numbers.

## Theorems

### Theorem 1.

Convex optimisation bound If $r,l \in \mathbb{N}$ maximise $mr + l$ subject to $r \le n$ and $l < m$, and $$(m-l){r \choose t} + l{r+1 \choose t} \le (s-1){n \choose t}$$ then $z(m,n;~s,t) \le mr + l$.

Let $\mathbf{r} \in \mathbb{N}^m$ be the vector of row weights of an $(s,t)$-rectangle-free matrix. We have$$\sum_{i=1}^m {r_i \choose t} \le (s-1){n \choose t}$$otherwise some combination of $t$ columns forms a rectangle with some $s$ rows by the pigeonhole principle. As this sum is a convex function of $\mathbf{r}$, without loss of generality $\sum r_i$ is maximised when every $\left|r_i - r_j\right| \le 1$. In this case we have $l$ rows of some weight $r+1$, and the remaining $m-l$ rows of weight $r$.

### Theorem 2.

Čulik's theorem [Cul56] If $m \ge (s-1){n \choose t}$ then $z(m,n;~s,t) = (t-1)m + (s-1){n \choose t}$.

The upper bound given by Theorem 1 has $r = t-1$ and $l = (s-1){n \choose t}$, which is attainable by using each combination of $t$ columns in $s-1$ rows.

### Theorem 3.

Reiman's theorem [Rei58] For $k \ge 2$, $$z(k^2 + k + 1,~k^2 + k + 1) \le (k+1)(k^2 + k + 1)$$and equality is acheived by and only by the incidence matrix of a finite projective plane of order $k$.

This is the upper bound given by Theorem 1, and is only achieved by a vector $\mathbf{r}$ with every $r_i=k+1$. As $(k^2 + k+1){k+1 \choose 2} = {k^2 + k + 1 \choose 2}$, every pair of columns must intersect in some row, as required for a finite projective plane.

## References

 [CRWR16] Alex Collins, Alexander Riasanovsky, John Wallace, Stanisław Radziszowski. Zarankiewicz numbers and bipartite Ramsey numbers. arXiv preprint arXiv:1604.01257, 2016. [Cul56] K. Čulik. Teilweise Lösung eines verallgemeinerten problems von K. Zarankiewicz. In Annales Polonici Mathematici, volume 1, pages 165–168, 1956. [DDR13] Janusz Dybizbański, Tomasz Dzido, Stanisław Radziszowski. On some Zarankiewicz numbers and bipartite Ramsey numbers for quadrilateral. arXiv preprint arXiv:1303.5475, 2013. [DHS13] Gábor Damásdi, Tamás Héger, and Tamás Szőnyi. The Zarankiewicz problem, cages, and geometries. Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae Sectio Mathematica, 56(1):3–37, 2013. [FGGP10] Stephen Fenner, William Gasarch, Charles Glover, and Semmy Purewal. Rectangle free coloring of grids. arXiv preprint arXiv:1005.3750, 2010. [FS13] Zoltán Füredi and Miklós Simonovits. The history of degenerate (bipartite) extremal graph problems. In Erdős Centennial, pages 169–264. Springer, 2013. [Guy68] Richard K. Guy. A problem of Zarankiewicz. In Theory of Graphs, pages 119–150. Akadémai Kiadó, Budapest, 1968. [Guy69] Richard K. Guy. A many-facetted problem of Zarankiewicz. In The Many Facets of Graph Theory, pages 129–148. Springer, 1969. [Kay16] Andrew Kay. Efficient algorithms for the Zarankiewicz problem. Pre-print, 2016. [KST54] T. Kóvari, V. Sós, and P. Turán. On a problem of K. Zarankiewicz. Colloquium Mathematicae, 3(1):50–57, 1954. [Rei58] Istvan Reiman. Über ein problem von K. Zarankiewicz. Acta Mathematica Hungarica, 9(3-4):269–273, 1958. [Rom75] Steven Roman. A problem of Zarankiewicz. Journal of Combinatorial Theory, Series A, 18(2):187–198, 1975. [SP13] Bernd Steinbach, Christian Posthoff. Solution of the Last Open Four-Colored Rectangle-Free Grid: An Extremely Complex Multiple-Valued Problem. Multiple-Valued Logic (ISMVL), 2013 IEEE 43rd International Symposium on. IEEE, 2013. [Zar51] Kazimierz Zarankiewicz. Problem p 101. In Colloq. Math, volume 2, page 5, 1951.