{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-21","reactions":{}}