Joints in graphs (Q2463464): Difference between revisions

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\).