The dismantling characterization of trivial matroid homomorphism reconfiguration

About 1 year old · traced to

Let NN be a matroid, and let Recol⁡M(N) \operatorname{Recol}_{\mathbb{M}}(N) denote the reconfiguration problem for matroid homomorphisms into NN. A matroid dismantles to a retract N′N' if a series of dismantling retractions has composition taking NN to N′N', 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. Recol⁡M(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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.