Zarankiewicz problem

This article is about graphs with no large complete bipartite subgraph. For crossing numbers of complete bipartite graphs, see Zarankiewicz crossing number conjecture.

The Zarankiewicz problem, an unsolved problem in mathematics, asks for the largest possible number of edges in a bipartite graph that has a given number of vertices and has no complete bipartite subgraphs of a given size. It belongs to the field of extremal graph theory, a branch of combinatorics, and is named after the Polish mathematician Kazimierz Zarankiewicz, who proposed several special cases of the problem in 1951.

Problem statement

A bipartite graph $G=(U\cup V,E)$ consists of two disjoint sets of vertices $U$ and $V$, and a set of edges each of which connects a vertex in $U$ to a vertex in $V$. No two edges can both connect the same pair of vertices. A complete bipartite graph is a bipartite graph in which every pair of a vertex from $U$ and a vertex from $V$ is connected to each other. A complete bipartite graph in which $U$ has $s$ vertices and $V$ has $t$ vertices is denoted $K_{s,t}$. If $G=(U\cup V,E)$ is a bipartite graph, and there exists a set of $s$ vertices of $U$ and $t$ vertices of $V$ that are all connected to each other, then these vertices induce a subgraph of the form $K_{s,t}$. (In this formulation, the ordering of $s$ and $t$ is significant: the set of $s$ vertices must be from $U$ and the set of $t$ vertices must be from $V$, not vice versa.)

The Zarankiewicz function $z(m,n;s,t)$ denotes the maximum possible number of edges in a bipartite graph $G=(U\cup V,E)$ for which $|U|=m$ and $|V|=n$, but which does not contain a subgraph of the form $K_{s,t}$. As a shorthand for an important special case, $z(n;t)$ is the same as $z(n,n;t,t)$. The Zarankiewicz problem asks for a formula for the Zarankiewicz function, or (failing that) for tight asymptotic bounds on the growth rate of $z(n;t)$ assuming that $t$ is a fixed constant, in the limit as $n$ goes to infinity.

For $s=t=2$ this problem is the same as determining cages with girth six. The Zarankiewicz problem, cages and finite geometry are strongly interrelated.

The same problem can also be formulated in terms of digital geometry. The possible edges of a bipartite graph $G=(U\cup V,E)$ can be visualized as the points of a $|U|\times |V|$ rectangle in the integer lattice, and a complete subgraph is a set of rows and columns in this rectangle in which all points are present. Thus, $z(m,n;s,t)$ denotes the maximum number of points that can be placed within an $m\times n$ grid in such a way that no subset of rows and columns forms a complete $s\times t$ grid. An alternative and equivalent definition is that $z(m,n;s,t)$ is the smallest integer $k$ such that every (0,1)-matrix of size $m\times n$ with $k+1$ ones must have a set of $s$ rows and $t$ columns such that the corresponding $s\times t$ submatrix is made up only of 1s.

Examples

A bipartite graph with 4 vertices on each side, 13 edges, and no $K_{3,3}$ subgraph, and an equivalent set of 13 points in a 4 × 4 grid, showing that $z(4;3)\geq 13$.

The number $z(n;2)$ asks for the maximum number of edges in a bipartite graph with $n$ vertices on each side that has no 4-cycle (its girth is six or more). Thus, $z(2;2)=3$ (achieved by a three-edge path), and $z(3;2)=6$ (a hexagon).

In his original formulation of the problem, Zarankiewicz asked for the values of $z(n;3)$ for $n=4,5,6$. The answers were supplied soon afterwards by Wacław Sierpiński: $z(4;3)=13$, $z(5;3)=20$, and $z(6;3)=26$. The case of $z(4;3)$ is relatively simple: a 13-edge bipartite graph with four vertices on each side of the bipartition, and no $K_{3,3}$ subgraph, may be obtained by adding one of the long diagonals to the graph of a cube. In the other direction, if a bipartite graph with 14 edges has four vertices on each side, then two vertices on each side must have degree four. Removing these four vertices and their 12 incident edges leaves a nonempty set of edges, any of which together with the four removed vertices forms a $K_{3,3}$ subgraph.

