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 but 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.^[2]

The Kővári–Sós–Turán theorem, named after Tamás Kővári, Vera T. Sós, and Pál Turán, provides an upper bound on the solution to the Zarankiewicz problem. When the forbidden complete bipartite subgraph has one side with at most three vertices, this bound has been proven to be within a constant factor of the correct answer. For larger forbidden subgraphs, it remains the best known bound, and has been conjectured to be tight. Applications of the Kővári–Sós–Turán theorem include bounding the number of incidences between different types of geometric object in discrete geometry.

Problem statement

A bipartite graph G = (U, 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, 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, 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.^[3]

The same problem can also be formulated in terms of digital geometry. The possible edges of a bipartite graph G = (U, V, E) can be visualized as the points of a |U| × |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 × n grid in such a way that no subset of rows and columns forms a complete s × t grid.^[4] 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 × n with k + 1 ones must have a set of s rows and t columns such that the corresponding s×t submatrix is made up only of 1's.

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) ≥ 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, and 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.^[4] 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 following upper bound was established by Tamás Kővári, Vera T. Sós and Pál Turán shortly after the problem had been posed,^[5] and has become known as the Kővári–Sós–Turán theorem:

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

In fact, Kővári, Sós, and Turán proved a similar inequality for z(n; t), but shortly afterwards, Hyltén-Cavallius observed that essentially the same argument can be used to prove the above inequality.^[6] An improvement to the constant factor in the second term of this formula, in the case of z(n; t), was given by Štefan Znám:^[7]

$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 big O notation, these formulas can be expressed as

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

and

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

Lower bounds

For t = 2, and for infinitely many values of n, a bipartite graph with n vertices on each side, Ω(n^3/2) edges, and no K_2,2 may be obtained as the Levi graph of a finite projective plane, a system of n points and lines in which each two points belong to a unique line and each two lines intersect in a unique point. The graph formed from this geometry has a vertex on one side of its bipartition for each point, a vertex on the other side of its bipartition for each line, and an edge for each incidence between a point and a line. The projective planes defined from finite fields of order p lead to K_2,2-free graphs with n = p² + p + 1 and with (p² + p + 1)(p + 1) edges. For instance, 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, showing that z(7; 2) ≥ 21. The lower bound on the Zarankiewicz function given by this family of examples matches an upper bound given by I. Reiman.^[8] Thus, for t = 2 and for those values of n for which this construction can be performed, it provides a precise answer to the Zarankiewicz problem. For other values of n, it follows from these upper and lower bounds that asymptotically^[9]

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

More generally,^[10]

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

For t = 3, and for infinitely many values of n, bipartite graphs with n vertices on each side, Ω(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.^[11]

It has been conjectured that

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

for all constant values of t, but this is only known for t = 2 and t = 3 by the above constructions.^[12] Tight bounds are also known for pairs (s, t) with widely differing sizes (specifically s ≥ (t − 1)!). For such pairs,

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

lending support to the above conjecture.^[13]

Non-bipartite graphs

Up to constant factors, z(n; t) also bounds the number of edges in an n-vertex graph (not required to be bipartite) that has no K_t,t subgraph. For, in one direction, a bipartite graph with z(n; t) edges and with n vertices on each side of its bipartition can be reduced to a graph with n vertices and (in expectation) z(n; t)/4 edges, by choosing n/2 vertices uniformly at random from each side. In the other direction, a graph with n vertices and no K_t,t can be transformed into a bipartite graph with n vertices on each side of its bipartition, twice as many edges, and still no K_t,t by taking its bipartite double cover.^[14]

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/3m^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.^[15]

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

References

1. Bollobás, Béla (2004), "VI.2 Complete subgraphs of r-partite graphs", Extremal Graph Theory, Mineola, NY: Dover Publications Inc., pp. 309–326, MR 2078877. Reprint of 1978 Academic Press edition, MR 0506522.
2. Zarankiewicz, K. (1951), "Problem P 101", Colloq. Math. 2: 301. As cited by Bollobás (2004).
3. http://www.cs.elte.hu/~hetamas/publ/DHSzFIN.pdf
4. Sierpiński, W. (1951), "Sur un problème concernant un reseau à 36 points", Ann. Soc. Polon. Math. 24: 173–174, MR 0059876.
5. Kővári, T.; T. Sós, V.; Turán, P. (1954), "On a problem of K. Zarankiewicz" (PDF), Colloquium Math. 3: 50–57, MR 0065617.
6. Hyltén-Cavallius, C. (1958), "On a combinatorical problem", Colloquium Mathematicum 6: 59–65, MR 0103158. As cited by Bollobás (2004).
7. Znám, Š. (1963), "On a combinatorical problem of K. Zarankiewicz", Colloquium Mathematicum 11: 81–84, MR 0162733. As cited by Bollobás (2004).
8. Reiman, I. (1958), "Über ein Problem von K. Zarankiewicz", Acta Mathematica Academiae Scientiarum Hungaricae 9: 269–273, doi:10.1007/bf02020254, MR 0101250. As cited by Bollobás (2004).
9. Bollobás (2004), Corollary 2.7, p. 313.
10. Füredi, Zoltán (1996), "New asymptotics for bipartite Turán numbers", Journal of Combinatorial Theory, Series A 75 (1): 141–144, doi:10.1006/jcta.1996.0067, MR 1395763.
11. Brown, W. G. (1966), "On graphs that do not contain a Thomsen graph", Canadian Mathematical Bulletin 9: 281–285, doi:10.4153/CMB-1966-036-2, MR 0200182.
12. Bollobás (2004), Conjecture 15, p. 312.
13. Alon, Noga; Rónyai, Lajos; Szabó, Tibor (1999), "Norm-graphs: variations and applications", Journal of Combinatorial Theory, Series B 76 (2): 280–290, doi:10.1006/jctb.1999.1906, MR 1699238. This work builds on an earlier bound, valid for larger values of s, of Kollár, János; Rónyai, Lajos; Szabó, Tibor (1996), "Norm-graphs and bipartite Turán numbers", Combinatorica 16 (3): 399–406, doi:10.1007/BF01261323, MR 1417348.
14. Bollobás (2004), Theorem 2.3, p. 310.
15. Matoušek, Jiří (2002), Lectures on discrete geometry, Graduate Texts in Mathematics 212, New York: Springer-Verlag, pp. 65–68, doi:10.1007/978-1-4613-0039-7, ISBN 0-387-95373-6, MR 1899299.