The Kovari-Sos-Turan Theorem bounds the maximum number of edges a bipartite graph on a given number of vertices can have while still avoiding a complete bipartite subgraph of a specified size, showing that maximum grows at a rate governed by the size of the forbidden subgraph. Named for Tamas Kovari, Vera Sos and Pal Turan, it is a foundational result of extremal graph theory and supplies the standard upper bound used in the broader Zarankiewicz problem on forbidden bipartite subgraphs.
Facts
Classification
Statement Form Connections
Has Statement Form
In Branch
Source Zarankiewicz problem (Wikipedia)
Sources
1. Zarankiewicz problem (Wikipedia)
References, Kovari, Sos and Turan 1954Quote, References, Kovari, Sos and Turan 1954
Kővári, T.; T. Sós, V.; Turán, P. (1954), "On a problem of K. Zarankiewicz", Colloquium Math., 3: 50-57
Zarankiewicz problem (Wikipedia)
In Branch: Graph Theory, Article textQuote, In Branch: Graph Theory, Article text
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. It belongs to the field of extremal graph theory, a branch of combinatorics
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.