Upper bounds

The Kővári–Sós–Turán theorem provides an upper bound on the solution to the Zarankiewicz problem. It was established by Tamás Kővári, Vera T. Sós and Pál Turán shortly after the problem had been posed:

$z(m,n;s,t)<(s-1)^{1/t}(n-t+1)m^{1-1/t}+(t-1)m.$

Kővári, Sós, and Turán originally proved this inequality for $z(n;t)$. Shortly afterwards, Hyltén-Cavallius observed that essentially the same argument can be used to prove the above inequality. An improvement on the second term of the upper bound on $z(n;t)$ was given by Štefan Znám:

$z(n;t)<(t-1)^{1/t}n^{2-1/t}+{\frac {1}{2}}(t-1)n.$

If $s$ and $t$ are assumed to be constant, then asymptotically, using the big O notation, these formulae can be expressed as

$z(m,n;s,t)=O(mn^{1-1/s}+n)$;

$z(m,n;s,t)=O(nm^{1-1/t}+m)$.

In the particular case $m=n$, assuming without loss of generality that $s\leq t$, we have the asymptotic upper bound

$z(n,n;s,t)=O(n^{2-1/s}).$

Lower bounds

One can verify that among the two asymptotic upper bounds of $z(m,n;s,t)$ in the previous section, the first bound is better when $m=o(n^{s/t})$, and the second bound becomes better when $m=\omega (n^{s/t})$. Therefore, if one can show a lower bound for $z(n^{s/t},n;s,t)$ that matches the upper bound up to a constant, then by a simple sampling argument (on either an $n^{t/s}\times t$ bipartite graph or an $m\times m^{s/t}$ bipartite graph that achieves the maximum edge number), we can show that for all $m,n$, one of the above two upper bounds is tight up to a constant. This leads to the following question: is it the case that for any fixed $s\leq t$ and $m\leq n^{s/t}$, we have

$z(m,n;s,t)=\Omega (mn^{1-1/s})$?

In the special case $m=n$, up to constant factors, $z(n,n;s,t)$ has the same order as ${\text{ex}}(n,K_{s,t})$, the maximum number of edges in an $n$-vertex (not necessarily bipartite) graph that has no $K_{s,t}$ as a subgraph. In one direction, a bipartite graph with $n$ vertices on each side and $z(n,n;s,t)$ edges must have a subgraph with $n$ vertices and at least $z(n,n;s,t)/4$ edges; this can be seen from choosing $n/2$ vertices uniformly at random from each side, and taking the expectation. In the other direction, we can transform a graph with $n$ vertices and no copy of $K_{s,t}$ into a bipartite graph with $n$ vertices on each side of its bipartition, twice as many edges and still no copy of $K_{s,t}$, by taking its bipartite double cover. Same as above, with the convention that $s\leq t$, it has been conjectured that

$z(n,n;s,t)=\Theta (n^{2-1/s})$

for all constant values of $s,t$.

For some specific values of $s,t$ (e.g., for $t$ sufficiently larger than $s$, or for $s=2$), the above statements have been proved using various algebraic and random algebraic constructions. At the same time, the answer to the general question is still unknown to us.

Incidence graphs in finite geometry

The Levi graph of the Fano plane gives rise to the Heawood graph, a bipartite graph with seven vertices on each side, 21 edges, and no 4-cycles.

