Department of
Applied
Mathematics

Sparse halves in dense triangle-free graphs

Liana Yepremyan

McGill University

Abstract

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.