Cheolwon Heo (허철원), The complexity of the matroid-homomorphism problems

In this talk, we introduce homomorphisms between binary matroids that generalize graph homomorphisms. For a binary matroid $N$, we prove a complexity dichotomy for the problem ${\mathrm{H}\mathrm{o}\mathrm{m}}_{\mathbb{M}}(\mathrm{N})$ of deciding if a binary matroid $M$ admits a homomorphism to $N$. The problem is polynomial-time solvable if $N$ has a loop or has no circuits of odd length, and is otherwise $\mathrm{N}\mathrm{P}$-complete. We also get dichotomies for the list, extension, and retraction versions of the problem.
This is joint work with Hyobin Kim and Mark Siggers at Kyungpook National University.