A note on 3‐partite graphs without 4‐cycles. Issue 10 (22nd June 2020)

• Record Type: Journal Article
• Authors: Lv, Zequn; Lu, Mei; Fang, Chunqiu
• Is Part Of: Journal of combinatorial designs. Volume 28:Issue 10(2020:Oct.)
• Page Start: 753
• Page End: 757
• Publication Date: 2020-06-22
• Subjects: extremal number -- 3‐partite graph -- 4‐cycle; Combinatorial designs and configurations -- Periodicals; Configurations et schémas combinatoires -- Périodiques; 511.6
• DOI: 10.1002/jcd.21742
• Languages: English
• ISSNs: 1063-8539

Abstract

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 .