More about sparse halves in triangle-free graphs

DOI10.1070/SM9615MaRDI QIDQ3391027zbMATH OpenOpenAlexFDO

Authors Alexander Razborov

Publication date 28 March 2022

Published in Sbornik: Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

extremal graph theorytriangle-free graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35)

Abstract: One of Erdos's conjectures states that every triangle-free graph on $n$ vertices has an induced subgraph on $n/2$ vertices with at most $n^2/50$ edges. We report several partial results towards this conjecture. In particular, we establish the new bound $frac271024n^2$ on the number of edges in general case. We completely prove the conjecture for graphs of girth $geq5$, for graphs with independence number $geq2n/5$ and for strongly regular graphs. Each of these three classes includes both known (conjectured) extremal configurations, the 5-cycle and the Petersen graph.

Recommendations

• Sparse halves in triangle-free graphs
• Sparse halves in dense triangle-free graphs
• The Spectrum of Triangle-Free Graphs

Cites work

• scientific article; zbMATH DE number 426334 (Why is no real title available?)
• scientific article; zbMATH DE number 3869331 (Why is no real title available?)
• scientific article; zbMATH DE number 3478931 (Why is no real title available?)
• scientific article; zbMATH DE number 3523543 (Why is no real title available?)
• A local density condition for triangles
• Flag algebras
• Graphs with Maximal Even Girth
• How to make a graph bipartite
• Non-three-colourable common graphs exist
• On Krein graphs without triangles
• On the edge distribution in triangle-free graphs
• On the maximum number of five-cycles in a triangle-free graph
• On the number of pentagons in triangle-free graphs
• Quasi-random graphs
• Some old and new problems in various branches of combinatorics
• Sparse halves in dense triangle-free graphs
• Sparse halves in triangle-free graphs
• The uniqueness of the strongly regular graph on 77 points
• There are exactly five biplanes with k = 11

Cited in

(6)

• Sparse halves in dense triangle-free graphs
• K4$K_4$‐free graphs have sparse halves
• The Spectrum of Triangle-Free Graphs
• 10 problems for partitions of triangle-free graphs
• Sparse halves in triangle-free graphs
• Sparse halves in K4‐free graphs

This page was built for publication: More about sparse halves in triangle-free graphs

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