{"id":"arxiv/2607.22420","url":"https://arxiv.org/abs/2607.22420","tags":["math.CO","math.DG"],"score":0,"title":"Bipartite graphs, random graphs, and Lin--Lu--Yau curvature","domain":"math.CO","source":"arxiv","authors":["Huiqiu Lin","Zhe You","Da Zhao"],"reviews":0,"subject":"math.CO","summary":"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 {n}{2}\\rceil} \\text{ if $n\\geq 2m$}, \\mbox{and} \\ n-1 \\text{ if $m\\leq n< 2m$}.$ We also show that every bipartite graph of order $m+n$ with $m \\geq n$ and minimum degree at least $\\min\\{n, \\lfloor{\\frac{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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-24","reactions":{}}