











Title 


Speaker 
Hong Liu 


Date 
20180410 


Host 



Place 
KAIST 




Abstract : Given graphs H1,…, Hk, a graph G is (H1,…, Hk)free if there is a kedgecolouring of G with no Hi in colouri for all i in {1,2,…,k}. Fix a function f(n), the RamseyTurán function rt(n,H1,…,Hk,f(n)) is the maximum size of an nvertex (H1,…, Hk)free graph with independence number at most f(n). We determine rt(n,K3,Ks,δ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,K8,f(n)) has a phase transition at f(n)=Θ(√(nlog n)). We prove that rt(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. Joint work with Jaehoon Kim and Younjin Kim.






