Premium
A note on 3‐partite graphs without 4‐cycles
Author(s) -
Lv Zequn,
Lu Mei,
Fang Chunqiu
Publication year - 2020
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21742
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , induced subgraph , order (exchange) , discrete mathematics , finance , economics
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 2from 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 .