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.
|
