Zarankiewicz problem

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.

[1] 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.

denotes the maximum possible number of edges in a bipartite graph

The Zarankiewicz problem, cages and finite geometry are strongly interrelated.

grid in such a way that no subset of rows and columns forms a complete

asks for the maximum number of edges in a bipartite graph with

In his original formulation of the problem, Zarankiewicz asked for the values of

subgraph, may be obtained by adding one of the long diagonals to the graph of a cube.

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: Kővári, Sós, and Turán originally proved this inequality for

[5] Shortly afterwards, Hyltén-Cavallius observed that essentially the same argument can be used to prove the above inequality.

are assumed to be constant, then asymptotically, using the big O notation, these formulae can be expressed as In the particular case

that matches the upper bound up to a constant, then by a simple sampling argument (on either an

bipartite graph that achieves the maximum edge number), we can show that for all

vertices uniformly at random from each side, and taking the expectation.

vertices on each side of its bipartition, twice as many edges and still no copy of

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.

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.

was verified by Kollár, Rónyai, and Szabó [15] and Alon, Rónyai, and Szabó [16] using the construction of norm graphs and projective norm graphs over finite fields.

, consider the norm graph NormGraphp,s with vertex set

using the projective norm graph, a construction slightly stronger than the above.

The above norm graph approach also gives tight lower bounds on

Using the same upper bound on he number of solutions to the system of equations, we know that these

Using a related result on clique partition numbers, Alon, Mellinger, Mubayi and Verstraëte [17] proved a tight lower bound on

To prove the asymptotic lower bound, it suffices to show that the expected number of edges in

, it is not hard to show that the right-hand side probability is small, so the expected number of

free, and the expected number of remaining edges is still large.

More recently, there have been a number of results verifying the conjecture

[8][20] 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.

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.