Large joints in graphs

DOI10.1016/J.EJC.2010.07.010MaRDI QIDQ607362zbMATH OpenOpenAlexFDO

Authors Béla Bollobás, Vladimir Nikiforov

Publication date 22 November 2010

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: We show that if G is a graph of sufficiently large order n containing as many r-cliques as the r-partite Turan graph of order n; then for some C>0 G has more than Cn^(r-1) (r+1)-cliques sharing a common edge unless G is isomorphic to the the r-partite Turan graph of order n. This structural result generalizes a previous result that has been useful in extremal graph theory.

Review text

The Turan \(r\)-partite graph of order \(n\), \(T_{r}(n)\), is the complete \(r\)-partite graph so that the sizes of any two parts differ by at most 1. It is proved in the paper that if \(r\geq 2\), \(n>r^8\), and \(G\) is a graph of order \(n\) so that, for some \(s\leq r\), the number of \(s\)-cliques of \(G\) \(\geq \) the number of \(s\)-cliques of \(T_{k}(n)\), then \(G\) contains more than \(n^{r-1}/r^{2r+12}\) \(r\)-cliques sharing a common edge unless G=\(T_{r}(n)\). This result generalizes a result that turned out to be useful in extremal graph theory.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Large joints in graphs

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