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:
“What had really caused the women’s movement was the additional years of human life. At the turn of the century women’s life expectancy was forty-six; now it was nearly eighty. Our groping sense that we couldn’t live all those years in terms of motherhood alone was “the problem that had no name.” Realizing that it was not some freakish personal fault but our common problem as women had enabled us to take the first steps to change our lives.”
—Betty Friedan (20th century)