ZarankiewiczDB,

an online database of Zarankiewicz numbers. home; recent; tables; submit; theorems & references

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.