Zarankiewicz problem
From Wikipedia, the free encyclopedia
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]