Title of article
Sparse halves in triangle-free graphs
Author/Authors
Keevash، نويسنده , , Peter and Sudakov، نويسنده , , Benny، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2006
Pages
7
From page
614
To page
620
Abstract
One of Erdősʹ favourite conjectures was that any triangle-free graph G on n vertices should contain a set of n / 2 vertices that spans at most n 2 / 50 edges. We prove this when the number of edges in G is either at most n 2 / 12 or at least n 2 / 5 .
Keywords
extremal graph theory , triangle-free graphs , Local density
Journal title
Journal of Combinatorial Theory Series B
Serial Year
2006
Journal title
Journal of Combinatorial Theory Series B
Record number
1527718
Link To Document