{
  "id": "math/9501231",
  "version": "v1",
  "published": "1995-01-01T00:00:00.000Z",
  "updated": "1995-01-01T00:00:00.000Z",
  "title": "A new series of dense graphs of high girth",
  "authors": [
    "Felix Lazebnik",
    "Vasiliy A. Ustimenko",
    "Andrew J. Woldar"
  ],
  "comment": "7 pages",
  "journal": "Bull. Amer. Math. Soc. (N.S.) 32 (1995) 73-79",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $k\\ge 1$ be an odd integer, $t=\\lfloor {{k+2}\\over 4}\\rfloor$, and $q$ be a prime power. We construct a bipartite, $q$-regular, edge-transitive graph $C\\!D(k,q)$ of order $v \\le 2q^{k-t+1}$ and girth $g \\ge k+5$. If $e$ is the the number of edges of $C\\!D(k,q)$, then $e =\\Omega(v^{1+ {1\\over {k-t+1}}})$. These graphs provide the best known asymptotic lower bound for the greatest number of edges in graphs of order $v$ and girth at least $g$, $ g\\ge 5$, $g \\not= 11,12$. For $g\\ge 24$, this represents a slight improvement on bounds established by Margulis and Lubotzky, Phillips, Sarnak; for $5\\le g\\le 23$, $g\\not= 11,12$, it improves on or ties existing bounds.",
  "revisions": [
    {
      "version": "v1",
      "updated": "1995-01-01T00:00:00.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "high girth",
      "dense graphs",
      "asymptotic lower bound",
      "odd integer",
      "prime power"
    ],
    "tags": [
      "journal article",
      "expository article"
    ],
    "publication": {
      "publisher": "AMS",
      "journal": "Bull. Amer. Math. Soc."
    },
    "note": {
      "typesetting": "TeX",
      "pages": 7,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "1995math......1231L"
    }
  }
}