기초과학연구원 이산수학그룹
On May 2, 2022, Cheolwon Heo (허철원) from Sungkyunkwan University gave a talk at the Discrete Math Seminar on the dichotomy of the problem on deciding the existence of a binary matroid homomorphism to a fixed binary matroid. The title of his talk was “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 $\rm{Hom}_\mathbb{M}(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 $\rm{NP}$-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.
On August 31, 2021, Cheolwon Heo (허철원) gave a talk on representations of even-cycle matroids at the Discrete Math Seminar. He finished his Ph.D. recently from the University of Waterloo and begins his postdoc position at the Applied Algebra and Optimization Research Center (AORC) of Sungkyunkwan University on September 1, 2021. The title of his talk is “Representations of even-cycle matroids”.
A signed graph is a pair $(G,\Sigma)$ where $G$ is a graph and $\Sigma$ is a subset of edges of $G$. A cycle $C$ of $G$ is a subset of edges of $G$ such that every vertex of the subgraph of $G$ induced by $C$ has an even degree. We say that $C$ is even in $(G,\Sigma)$ if $|C \cap \Sigma|$ is even; otherwise, $C$ is odd. A matroid $M$ is an even-cycle matroid if there exists a signed graph $(G,\Sigma)$ such that circuits of $M$ precisely corresponds to inclusion-wise minimal non-empty even cycles of $(G,\Sigma)$. For even-cycle matroids, two fundamental questions arise:
(1) what is the relationship between two signed graphs representing the same even-cycle matroids?
(2) how many signed graphs can an even-cycle matroid have?
For (a), we characterize two signed graphs $(G_1,\Sigma_1)$ and $(G_2,\Sigma_2)$ where $G_1$ and $G_2$ are $4$-connected that represent the same even-cycle matroids.
For (b), we introduce pinch-graphic matroids, which can generate exponentially many representations even when the matroid is $3$-connected. An even-cycle matroid is a pinch-graphic matroid if there exists a signed graph with a pair of vertices such that every odd cycle intersects with at least one of them. We prove that there exists a constant $c$ such that if a matroid is even-cycle matroid that is not pinch-graphic, then the number of representations is bounded by $c$. This is joint work with Bertrand Guenin and Irene Pivotto.