Turán Number of an Induced Complete Bipartite Graph Plus an Odd Cycle. (16th July 2018)

• Record Type: Journal Article
• Authors: ERGEMLIDZE, BEKA; GYŐRI, ERVIN; METHUKU, ABHISHEK
• Is Part Of: Combinatorics, probability and computing. Volume 28:Number 2(2019)
• Page Start: 241
• Page End: 252
• Publication Date: 2018-07-16
• Subjects: Primary 05C35, -- Secondary 05C69; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548318000354
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : Let k ⩾ 2 be an integer. We show that if s = 2 and t ⩾ 2, or s = t = 3, then the maximum possible number of edges in a C 2 k +1 -free graph containing no induced copy of Ks, t is asymptotically equal to ( t − s + 1) 1/ s ( n /2) 2−1/ s except when k = s = t = 2. This strengthens a result of Allen, Keevash, Sudakov and Verstraëte [1], and answers a question of Loh, Tait, Timmons and Zhou [14].