Zarankiewicz problem

Zarankiewicz problem   (Redirected from Kövari–Sós–Turán theorem) Jump to navigation Jump to search 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.[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] Contents 1 Problem statement 2 Examples 3 Upper bounds 4 Lower bounds 4.1 Incidence graphs in finite geometry 4.2 Norm graphs and projective norm graphs 4.3 Clique partitions 4.4 Randomized algebraic constructions 5 Applications 6 See also 7 References Problem statement A bipartite graph {displaystyle G=(Ucup V,E)} consists of two disjoint sets of vertices {displaystyle U} and {displaystyle V} , and a set of edges each of which connects a vertex in {displaystyle U} to a vertex in {displaystyle 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 {displaystyle U} and a vertex from {displaystyle V} is connected to each other. A complete bipartite graph in which {displaystyle U} has {displaystyle s} vertices and {displaystyle V} has {displaystyle t} vertices is denoted {displaystyle K_{s,t}} . If {displaystyle G=(Ucup V,E)} is a bipartite graph, and there exists a set of {displaystyle s} vertices of {displaystyle U} and {displaystyle t} vertices of {displaystyle V} that are all connected to each other, then these vertices induce a subgraph of the form {displaystyle K_{s,t}} . (In this formulation, the ordering of {displaystyle s} and {displaystyle t} is significant: the set of {displaystyle s} vertices must be from {displaystyle U} and the set of {displaystyle t} vertices must be from {displaystyle V} , not vice versa.) The Zarankiewicz function {displaystyle z(m,n;s,t)} denotes the maximum possible number of edges in a bipartite graph {displaystyle G=(Ucup V,E)} for which {displaystyle |U|=m} and {displaystyle |V|=n} , but which does not contain a subgraph of the form {displaystyle K_{s,t}} . As a shorthand for an important special case, {displaystyle z(n;t)} is the same as {displaystyle 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 {displaystyle z(n;t)} assuming that {displaystyle t} is a fixed constant, in the limit as {displaystyle n} goes to infinity.

For {displaystyle 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 {displaystyle G=(Ucup V,E)} can be visualized as the points of a {displaystyle |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, {displaystyle z(m,n;s,t)} denotes the maximum number of points that can be placed within an {displaystyle mtimes n} grid in such a way that no subset of rows and columns forms a complete {displaystyle stimes t} grid.[4] An alternative and equivalent definition is that {displaystyle z(m,n;s,t)} is the smallest integer {displaystyle k} such that every (0,1)-matrix of size {displaystyle mtimes n} with {displaystyle k+1} ones must have a set of {displaystyle s} rows and {displaystyle t} columns such that the corresponding {displaystyle stimes t} submatrix is made up only of 1's.

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

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

In his original formulation of the problem, Zarankiewicz asked for the values of {displaystyle z(n;3)} for {displaystyle n=4,5,6} . The answers were supplied soon afterwards by Wacław Sierpiński: {displaystyle z(4;3)=13} , {displaystyle z(5;3)=20} , and {displaystyle z(6;3)=26} .[4] The case of {displaystyle z(4;3)} is relatively simple: a 13-edge bipartite graph with four vertices on each side of the bipartition, and no {displaystyle 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 {displaystyle 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: {displaystyle 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 {displaystyle z(n;t)} .[5] Shortly afterwards, Hyltén-Cavallius observed that essentially the same argument can be used to prove the above inequality.[6] An improvement on the second term of the upper bound on {displaystyle z(n;t)} was given by Štefan Znám:[7] {displaystyle z(n;t)<(t-1)^{1/t}n^{2-1/t}+{frac {1}{2}}(t-1)n.} If {displaystyle s} and {displaystyle t} are assumed to be constant, then asymptotically, using the big O notation, these formulae can be expressed as {displaystyle z(m,n;s,t)=O(mn^{1-1/s}+n)} ; {displaystyle z(m,n;s,t)=O(nm^{1-1/t}+m)} . In the particular case {displaystyle m=n} , assuming without loss of generality that {displaystyle sleq t} , we have the asymptotic upper bound {displaystyle z(n,n;s,t)=O(n^{2-1/t}).} Lower bounds One can verify that among the two asymptotic upper bounds of {displaystyle z(m,n;s,t)} in the previous section, the first bound is better when {displaystyle m=o(n^{s/t})} , and the second bound becomes better when {displaystyle m=omega (n^{s/t})} . Therefore, if one can show a lower bound for {displaystyle 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 {displaystyle n^{t/s}times t} bipartite graph or an {displaystyle mtimes m^{s/t}} bipartite graph that achieves the maximum edge number), we can show that for all {displaystyle 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 {displaystyle sleq t} and {displaystyle mleq n^{s/t}} , we have {displaystyle z(m,n;s,t)=Omega (mn^{1-1/s})} ? [8] In the special case {displaystyle m=n} , up to constant factors, {displaystyle z(n,n;s,t)} has the same order as {displaystyle {text{ex}}(n,K_{s,t})} , the maximum number of edges in an {displaystyle n} -vertex (not necessarily bipartite) graph that has no {displaystyle K_{s,t}} as a subgraph. In one direction, a bipartite graph with {displaystyle n} vertices on each side and {displaystyle z(n,n;s,t)} edges must have a subgraph with {displaystyle n} vertices and at least {displaystyle z(n,n;s,t)/4} edges; this can be seen from choosing {displaystyle n/2} vertices uniformly at random from each side, and taking the expectation. In the other direction, we can transform a graph with {displaystyle n} vertices and no copy of {displaystyle K_{s,t}} into a bipartite graph with {displaystyle n} vertices on each side of its bipartition, twice as many edges and still no copy of {displaystyle K_{s,t}} , by taking its bipartite double cover.[9] Same as above, with the convention that {displaystyle sleq t} , it has been conjectured that {displaystyle z(n,n;s,t)=Theta (n^{2-1/s})} for all constant values of {displaystyle s,t} .[10] For some specific values of {displaystyle s,t} (e.g., for {displaystyle t} sufficiently larger than {displaystyle s} , or for {displaystyle 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 {displaystyle s=t=2} , a bipartite graph with {displaystyle n} vertices on each side, {displaystyle Omega (n^{3/2})} edges, and no {displaystyle K_{2,2}} may be obtained as the Levi graph, or point-line incidence graph, of a projective plane of order {displaystyle q} , a system of {displaystyle q^{2}+q+1} points and {displaystyle 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 {displaystyle K_{2,2}} -free graph with {displaystyle q^{2}+q+1} vertices and {displaystyle (q^{2}+q+1)(q+1)} edges. Since this lower bound matches the upper bound given by I. Reiman,[11] we have the asymptotic [12] {displaystyle z(n;2)=(1/2+o(1))n^{3/2}.} For {displaystyle s=t=3} , bipartite graphs with {displaystyle n} vertices on each side, {displaystyle Omega (n^{5/3})} edges, and no {displaystyle 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.[13] More generally, consider {displaystyle s=2} and any {displaystyle t} . Let {displaystyle mathbb {F} _{q}} be the {displaystyle q} -element finite field, and {displaystyle h} be an element of multiplicative order {displaystyle t} , in the sense that {displaystyle H={1,h,dots ,h^{t-1}}} form a {displaystyle t} -element subgroup of the multiplicative group {displaystyle mathbb {F} _{q}^{*}} . We say that two nonzero elements {displaystyle (a,b),(a',b')in mathbb {F} _{q}times mathbb {F} _{q}} are equivalent if we have {displaystyle a'=h^{d}a} and {displaystyle b'=h^{d}b} for some {displaystyle d} . Consider a graph {displaystyle G} on the set of all equivalence classes {displaystyle langle a,brangle } , such that {displaystyle langle a,brangle } and {displaystyle langle x,yrangle } are connected if and only if {displaystyle ax+byin H} . One can verify that {displaystyle G} is well-defined and free of {displaystyle K_{2,t+1}} , and every vertex in {displaystyle G} has degree {displaystyle q} or {displaystyle q-1} . Hence we have the upper bound [14] {displaystyle z(n,n;2,t+1)=(t^{1/2}+o(1))n^{3/2}.} Norm graphs and projective norm graphs For {displaystyle t} sufficiently larger than {displaystyle s} , the above conjecture {displaystyle z(n,n;s,t)=Theta (n^{2-1/s})} 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. For {displaystyle t>s!} , consider the norm graph NormGraphp,s with vertex set {displaystyle mathbb {F} _{p^{s}}} , such that every two vertices {displaystyle a,bin mathbb {F} _{p^{s}}} are connected if and only if {displaystyle N(a+b)=1} , where {displaystyle Ncolon mathbb {F} _{p^{s}}rightarrow mathbb {F} _{p}} is the norm map {displaystyle N(x)=xcdot 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 {displaystyle p^{s}} vertices and at least {displaystyle p^{2s-1}/2} edges. To see that this graph is {displaystyle K_{s,s!+1}} -free, observe that any common neighbor {displaystyle x} of {displaystyle s} vertices {displaystyle y_{1},ldots ,y_{s}in mathbb {F} _{p^{s}}} must satisfy {displaystyle 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 {displaystyle i=1,ldots ,s} , which a system of equations that has at most {displaystyle s!} solutions.

The same result can be proved for all {displaystyle t<(s-1)!} using the projective norm graph, a construction slightly stronger than the above. The projective norm graph ProjNormGraphp,s is the graph on vertex set {displaystyle mathbb {F} _{p^{s-1}}times mathbb {F} _{p}^{times }} , such that two vertices {displaystyle (X,x),(Y,y)} are adjacent if and only if {displaystyle N(X+Y)=xy} , where {displaystyle Ncolon mathbb {F} _{p^{s}}rightarrow mathbb {F} _{p}} is the norm map defined by {displaystyle N(x)=x^{(p^{s}-1)/(p-1)}} . By a similar argument to the above, one can verify that it is a {displaystyle K_{s,t}} -free graph with {displaystyle Omega (n^{2-1/s})} edges. The above norm graph approach also gives tight lower bounds on {displaystyle z(m,n;s,t)} for certain choices of {displaystyle m,n} .[16] In particular, for {displaystyle sgeq 2} , {displaystyle t>s!} , and {displaystyle n^{1/t}leq mleq n^{1+1/t}} , we have {displaystyle z(m,n;s,t)=Theta (mn^{1-1/s}).} In the case {displaystyle m=(1+o(1))n^{1+1/s}} , consider the bipartite graph {displaystyle G} with bipartition {displaystyle V=V_{1}cup V_{2}} , such that {displaystyle V_{1}=mathbb {F} _{p^{t}}times mathbb {F} _{p}^{times }} and {displaystyle V_{2}=mathbb {F} _{p^{t}}} . For {displaystyle Ain V_{1}} and {displaystyle (B,b)in V_{2}} , let {displaystyle Asim (B,b)} in {displaystyle G} if and only if {displaystyle N(A+B)=b} , where {displaystyle N(cdot )} is the norm map defined above. To see that {displaystyle G} is {displaystyle K_{s,t}} -free, consider {displaystyle s} tuples {displaystyle (B_{1},b_{1}),ldots ,(B_{s},b_{s})in V_{1}} . Observe that if the {displaystyle s} tuples have a common neighbor, then the {displaystyle B_{i}} must be distinct. Using the same upper bound on he number of solutions to the system of equations, we know that these {displaystyle s} tuples have at most {displaystyle s!q/2} for some large constant {displaystyle C} , which implies {displaystyle mathbb {P} (|Z_{U}|>C)=mathbb {P} (|Z_{U}|>q/2)} .

Since {displaystyle f} is chosen randomly over {displaystyle mathbb {F} _{q}} , it is not hard to show that the right-hand side probability is small, so the expected number of {displaystyle s} -subsets {displaystyle U} with {displaystyle |Z_{U}|>C} also turned out to be small. If we remove a vertex from every such {displaystyle U} , then the resulting graph is {displaystyle K_{s,C+1}} free, and the expected number of remaining edges is still large. This finishes the proof that {displaystyle {text{ex}}(n,K_{s,t})=Omega (n^{2-1/s})} for all {displaystyle t} sufficiently large with respect to {displaystyle s} . More recently, there have been a number of results verifying the conjecture {displaystyle z(m,n;s,t)=Omega (n^{2-1/s})} for different values of {displaystyle s,t} , using similar ideas but with more tools from algebraic geometry.[8][20] 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 {displaystyle n} points and {displaystyle m} lines in the Euclidean plane necessarily has no {displaystyle K_{2,2}} , so by the Kővári–Sós–Turán it has {displaystyle O(nm^{1/2}+m)} point-line incidences. This bound is tight when {displaystyle m} is much larger than {displaystyle n} , but not when {displaystyle m} and {displaystyle n} are nearly equal, in which case the Szemerédi–Trotter theorem provides a tighter {displaystyle 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.[21] 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 ^ 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, MR0506522. ^ Zarankiewicz, K. (1951), "Problem P 101", Colloq. Math., 2: 301. As cited by Bollobás (2004). ^ "Archived copy" (PDF). Archived from the original (PDF) on 2016-03-04. Retrieved 2014-09-16. ^ Jump up to: a b Sierpiński, W. (1951), "Sur un problème concernant un reseau à 36 points", Ann. Soc. Polon. Math., 24: 173–174, MR 0059876. ^ Kővári, T.; T. Sós, V.; Turán, P. (1954), "On a problem of K. Zarankiewicz" (PDF), Colloquium Math., 3: 50–57, doi:10.4064/cm-3-1-50-57, MR 0065617. ^ Hyltén-Cavallius, C. (1958), "On a combinatorical problem", Colloquium Mathematicum, 6: 59–65, doi:10.4064/cm-6-1-61-65, MR 0103158. As cited by Bollobás (2004). ^ Znám, Š. (1963), "On a combinatorical problem of K. Zarankiewicz", Colloquium Mathematicum, 11: 81–84, doi:10.4064/cm-11-1-81-84, MR 0162733. As cited by Bollobás (2004). ^ Jump up to: a b Conlon, David (2021), "Some remarks on the Zarankiewicz problem", Mathematical Proceedings of the Cambridge Philosophical Society: 1–7, doi:10.1017/S0305004121000475. ^ Bollobás (2004), Theorem 2.3, p. 310. ^ Bollobás (2004), Conjecture 15, p. 312. ^ Reiman, I. (1958), "Über ein Problem von K. Zarankiewicz", Acta Mathematica Academiae Scientiarum Hungaricae, 9 (3–4): 269–273, doi:10.1007/bf02020254, MR 0101250, S2CID 121692172. ^ Bollobás (2004), Corollary 2.7, p. 313. ^ Brown, W. G. (1966), "On graphs that do not contain a Thomsen graph", Canadian Mathematical Bulletin, 9 (3): 281–285, doi:10.4153/CMB-1966-036-2, MR 0200182. ^ 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. ^ 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, S2CID 26363618. ^ Jump up to: a b 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. ^ Alon, Noga; Mellinger, Keith E.; Mubayi, Dhruv; Verstraëte, Jacques (2012), "The de Bruijn-Erdős Theorem for Hypergraphs", Des. Codes Cryptogr., 65: 233–245. ^ Blagojević, Pavle; Bukh, Boris; Karasev, Roman (2013), "Turán numbers for Ks,t-free graphs: topological obstructions and algebraic constructions", Israel Journal of Mathematics, 197: 199–214, doi:10.1007/s11856-012-0184-z. ^ Bukh, Boris (2015), "Random algebraic construction of extremal graphs", Bull. London Math. Soc., 47: 939–945. ^ Bukh, Boris (2021), Extremal graphs without exponentially-small bicliques. ^ Matoušek, Jiří (2002), Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, New York: Springer-Verlag, pp. 65–68, doi:10.1007/978-1-4613-0039-7, ISBN 0-387-95373-6, MR 1899299. Categories: Extremal graph theoryMathematical problemsUnsolved problems in graph theoryBipartite graphs