Turán numbers of theta graphs. (13th July 2020)

• Record Type: Journal Article
• Authors: Bukh, Boris; Tait, Michael
• Is Part Of: Combinatorics, probability and computing. Volume 29:Number 4(2020)
• Page Start: 495
• Page End: 507
• Publication Date: 2020-07-13
• Subjects: 05C35, -- 05D99, -- 05D40; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548320000012
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract: The theta graph ${\Theta _{\ell, t}}$ consists of two vertices joined by t vertex-disjoint paths, each of length $\ell $ . For fixed odd $\ell $ and large t, we show that the largest graph not containing ${\Theta _{\ell, t}}$ has at most ${c_\ell }{t^{1 - 1/\ell }}{n^{1 + 1/\ell }}$ edges and that this is tight apart from the value of ${c_\ell }$ .