Minimal transitive factorizations supported on quasi-threshold graphs
We study the number of minimal transitive factorizations of the identity permutation in $S_n$ into transpositions supported on a quasi-threshold graph. We show that this number is always divisible by $(2n-2)!/n!$, which is the factorization count for a star graph, as shown by Irving and Rattan. To prove this, we give a combinatorial formula for the number of such factorizations as a weighted sum over a subset of the $n^{n-2}$ factorization trees, which are edge-weighted spanning trees satisfying certain flow constraints.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.31982
curl -X POST /api/v1/records/arxiv/2609.31982/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.31982/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'