2018/03/13 by Kim, Jaehoon, Kim, Younjin, Liu, Hong · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1803.04721
Given graphs H1,…, Hk, a graph G is (H1,…, Hk)-free if there is a k-edge-colouring ϕ:E(G)→ [k] with no monochromatic copy of Hi with edges of colour i for each i∈[k]. Fix a function f(n), the Ramsey-Turán function \textrmRT(n,H1,…,Hk,f(n)) is the maximum number of edges in an n-vertex (H1,…,Hk)-free graph with independence number at most f(n). We determine \textrmRT(n,K3,Ks,δn) for s∈\3,4,5\ and sufficiently small δ, confirming a conjecture of Erdős and Sós from 1979. It is known that \textrmRT(n,K8,f(n)) has a phase transition at f(n)=Θ(√(nlog n)). However, the values of \textrmRT(n,K8, o(√(nlog n))) was not known. We determined this value by proving \textrmRT(n,K8,o(√(nlog n)))=(n2)/(4)+o(n2), answering a question of Balogh, Hu and Simonovits. The proofs utilise, among others, dependent random choice and results from graph packings.