On a theorem of Erd\H{o}s and Simonovits on graphs not containing the cube

zbMATH Open1301.05187arXiv1307.1062MaRDI QIDQ2874919

Zoltán Füredi

Publication date: 12 August 2014

Abstract: The cube Q is the usual 8-vertex graph with 12 edges. Here we give a new proof for a theorem of ErdH{o}s and Simonovits concerning the Tur'an 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.

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

zbMATH Keywords

cube graphbipartite extremal graphsTurán graph problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Extremal combinatorics (05D99)

Related Items (3)

On Turán exponents of bipartite graphs ⋮ Extremal graphs for the odd prism ⋮ Turán Numbers of Bipartite Subdivisions

This page was built for publication: On a theorem of Erd\H{o}s and Simonovits on graphs not containing the cube

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