Two conjectures in Ramsey-Turán theory

Hong Liu
Mathematics Institute, University of Warwick, Warwick, UK

2018/4/10 Tue 5PM

Given graphs H_{1},…, H_{k}, a graph G is (H_{1},…, H_{k})-free if there is a k-edge-colouring of G with no H_{i} in colour-i for all i in {1,2,…,k}. Fix a function f(n), the Ramsey-Turán function rt(n,H_{1},…,H_{k},f(n)) is the maximum size of an n-vertex (H_{1},…, H_{k})-free graph with independence number at most f(n). We determine rt(n,K_{3},K_{s},δn) for s in {3,4,5} and sufficiently small δ, confirming a conjecture of Erdős and Sós from 1979. It is known that rt(n,K_{8},f(n)) has a phase transition at f(n)=Θ(√(n\log n)). We prove that rt(n,K_{8},o(√(n\log n)))=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. Joint work with Jaehoon Kim and Younjin Kim.