The dismantling characterization of trivial matroid homomorphism reconfiguration

From papers

Let NN be a matroid, and let RecolM(N) \operatorname{Recol}_{\mathbb{M}}(N) denote the reconfiguration problem for matroid homomorphisms into NN. A matroid dismantles to a retract NN' if a series of dismantling retractions has composition taking NN to NN', where a dismantling retraction is a retraction adjacent to the identity map. Write M(K1)M^\ell(K_1) for the loop on one vertex and M(K2)M(K_2) for the matroid of an edge.

Dismantling characterization. RecolM(N)\operatorname{Recol}_{\mathbb{M}}(N) is trivial if and only if NN dismantles to the loop M(K1)M^\ell(K_1) or the edge M(K2)M(K_2).

This would extend the corresponding characterization for graphs, where triviality of the reconfiguration problem is equivalent to dismantlability. The preceding results establish that dismantling to either of these two small matroids is sufficient; the converse is posed as an analogue for matroids and remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Cheolwon Heo and Mark Siggers, “The complexity of matroid homomorphism reconfiguration”, arXiv:2503.19181 (2025).

Solutions 0

No solutions have been posted yet.