Two conjectures in Ramsey-Turán theory

Abstract

Given graphs $H_1,\dots ,H_k$, a graph $G$ is $(H_1,\dots ,H_k)$-free if there is a $k$-edge-colouring $\varphi :E(G)\to [k]$ with no monochromatic copy of $H_i$ with edges of colour $i$ for each $i\in [k]$. Fix a function $f(n)$, the Ramsey-Turán function $\text{RT}(n,H_1,\dots ,H_k,f(n))$ is the maximum number of edges in an $n$-vertex $(H_1,\dots ,H_k)$-free graph with independence number at most $f(n)$. We determine $\text{RT}(n,K_3,K_s,\delta n)$ for $s\in \{3,4,5\}$ and sufficiently small $\delta$, confirming a conjecture of Erdős and Sós from 1979. It is known that $\text{RT}(n,K_8,f(n))$ has a phase transition at $f(n)=\Theta (\sqrt{n\log n})$. However, the values of $\text{RT}(n,K_8,o(\sqrt{n\log n}))$ was not known. We determined this value by proving $\text{RT}(n,K_8,o(\sqrt{n\log n}))=\frac{n^2}{4}+o(n^2)$, answering a question of Balogh, Hu and Simonovits. The proofs utilise, among others, dependent random choice and results from graph packings.

20 pages, 2 figures, 2 pages appendix