For $s=t=2$, a bipartite graph with $n$ vertices on each side, $\Omega (n^{3/2})$ edges, and no $K_{2,2}$ may be obtained as the Levi graph, or point-line incidence graph, of a projective plane of order $q$, a system of $q^{2}+q+1$ points and $q^{2}+q+1$ lines in which each two points determine a unique line, and each two lines intersect at a unique point. We construct a bipartite graph associated to this projective plane that has one vertex part as its points, the other vertex part as its lines, such that a point and a line is connected if and only if they are incident in the projective plane. This leads to a $K_{2,2}$-free graph with $q^{2}+q+1$ vertices and $(q^{2}+q+1)(q+1)$ edges. Since this lower bound matches the upper bound given by I. Reiman, we have the asymptotic

$z(n;2)=(1/2+o(1))n^{3/2}.$

For $s=t=3$, bipartite graphs with $n$ vertices on each side, $\Omega (n^{5/3})$ edges, and no $K_{3,3}$ may again be constructed from finite geometry, by letting the vertices represent points and spheres (of a carefully chosen fixed radius) in a three-dimensional finite affine space, and letting the edges represent point-sphere incidences.

More generally, consider $s=2$ and any $t$. Let $\mathbb {F} _{q}$ be the $q$-element finite field, and $h$ be an element of multiplicative order $t$, in the sense that $H=\{1,h,\dots ,h^{t-1}\}$ form a $t$-element subgroup of the multiplicative group $\mathbb {F} _{q}^{*}$. We say that two nonzero elements $(a,b),(a',b')\in \mathbb {F} _{q}\times \mathbb {F} _{q}$ are equivalent if we have $a'=h^{d}a$ and $b'=h^{d}b$ for some $d$. Consider a graph $G$ on the set of all equivalence classes $\langle a,b\rangle$, such that $\langle a,b\rangle$ and $\langle x,y\rangle$ are connected if and only if $ax+by\in H$. One can verify that $G$ is well-defined and free of $K_{2,t+1}$, and every vertex in $G$ has degree $q$ or $q-1$. Hence we have the upper bound

$z(n,n;2,t+1)=(t^{1/2}+o(1))n^{3/2}.$

Norm graphs and projective norm graphs

For $t$ sufficiently larger than $s$, the above conjecture $z(n,n;s,t)=\Theta (n^{2-1/s})$ was verified by Kollár, Rónyai, and Szabó and Alon, Rónyai, and Szabó using the construction of norm graphs and projective norm graphs over finite fields.

For $t>s!$, consider the norm graph NormGraph_p,s with vertex set $\mathbb {F} _{p^{s}}$, such that every two vertices $a,b\in \mathbb {F} _{p^{s}}$ are connected if and only if $N(a+b)=1$, where $N\colon \mathbb {F} _{p^{s}}\rightarrow \mathbb {F} _{p}$ is the norm map

$N(x)=x\cdot x^{p}\cdot x^{p^{2}}\cdots x^{p^{s-1}}=x^{(p^{s}-1)/(p-1)}.$

It is not hard to verify that the graph has $p^{s}$ vertices and at least $p^{2s-1}/2$ edges. To see that this graph is $K_{s,s!+1}$-free, observe that any common neighbor $x$ of $s$ vertices $y_{1},\ldots ,y_{s}\in \mathbb {F} _{p^{s}}$ must satisfy

$1=N(x+y_{i})=(x+y_{i})\cdot (x+y_{i})^{p}\cdots (x+y_{i})^{p^{s-1}}=(x+y_{i})\cdot (x^{p}+y_{i}^{p})\cdots (x^{p^{s-1}}+y_{i}^{p^{s-1}})$

for all $i=1,\ldots ,s$, which a system of equations that has at most $s!$ solutions.

The same result can be proved for all $t>(s-1)!$ using the projective norm graph, a construction slightly stronger than the above. The projective norm graph ProjNormGraph_p,s is the graph on vertex set $\mathbb {F} _{p^{s-1}}\times \mathbb {F} _{p}^{\times }$, such that two vertices $(X,x),(Y,y)$ are adjacent if and only if $N(X+Y)=xy$, where $N\colon \mathbb {F} _{p^{s}}\rightarrow \mathbb {F} _{p}$ is the norm map defined by $N(x)=x^{(p^{s}-1)/(p-1)}$. By a similar argument to the above, one can verify that it is a $K_{s,t}$ -free graph with $\Omega (n^{2-1/s})$ edges.

