Joints in graphs

DOI10.1016/J.DISC.2007.03.045MaRDI QIDQ2463464zbMATH OpenOpenAlexFDO

Authors Béla Bollobás, Vladimir Nikiforov

Publication date 12 December 2007

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2007.03.045

zbMATH Keywords

clique extremal graph joint stability Turán graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Review text

Let \(t_r (n)\) be the size of the \(r\)-partite \(n\)-element Turán graph, and given a graph \(G\), let \(js_q(G)\) be the largest \(t\) such that there exists \(t\) distinct \(q\)-cliques in \(G\) with a common edge. \textit{P. Erdős} [Čas. Pest. Mat. 94, 290--296 (1969; Zbl 0177.52502)] proved that if \(G\) is of order \(n\) and size \(e(G) > t_r(n)\), then \(js_{r+1}(G) \geq n^{r-1}/(10r)^{6r}\). In this paper, it is proven that if \(e(G) > t_r(n)\), then \(js_{r+1}(G) \geq n^{r-1} / r^{r+5}\). In fact, any \(n\)-element graph \(G\) of size \(t_r(n)\) -- besides the Turán graph of course -- satisfies \(js_{r+1}(G) > n^{r-1} / r^{r+5}\). The article is largely self-contained, and the proofs are sequences of mostly elementary but complex manipulations driven by careful bounds. The authors conclude with a `stability' result: if \(r \geq 2\) and \(n\) is sufficiently large and \(\alpha\) sufficiently small, then any \(n\)-element graph with more than \((1/2 - 1/2r - \alpha)n^2\) edges will either have \(js_{r+1} > (1 - r^{-3}) n^{r-1} / r^{r+5}\) \textit{or} admit an induced \(r\)-colorable subgraph of order at least \((1 - 2 \sqrt \alpha)n\) and minimal degree at least \((1 - r^{-1} - 4 \sqrt \alpha)n\).

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Joints in graphs

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