{
  "id": "1106.0811",
  "version": "v1",
  "published": "2011-06-04T11:04:21.000Z",
  "updated": "2011-06-04T11:04:21.000Z",
  "title": "The Largest Eigenvalue and Bi-Average Degree of a Graph",
  "authors": [
    "Vsevolod F. Lev"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "We show that for a graph $G$ with the vertex set $V$ and the largest eigenvalue $\\lambda_{\\max}(G)$, letting $$ M(G) := \\max_{X,Y \\subset V} \\frac{e(X,Y)}{\\sqrt{|X||Y|}} $$ (where $e(X,Y)$ denotes the number of edges between $X$ and $Y$), we have $$ M(G) \\le \\lambda_{\\max}(G) \\le \\big(\\frac14 \\log|V| + 1 \\big) \\M(G). $$ 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 |V|/\\log\\log|V|)^{1/8}$. Further refinements are established, particularly in the case where $G$ is bipartite.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-06-04T11:04:21.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C50"
    ],
    "keywords": [
      "largest eigenvalue",
      "bi-average degree",
      "factor growing slower",
      "vertex set",
      "upper bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1106.0811L"
    }
  }
}