Graphs with many r -cliques have large complete r -partite subgraphs

DOI10.1112/BLMS/BDM093MaRDI QIDQ5459244zbMATH OpenOpenAlexFDO

Authors Vladimir Nikiforov

Publication date 25 April 2008

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

cliquescomplete multipartite graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Abstract: We prove that for all $rgeq2$ and c>0, every graph of order n with at least cn^{r} cliques of order r contains a complete r-partite graph with each part of size $lfloor{c}^{r}lognfloor.$ This result implies a concise form of the ErdH{o}s-Stone theorem.

Recommendations

• Complete \(r\)-partite subgraphs of dense \(r\)-graphs
• Large joints in graphs
• Complete Subgraphs of r-partite Graphs
• The number of complete subgraphs of equi-partite graphs
• The maximal number of induced \(r\)-partite subgraphs

Cited in

(23)

• Complete \(r\)-partite subgraphs of dense \(r\)-graphs
• Turán's theorem inverted
• An extension of the Erdős-Stone theorem
• Supersaturation for subgraph counts
• Two Erdős-Hajnal-type theorems in hypergraphs
• Blowup Ramsey numbers
• Joints in graphs
• Degree powers in graphs: the Erdős-Stone theorem
• Complete partite subgraphs in dense hypergraphs
• Edge Distribution of Graphs with Few Copies of a Given Graph
• A spectral Erdős-Stone-Bollobás theorem
• Stability for large forbidden subgraphs
• Some extremal problems for hereditary properties of graphs
• On a topological version of Pach's overlap theorem
• Many \(T\) copies in \(H\)-free graphs
• On the density of a graph and its blowup
• Large joints in graphs
• Ramsey non-goodness involving books
• Unavoidable patterns in locally balanced colourings
• Blowing up Dirac's theorem
• The number of graphs with large forbidden subgraphs
• Some Turán-type results for the signless Laplacian spectral radius
• Unavoidable patterns

This page was built for publication: Graphs with many r -cliques have large complete r -partite subgraphs

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