Turán numbers for $K_{s,t}$-free graphs: topological obstructions and algebraic constructions

Abstract

We show that every hypersurface in ${\mathbb{R}}^s\times {\mathbb{R}}^s$ contains a large grid, i.e., the set of the form $S\times T$, with $S,T\subset {\mathbb{R}}^s$. We use this to deduce that the known constructions of extremal $K_{2,2}$-free and $K_{3,3}$-free graphs cannot be generalized to a similar construction of $K_{s,s}$-free graphs for any $s\ge 4$. We also give new constructions of extremal $K_{s,t}$-free graphs for large $t$.

Fixed a small mistake in the application of Proposition 1

Cited by in corpus (6)

• A bound on the number of edges in graphs without an even cycle
• Graphs with few paths of prescribed length between any two vertices
• On Turán exponents of bipartite graphs
• Some remarks on the Zarankiewicz problem
• Some tight lower bounds for Turán problems via constructions of multi-hypergraphs
• A polynomial resultant approach to algebraic constructions of extremal graphs