Extremal graphs without exponentially small bicliques
Boris Bukh
Abstract
The Turán problem asks for the largest number of edges in an n-vertex graph not containing a fixed forbidden subgraph F. We construct a new family of graphs not containing Ks,t, for t=Cs, with Ω(n2−1∕s) edges matching the upper bound of Kövári, Sós, and Turán.
Topics & Concepts
CombinatoricsOmegaMathematicsGraphVertex (graph theory)Upper and lower boundsMatching (statistics)Discrete mathematicsPhysicsStatisticsQuantum mechanicsMathematical analysisLimits and Structures in Graph TheoryAdvanced Graph Theory ResearchGraph theory and applications