2026/07/24 by Huiqiu Lin, Zhe You, Da Zhao
#math.CO #math.DG
Let G = (X, Y; E) be a bipartite graph with parts X and Y where |X|=m and |Y|=n. We show that every bipartite graph with more than mn - D(m,n) edges has positive Lin--Lu--Yau curvature, where D(m,n)=m-2+\lceil\frac n2\rceil if n≥ 2m, and n-1 if m≤ n< 2m. We also show that every bipartite graph of order m+n with m ≥ n and minimum degree at least min\n, \lfloor(m+n)/(3)\rfloor+1\ has positive Lin--Lu--Yau curvature. Both bounds are sharp. Meanwhile probabilistically we can relax the edge density conditions in above results. It is shown that relatively dense random bipartite graph is positively curved. All of our proofs are based on a new formula for Lin--Lu--Yau curvature of bipartite graphs.