Turán numbers for Ks,t-free graphs: Topological obstructions and algebraic constructions

Abstract

We show that every hypersurface in ℝs × ℝs contains a large grid, i.e., the set of the form S × T, with S, T ⊂ ℝ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 ≥ 4. We also give new constructions of extremal K s,t-free graphs for large t.