Id: arxiv/2607.19713 Url: https://arxiv.org/abs/2607.19713 Tags: math.CO, cs.CC Score: 0 Title: Counting spanning quasi-trees of ribbon graphs: determinants and #P-completeness Domain: math.CO Source: arxiv Authors: William Whistler Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-21 Page: https://delphi.science/r/arxiv/2607.19713 A quasi-tree of a connected ribbon graph is a spanning ribbon subgraph with exactly one boundary component; quasi-trees play the role of spanning trees in the topological graph theory of embedded graphs. We prove that counting them is #P-complete under polynomial-time Turing reductions, already for bouquets. The proof identifies every nonempty framed chord diagram, up to natural identifications, with a 4-regular map equipped with a distinguished A-trail, in such a way that quasi-trees correspond to A-trails, whose counting is #P-complete by a theorem of Ge and Štefankovič. Through the framed…