On subgraphs of tripartite graphs

2022/07/17 by Abhijeet Bhalkikar, Yi Zhao, Bhalkikar, Abhijeet +1
Computer Science · Engineering · Mathematics · #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2207.08055

openalex publication_date 2022/07/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Bollobás, Erdős, and Szemerédi [Discrete Math 13 (1975), 97--107] investigated a tripartite generalization of the Zarankiewicz problem: what minimum degree forces a tripartite graph with n vertices in each part to contain an octahedral graph K₃(2)? They proved that n+2^-1/2n^3/4 suffices and suggested it could be weakened to n+cn^1/2 for some constant c>0. In this note we show that their method only gives n+ (1+o(1)) n^11/12 and provide many constructions that show if true, n+ c n^1/2 is better possible.

Related

• Complete tripartite subgraphs of balanced tripartite graphs with large minimum degree
• The Zarankiewicz problem on tripartite graphs
• Zarankiewicz's problem via ε-t-nets
• On the existence of tripartite graphs and n-partite graphs
• C₄-free subgraphs of high degree with geometric applications