Title: Recognizing even cycle matroids
| Speaker: | Cheolwon Heo |
| Affiliation: | University of Waterloo |
| Room: | MC 6486 |
Abstract: A signed graph is a pair $(G,\Sigma)$, where $G$ is a graph and $\Sigma$ is a subset of the edges. An even cycle $C$ of the signed graph is an Eulerian subgraph of $G$ such that $|C \cap \Sigma|$ is even. A matroid is an even cycle matroid if there exists a signed graph where the cycles of the matroid correspond to the even cycles of the signed graph. Even cycle matroids are binary matroids. A long standing open problem is that of recognizing even cycle matroids: namely, given a 0,1 matrix representing a binary matroid $M$, we want in polynomial time in the size of the matrix, establish if $M$ is an even cycle matroid. We will give a polynomial time algorithm to recognize even cycle matroids. This is joint work with B. Guenin and I. Pivotto.