Zarankiewicz' problem and finite geometries

Tam\'as Sz\H onyi
ELTE Budapest

Tam\'as H\'eger
MTA-ELTE GAC Research Group

Gabor Damasdi
ELTE Budapest

PDF

Minisymposium: FINITE GEOMETRY

Content: Zarankiewicz asked for the minimum number of $1$s in an $m\times n$ $0$-$1$ matrix that assures the existence of an $s\times t$ submatrix containing only $1$s. We consider the following, equivalent formulation. A bipartite graph $G=(A,B;E)$ is \emph{$K_{s,t}$-free} if it does not contain $s$ nodes in $A$ and $t$ nodes in $B$ that span a subgraph isomorphic to $K_{s,t}$. The maximum number of edges a $K_{s,t}$-free bipartite graph with $|A|=m$, $|B|=n$ may have is denoted by $Z_{s,t}(m,n)$, and is called a \emph{Zarankiewicz number}. Note that a $K_{s,t}$-free bipartite graph is not necessarily $K_{t,s}$-free if $s\neq t$. An old result, due to Reiman establishes a connection between Zarankiewicz' problem and incidence graphs of block designs (in particular, projective planes). In this talk, based on joint work with G.~Dam\'asdi and T.~H\'eger, we present upper and lower bounds on Zarankiewicz numbers, some giving exact values. We put emphasis on the case $s=t=2$, which has strong connections with finite geometries. Some of the results can be regarded as stability results for incidence graphs.

Back to all abstracts