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:
“Will women find themselves in the same position they have always been? Or do we see liberation as solving the conditions of women in our society?... If we continue to shy away from this problem we will not be able to solve it after independence. But if we can say that our first priority is the emancipation of women, we will become free as members of an oppressed community.”
—Ruth Mompati (b. 1925)