The above norm graph approach also gives tight lower bounds on $z(m,n;s,t)$ for certain choices of $m,n$. In particular, for $s\geq 2$, $t>s!$, and $n^{1/t}\leq m\leq n^{1+1/t}$, we have

$z(m,n;s,t)=\Theta (mn^{1-1/s}).$

In the case $m=(1+o(1))n^{1+1/s}$, consider the bipartite graph $G$ with bipartition $V=V_{1}\cup V_{2}$, such that $V_{1}=\mathbb {F} _{p^{t}}\times \mathbb {F} _{p}^{\times }$ and $V_{2}=\mathbb {F} _{p^{t}}$. For $A\in V_{1}$ and $(B,b)\in V_{2}$, let $A\sim (B,b)$ in $G$ if and only if $N(A+B)=b$, where $N(\cdot )$ is the norm map defined above. To see that $G$ is $K_{s,t}$ -free, consider $s$ tuples $(B_{1},b_{1}),\ldots ,(B_{s},b_{s})\in V_{1}$. Observe that if the $s$ tuples have a common neighbor, then the $B_{i}$ must be distinct. Using the same upper bound on he number of solutions to the system of equations, we know that these $s$ tuples have at most $s!<t$ common neighbors.

Clique partitions

Using a related result on clique partition numbers, Alon, Mellinger, Mubayi and Verstraëte proved a tight lower bound on $z(m,n;2,t)$ for arbitrary $t$: if $m=(1+o(1))n^{t/2}$, then we have

$z(m,n;2,t)=(1+o(1))mn^{1/2}$.

For $2\leq t\leq n$, we say that a collection of subsets $A_{1},\dots ,A_{\ell }\subset [n]$ is a clique partition of $H\subset {[n] \choose t}$ if $\bigcup _{i=1}^{\ell }{A_{i} \choose t}$ form a partition of $H$. Observe that for any $k$, if there exists some $H\subset {[n] \choose t}$ of size $(1-o(1)){n \choose t}$ and $m=(1+o(1)){n \choose t}/{k \choose t}$, such that there is a partition of $H$ into $m$ cliques of size $k$, then we have $z(m,n;2,t)=km$. Indeed, supposing $A_{1},\dots ,A_{m}\subset [n]$ is a partition of $H$ into $m$ cliques of size $k$, we can let $G$ be the $m\times n$ bipartite graph with $V_{1}=\{A_{1},\dots ,A_{m}\}$ and $V_{2}=[n]$, such that $A_{i}\sim v$ in $G$ if and only if $v\in A_{i}$. Since the $A_{i}$ form a clique partition, $G$ cannot contain a copy of $K_{2,t}$.

It remains to show that such a clique partition exists for any $m=(1+o(1))n^{t/2}$. To show this, let $\mathbb {F} _{q}$ be the finite field of size $q$ and $V=\mathbb {F} _{q}\times \mathbb {F} _{q}$. For every polynomial $p(\cdot )$ of degree at most $t-1$ over $\mathbb {F} _{q}$, define $C_{p}=\{(x,p(x)):x\in \mathbb {F} _{q}\}\subset V$. Let ${\mathcal {C}}$ be the collection of all $C_{p}$, so that $|{\mathcal {C}}|=q^{t}=n^{t/2}$ and every $C_{p}$ has size $q={\sqrt {n}}$. Clearly no two members of ${\mathcal {C}}$ can share $t$ members. Since the only $t$-sets in $V$ that do not belong to $H$ are those that have at least two points sharing the same first coordinate, we know that almost all $t$-subsets of $V$ are contained in some $C_{p}$.

Randomized algebraic constructions

