pith. sign in

arxiv: 1311.5818 · v2 · pith:GFFRAKQ7new · submitted 2013-11-22 · 🧮 math.CO

Sparse halves in dense triangle-free graphs

classification 🧮 math.CO
keywords graphsdegreefracleastconjectureaveragegraphminimum
0
0 comments X
read the original abstract

Erd\H{o}s conjectured that every triangle-free graph $G$ on $n$ vertices contains a set of $\lfloor n/2 \rfloor$ vertices that spans at most $n^2 /50$ edges. Krivelevich proved the conjecture for graphs with minimum degree at least $\frac{2}{5}n$. Keevash and Sudakov improved this result to graphs with average degree at least $\frac{2}{5}n$. We strengthen these results by showing that the conjecture holds for graphs with minimum degree at least $\frac{5}{14}n$ and for graphs with average degree at least $(\frac{2}{5} - \varepsilon)n$ for some absolute $\varepsilon >0$. Moreover, we show that the conjecture is true for graphs which are close to the Petersen graph in edit distance.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.