Turán numbers for Kₛ,ₜ-free graphs: topological obstructions and algebraic constructions

الأصل · EN

We show that every hypersurface in ˢ× ˢ contains a large grid, i.e., the set of the form S× T, with S,T⊂ ˢ. We use this to deduce that the known constructions of extremal K₂,₂-free and K₃,₃-free graphs cannot be generalized to a similar construction of Kₛ,ₛ-free graphs for any s≥ 4. We also give new constructions of extremal Kₛ,ₜ-free graphs for large t.