Sparse halves in dense triangle-free graphs

DOI10.1016/J.JCTB.2015.04.006MaRDI QIDQ490981zbMATH OpenOpenAlexFDO

Authors L. Yepremyan, Serguei Norine

Publication date 21 August 2015

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.5818

zbMATH Keywords

minimum degreeblowupedit distancePetersen graphtriangle-free graphsparse half

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07)

Abstract: ErdH{o}s conjectured that every triangle-free graph $G$ on $n$ vertices contains a set of $lfloorn/2floor$ vertices that spans at most $n^2/50$ edges. Krivelevich proved the conjecture for graphs with minimum degree at least $frac25n$. Keevash and Sudakov improved this result to graphs with average degree at least $frac25n$. We strengthen these results by showing that the conjecture holds for graphs with minimum degree at least $frac514n$ and for graphs with average degree at least $(frac25-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.

Recommendations

• Sparse halves in triangle-free graphs
• More about sparse halves in triangle-free graphs
• Sparse halves in K4‐free graphs
• On the asymptotic structure of sparse triangle free graphs
• On the Structure of Dense Triangle-Free Graphs
• Sparse graphs are near-bipartite
• Sparse graphs of high gonality
• Sparse hypergraphs: new bounds and constructions
• Triangles in regular graphs with density below one half
• Spanners in Sparse Graphs

Cites work

• scientific article; zbMATH DE number 3523543 (Why is no real title available?)
• A local density condition for triangles
• ODD Cycles of Specified Length in Non-Bipartite Graphs
• On Turán's \((3,4)\)-problem with forbidden subgraphs
• On the Caccetta-Häggkvist conjecture with forbidden subgraphs
• On the connection between chromatic number, maximal clique and minimal degree of a graph
• On the edge distribution in triangle-free graphs
• Some old and new problems in various branches of combinatorics
• Sparse halves in triangle-free graphs
• Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture
• Testing properties of graphs and functions
• The binding number of a graph and its Anderson number
• Triangle-Free Graphs with Large Degree
• Triangle-free four-chromatic graphs

Cited in

(7)

• K4$K_4$‐free graphs have sparse halves
• The Spectrum of Triangle-Free Graphs
• 10 problems for partitions of triangle-free graphs
• The regularity method for graphs with few 4‐cycles
• Sparse halves in triangle-free graphs
• More about sparse halves in triangle-free graphs
• Sparse halves in K4‐free graphs

This page was built for publication: Sparse halves in dense triangle-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490981)