A note on 3‐partite graphs without 4‐cycles. Issue 10 (22nd June 2020) - Lv, Zequn; Lu, Mei; Fang, Chunqiu
Abstract: Let C 4 be a cycle of order 4. Write e x ( n, n, n, C 4 ) for the maximum number of edges in a balanced 3‐partite graph whose vertex set consists of three parts, each has n vertices that have no subgraph isomorphic to C 4 . In this paper, we show that e x ( n, n, n, C 4 ) ≥ 3 2 n ( p + 1 ), where n = p ( p − 1 ) 2 and p is a prime number. Note that e x ( n, n, n, C 4 ) ≤ ( 3 2 2 + o ( 1 ) ) n 3 2 from Tait and Timmons's works. Since for every integer m, one can find a prime p such that m ≤ p ≤ ( 1 + o ( 1 ) ) m, we obtain that lim n → ∞ e x ( n, n, n, C 4 ) 3 2 2 n 3 2 = 1 .