In the mathematical field of extremal graph theory, the Zarankiewicz problem asks how many edges can be added to a bipartite graph while avoiding a specific bipartite subgraph. Initially, the Polish mathematician Kazimierz Zarankiewicz proposed the problem of determining the maximum number of edges in an n-vertex graph with no complete bipartite graph K3,3 as a subgraph, for n ≤ 6; that is, in later notation, he asked for the values of the function Z3(n). The Kővári–Sós–Turán theorem gives a bound on the Zarankiewicz problem when the subgraph to be avoided is a complete bipartite graph.
Read more about Zarankiewicz Problem: Definition, Example, The Kővári–Sós–Turán Theorem
Famous quotes containing the word problem:
“And just as there are no words for the surface, that is,
No words to say what it really is, that it is not
Superficial but a visible core, then there is
No way out of the problem of pathos vs. experience.”
—John Ashbery (b. 1927)