math_groups_discgeom

Turán numbers for K(s,t)-free graphs: topological obstructions and algebraic constructions

Pavle Blagojević, Boris Bukh, Roman Karasev— 2013

Focus Area 3: Topological connectivity and diameter of Discrete Structures 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.

TitleTurán numbers for K(s,t)-free graphs: topological obstructions and algebraic constructions
AuthorPavle Blagojević, Boris Bukh, Roman Karasev
Date201301
IdentifierDOI: 10.1007/s11856-012-0184-z
Source(s)
Appeared InIsrael Journal of Mathematics, October 2013, Volume 197, Issue 1, pp 199-214
TypeText