Alternative proofs of ${\text{ex}}(n,K_{s,t})=\Omega (n^{2-1/s})$ for $t$ sufficiently larger than $s$ were also given by Blagojević, Bukh and Karasev and by Bukh using the method of random algebraic constructions. The basic idea is to take a random polynomial $f:\mathbb {F} _{q}^{s}\times \mathbb {F} _{q}^{s}\rightarrow \mathbb {F} _{q}$ and consider the graph $G$ between two copies of $\mathbb {F} _{q}^{s}$ whose edges are all those pairs $(x,y)$ such that $f(x,y)=0$.

To start with, let $q$ be a prime power and $n=q^{2}$. Let

$f\in \mathbb {F} _{q}[x_{1},\dots ,x_{s},y_{1},\dots ,t_{s}]_{\leq s^{2}}$

be a random polynomial with degree at most $s^{2}$ in $X=(x_{1},\dots ,x_{s})$, degree at most $s^{2}$ in $Y=(y_{1},\dots ,y_{s})$, and furthermore satisfying $f(X,Y)=f(Y,X)$ for all $X,Y$. Let $G$ be the associated random graph on vertex set $\mathbb {F} _{q}^{s}$, such that two vertices $x$ and $y$ are adjacent if and only if $f(x,y)=0$.

To prove the asymptotic lower bound, it suffices to show that the expected number of edges in $G$ is $\Omega (q^{2s-1})$. For every $s$-subset $U\subset \mathbb {F} _{q}^{s}$, we let $Z_{U}$ denote the vertex subset of $\mathbb {F} _{q}^{s}\setminus U$ that "vanishes on $f(\cdot ,U)$":

$Z_{U}=\{x\in \mathbb {F} _{q}^{s}\setminus U:f(x,u)=0{\text{ for all }}u\in U\}$.

Using the Lang-Weil bound for polynomials $f(\cdot ,u)$ in $\mathbb {F} _{q}^{s}$, we can deduce that one always has $Z_{U}\leq C$ or $Z_{U}>q/2$ for some large constant $C$, which implies

$\mathbb {P} (|Z_{U}|>C)=\mathbb {P} (|Z_{U}|>q/2)$.

Since $f$ is chosen randomly over $\mathbb {F} _{q}$, it is not hard to show that the right-hand side probability is small, so the expected number of $s$-subsets $U$ with $|Z_{U}|>C$ also turned out to be small. If we remove a vertex from every such $U$, then the resulting graph is $K_{s,C+1}$ free, and the expected number of remaining edges is still large. This finishes the proof that ${\text{ex}}(n,K_{s,t})=\Omega (n^{2-1/s})$ for all $t$ sufficiently large with respect to $s$. More recently, there have been a number of results verifying the conjecture $z(m,n;s,t)=\Omega (n^{2-1/s})$ for different values of $s,t$, using similar ideas but with more tools from algebraic geometry.

Applications

The Kővári–Sós–Turán theorem has been used in discrete geometry to bound the number of incidences between geometric objects of various types. As a simple example, a set of $n$ points and $m$ lines in the Euclidean plane necessarily has no $K_{2,2}$, so by the Kővári–Sós–Turán it has $O(nm^{1/2}+m)$ point-line incidences. This bound is tight when $m$ is much larger than $n$, but not when $m$ and $n$ are nearly equal, in which case the Szemerédi–Trotter theorem provides a tighter $O(n^{2/3}m^{2/3}+n+m)$ bound. However, the Szemerédi–Trotter theorem may be proven by dividing the points and lines into subsets for which the Kővári–Sós–Turán bound is tight.

See also

• Biclique-free graph, sparse graphs whose sparsity is controlled by the solution to the Zarankiewicz problem
• Forbidden subgraph problem, a non-bipartite generalization of the Zarankiewicz problem
• Forbidden graph characterization, families of graphs defined by forbidden subgraphs of various types
• Turán's theorem, a bound on the number of edges of a graph with a forbidden complete subgraph