A New Proof on the Bipartite Turán Number of Bipartite Graphs

Abstract

The bipartite Turán number of a graph H , denoted by ex ( m , n ; H ) , is the maximum number of edges in any bipartite graph G = ( A , B ; E ( G ) ) with | A | = m and | B | = n which does not contain H as a subgraph. When min { m , n } > 2 t , the problem of determining the value of ex ( m , n ; K m − t , n − t ) has been solved by Balbuena et al. in 2007, whose proof focuses on the structural analysis of bipartite graphs. In this paper, we provide a new proof on the value of ex ( m , n ; K m − t , n − t ) by virtue of algebra method with the tool of adjacency matrices of bipartite graphs, which is inspired by the method using { 0 , 1 } -matrices due to Zarankiewicz [Problem P 101. Colloquium Mathematicum, 2(1951), 301].