the smallest integer such that every (0,1)-matrix of size with ones must have a set of rows and columns such that the corresponding submatrix is made up only of 1's. Examples The number asks for the maximum number of edges in a bipartite graph with vertices on each side that has no 4-cycle (its girth is six or more). Thus, (achieved by a three-edge path), and (a hexagon). In his original formulation of the problem, Zarankiewicz asked for the values of for . The answers were supplied soon afterwards by Wacław Sierpiński: , , and . The case of is relatively simple: a 13-edge bipartite graph with four vertices on each side of the bipartition, and no 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 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: Kővári, Sós, and Turán originally proved this inequality for . 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 was given by Štefan Znám: If and are assumed to be constant, then asymptotically, using the big O notation, these formulae can be expressed as ; . In the particular case , assuming without loss of generality that , we have the asymptotic upper bound Lower bounds One can verify that among the two asymptotic upper bounds of in the previous section, the first bound is better when , and the second bound becomes better when . Therefore, if one can show a lower bound for that matches the upper bound up to a constant, then by a simple sampling argument (on either an bipartite graph or an bipartite graph that achieves the maximum edge number), we can show that for all , one of the above two upper bounds is tight up to a constant. This leads to