{
  "abstract": "Dittmer and Pak proved that counting the linear extensions of the incidence poset I G of a graph G is #P-complete, positively resolving a conjecture in [1] about height-2 posets, and specifically solving a problem mentioned in [7] about incidence posets. We show that the problem remains #P-complete when G is restricted to bipartite graphs; consequently, computing exactly the volume of the McCormick relaxation of a bilinear program is #P-hard. As in their work, we compute the count modulo many primes p, gluing the input to a gadget graph whose own count is known modulo p. Here, the gadget must be bipartite, and we evaluate its residue by a block decomposition of the count modulo p together with a binomial cancellation identity; the same method gives a short proof of the residue of the Dittmer-Pak gadget, correcting a small non-fatal calculation error in their paper. In contrast, we show that the count can be computed in polynomial time for graphs of bounded neighborhood diversity, for example complete bipartite graphs, by a recursion over the numbers of remaining vertices of each type.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": null,
  "author_total": 1,
  "authors": [
    {
      "name": "Jon Lee"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/86gepzj9scrte.bib",
  "cited_by": 0,
  "doi": null,
  "fulltext_url": null,
  "id": "86gepzj9scrte",
  "issns": [],
  "landing_url": "https://hal.science/hal-05793069v1",
  "language": "en",
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "https://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": null,
  "native_subjects": [
    [
      "hal",
      "0.math"
    ]
  ],
  "openalex": null,
  "pdf_url": "https://hal.science/hal-05793069/document",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-11",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/86gepzj9scrte.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:17:54Z",
      "native_id": "hal-05793069",
      "source": "hal",
      "url": "https://hal.science/hal-05793069v1"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "hal:0.math",
      "subfield": "general"
    }
  ],
  "title": "Counting linear extensions of incidence posets of bipartite graphs is #P-complete",
  "title_text": "Counting linear extensions of incidence posets of bipartite graphs is #P-complete",
  "type": "preprint",
  "updated_at": "2026-10-30T12:17:54Z",
  "url": "https://research.draconitic.com/paper/86gepzj9scrte",
  "venue": "HAL",
  "versions": []
}