The Zarankiewicz problem in 3‐partite graphs. Issue 6 (13th February 2019)

• Record Type: Journal Article
• Authors: Tait, Michael; Timmons, Craig
• Is Part Of: Journal of combinatorial designs. Volume 27:Issue 6(2019:Jun.)
• Page Start: 391
• Page End: 405
• Publication Date: 2019-02-13
• Subjects: Bose‐Chowla -- extremal graph theory -- idon set; Combinatorial designs and configurations -- Periodicals; Configurations et schémas combinatoires -- Périodiques; 511.6
• DOI: 10.1002/jcd.21654
• Languages: English
• ISSNs: 1063-8539

Abstract

Abstract: Let F be a graph, k ≥ 2 be an integer, and write ex χ ≤ k ( n, F ) for the maximum number of edges in an n ‐vertex graph that is k ‐partite and has no subgraph isomorphic to F . The function ex χ ≤ 2 ( n, F ) has been studied by many researchers. Finding ex χ ≤ 2 ( n, K s, t ) is a special case of the Zarankiewicz problem. We prove an analog of the Kövári‐Sós‐Turán theorem for 3‐partite graphs by showing ex χ ≤ 3 ( n, K s, t ) ≤ 1 3 1 − 1 ∕ s t − 1 2 + o ( 1 ) 1 ∕ s n 2 − 1 ∕ s for 2 ≤ s ≤ t . Using Sidon sets constructed by Bose and Chowla, we prove that this upper bound is asymptotically best possible in the case that s = 2 and t ≥ 3 is odd, that is, ex χ ≤ 3 ( n, K 2, 2 t + 1 ) = t 3 n 3 ∕ 2 + o ( n 3 ∕ 2 ) for t ≥ 1 . In the cases of K 2, t and K 3, 3, we use a result of Allen, Keevash, Sudakov, and Verstraëte, to show that a similar upper bound holds for all k ≥ 3 and gives a better constant when s = t = 3 . Finally, we point out an interesting connection between difference families from design theory and ex χ ≤ 3 ( n, C 4 ) .