TITLE:
A New Proof on the Bipartite Turán Number of Bipartite Graphs
AUTHORS:
Shiqian Wang
KEYWORDS:
Bipartite Turán Number, Adjacency Matrix, Zarankiewicz Problem
JOURNAL NAME:
Engineering,
Vol.16 No.9,
September
27,
2024
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 }>2t
, 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].