Donggyu Kim (김동규), 𝝘-graphic delta-matroids and their applications

Bouchet (1987) defined delta-matroids by relaxing the base exchange axiom of matroids. Oum (2009) introduced a graphic delta-matroid from a pair of a graph and its vertex subset. We define a $\mathrm{\Gamma }$-graphic delta-matroid for an abelian group $\mathrm{\Gamma }$, which generalizes a graphic delta-matroid.

For an abelian group $\mathrm{\Gamma }$, a $\mathrm{\Gamma }$-labelled graph is a graph whose vertices are labelled by elements of $\mathrm{\Gamma }$. We prove that a certain collection of edge sets of a $\mathrm{\Gamma }$-labelled graph forms a delta-matroid, which we call a $\mathrm{\Gamma }$-graphic delta-matroid, and provide a polynomial-time algorithm to solve the separation problem, which allows us to apply the symmetric greedy algorithm of Bouchet (1987) to find a maximum weight feasible set in such a delta-matroid. We also prove that a $\mathrm{\Gamma }$-graphic delta-matroid is a graphic delta-matroid if and only if it is even. We prove that every ${\mathbb{Z}}_p^k$-graphic delta matroid is represented by some symmetric matrix over a field of characteristic of order $p^k$, and if every $\mathrm{\Gamma }$-graphic delta-matroid is representable over a finite field $\mathbb{F}$, then $\mathrm{\Gamma }$ is isomorphic to ${\mathbb{Z}}_p^k$ and $\mathbb{F}$ is a field of order $p^{\ell }$ for some prime $p$ and positive integers $k$ and $\ell$.

This is joint work with Duksang Lee and Sang-il Oum.