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:
“It is part of the educator’s responsibility to see equally to two things: First, that the problem grows out of the conditions of the experience being had in the present, and that it is within the range of the capacity of students; and, secondly, that it is such that it arouses in the learner an active quest for information and for production of new ideas. The new facts and new ideas thus obtained become the ground for further experiences in which new problems are presented.”
—John Dewey (1859–1952)