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. 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.
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.
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 Ks,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 Ks,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.)
...
Wikipedia