More about sparse halves in triangle-free graphs

DOI10.1070/SM9615zbMATH Open1485.05087arXiv2104.09406OpenAlexW4205357337MaRDI QIDQ3391027FDOQ3391027

Authors: Alexander Razborov 

Publication date: 28 March 2022

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

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.

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

Recommendations

• Sparse halves in triangle-free graphs
• Sparse halves in dense triangle-free graphs
• On the local density problem for graphs of given odd-girth
• On the local density problem for graphs of given odd-girth
• The Spectrum of Triangle-Free Graphs

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)

Cites Work

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

Cited In (6)

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

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)