On a theorem of Erdős and Simonovits on graphs not containing the cube

2013/07/03 by Zoltán Füredi, Füredi, Zoltán
Mathematics · #05C35 #05D99 #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO #msc:05C35 #msc:05D99

paper · pdf · doi:10.48550/arxiv.1307.1062

15 pages. This is the preliminary version of my article in the Turan memorial volume

arxiv created 2013/07/03 · openalex publication_date 2013/07/03 · arxiv updated 2013/07/04 · openalex created_date 2022/09/30 · openalex updated_date 2026/07/28

Abstract

The cube Q is the usual 8-vertex graph with 12 edges. Here we give a new proof for a theorem of Erdős and Simonovits concerning the Turán number of the cube. Namely, it is shown that e(G) < n^8/5+(2n)^3/2 holds for any n-vertex cube-free graph G. Our aim is to give a self-contained exposition. We also point out the best known results and supply bipartite versions.

Related

• A Note on Turán Numbers and the Erdős-Stone-Simonovits Theorem
• Small dense subgraphs of a graph
• On the Turán number of the hypercube
• Many Turan exponents via subdivisions
• Disproof of a conjecture of Erdős and Simonovits on the Turán number of graphs with minimum degree 3