Conformal Prediction Sets for Permutations as Bipartite Matching Graphs

Permutation prediction sets may contain factorially many complete assignments, making explicit enumeration unusable even when statistical calibration is straightforward. We study how to represent such sets exactly while preserving the one-to-one constraint. A bottleneck score assigns a permutation the nonconformity of its worst selected edge; at every threshold, the accepted permutations then coincide exactly with the perfect matchings of a bipartite graph of admissible edges. The graph uses at most $n^2$ edges and supports membership, feasibility, representative-assignment, feasible-partner, and localization queries without enumerating its perfect matchings. Split conformal calibration selects the graph threshold and gives finite-sample marginal coverage of the complete assignment under exchangeability. We characterize the scope of this representation: every threshold set of a permutation score is exactly graph-representable if and only if the score has a bottleneck form. Across synthetic, sorting, and frozen pretrained keypoint-matching experiments, the method achieves near-nominal coverage and exposes localized and global ambiguity. In sorting, roughly 149 edges represent a median $2.99\times 10^{12}$ accepted permutations.