The Largest Eigenvalue and Bi-Average Degree of a Graph

We show that for a graph $G$ with the vertex set $V$ and the largest eigenvalue ${\lambda }_{\max }(G)$, letting $$M(G):=\underset{X,Y\subset V}{\max }\frac{e(X,Y)}{\sqrt{\mathrm{\mid }X\mathrm{\mid }\mathrm{\mid }Y\mathrm{\mid }}}$$ (where $e(X,Y)$ denotes the number of edges between $X$ and $Y$), we have $$M(G)\le {\lambda }_{\max }(G)\le (\frac{1}{4}\log \mathrm{\mid }V\mathrm{\mid }+1)\text{M}(G)\mathrm{.}$$ Here the lower bound is attained if $G$ is regular or bi-regular, whereas the logarithmic factor in the upper bound, conjecturally, can be improved — although we present an example showing that it cannot be replaced with a factor growing slower than $(\log \mathrm{\mid }V\mathrm{\mid }\mathrm{/}\log \log \mathrm{\mid }V\mathrm{\mid }{)}^{1\mathrm{/}8}$. Further refinements are established, particularly in the case where $G$ is bipartite.