Sparse halves in dense triangle-free graphs

DOI10.1016/J.JCTB.2015.04.006zbMATH Open1319.05043arXiv1311.5818OpenAlexW2002473456MaRDI QIDQ490981FDOQ490981

Authors: L. Yepremyan, Serguei Norine 

Publication date: 21 August 2015

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

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.

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

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

zbMATH Keywords

minimum degreeblowupedit distancePetersen graphtriangle-free graphsparse half

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

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

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)