Tag: 허철원

A signed graph is a pair $(G,\mathrm{\Sigma })$ where $G$ is a graph and $\mathrm{\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,\mathrm{\Sigma })$ if $|C\cap \mathrm{\Sigma }|$ is even; otherwise, $C$ is odd. A matroid $M$ is an even-cycle matroid if there exists a signed graph $(G,\mathrm{\Sigma })$ such that circuits of $M$ precisely corresponds to inclusion-wise minimal non-empty even cycles of $(G,\mathrm{\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,{\mathrm{\Sigma }}_1)$ and $(G_2,{\mathrm{\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.