Local and global average degree in bipartite graphs

Abstract

Let $F_{\mathrm{bip}}(n)$ denote the maximum, over all $n$-vertex bipartite graphs without isolated vertices, of the ratio of the minimum local average degree to the global average degree. We prove that $F_{\mathrm{bip}}(n)=\frac14\sqrt n+\frac38+o(1)$. This answers a problem posed by Tuza.

Disclosure

“them would obscure the main argument. We therefore leave these questions open and retain the √ clean asymptotic statement Fbip (n) = 14 n + 38 + o(1). Declaration on the use of AI The authors used generative AI tools to assist in discussing proof strategies, checking proofs, and improving exposition. All mathematical arguments, results, and conclusions were reviewed and verified by the authors. References [1] E. Bertram, P. Erdős, P. Horák, J.”

PDF page 8

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T18:54:20.500152Z

Structural counts