{
  "id": "1407.6325",
  "version": "v1",
  "published": "2014-07-23T18:28:49.000Z",
  "updated": "2014-07-23T18:28:49.000Z",
  "title": "Log-Concavity of Combinations of Sequences and Applications to Genus Distributions",
  "authors": [
    "Jonathan L. Gross",
    "Toufik Mansour",
    "Thomas W. Tucker",
    "David G. L. Wang"
  ],
  "comment": "28 pages, 5 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "We formulate conditions on a set of log-concave sequences, under which any linear combination of those sequences is log-concave, and further, of conditions under which linear combinations of log-concave sequences that have been transformed by convolution are log-concave. These conditions involve relations on sequences called \\textit{synchronicity} and \\textit{ratio-dominance}, and a characterization of some bivariate sequences as \\textit{lexicographic}. We are motivated by the 25-year old conjecture that the genus distribution of every graph is log-concave. Although calculating genus distributions is NP-hard, they have been calculated explicitly for many graphs of tractable size, and the three conditions have been observed to occur in the \\textit{partitioned genus distributions} of all such graphs. They are used here to prove the log-concavity of the genus distributions of graphs constructed by iterative amalgamation of double-rooted graph fragments whose genus distributions adhere to these conditions, even though it is known that the genus polynomials of some such graphs have imaginary roots. A blend of topological and combinatorial arguments demonstrates that log-concavity is preserved through the iterations.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-07-23T18:28:49.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A15",
      "05A20",
      "05C10"
    ],
    "keywords": [
      "log-concavity",
      "applications",
      "log-concave sequences",
      "linear combination",
      "genus distributions adhere"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 28,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1407.6325G"
    }
  }
}