On 13.06.2013 at 12:20 in S6, there is the following noon lecture:
Sparse halves in dense triangle-free graphs
This talk is about one of well-known conjectures of Erdős stating that every triangle-free graph G on n vertices should contain a set of floor(n/2) vertices that spans at most n^2/50 edges. Krivelevich proved the conjecture for graphs with minimum degree at least 2n/5. Keevash and Sudakov improved this result to graphs with average at least 2n/5. We strengthen these results by showing that the conjecture holds for graphs with minimum degree at least 5n/14 and average degree at least (2/5-epsilon)n for some absolute epsilon>0.
Webmaster: kamweb.mff.cuni.cz Modified: 19. 10. 2010