Tag: 김동규

Even delta-matroids generalize matroids, as they are defined by a certain basis exchange axiom weaker than that of matroids. One natural example of even delta-matroids comes from a skew-symmetric matrix over a given field $K$, and we say such an even delta-matroid is representable over the field $K$. Interestingly, a matroid is representable over $K$ in the usual manner if and only if it is representable over $K$ in the sense of even delta-matroids. The representability of matroids got much interest and was extensively studied such as excluded minors and representability over more than one field. Recently, Baker and Bowler (2019) integrated the notions of $K$-representable matroids, oriented matroids, and valuated matroids using tracts that are commutative ring-like structures in which the sum of two elements may output no element or two or more elements.

We generalize Baker-Bowler’s theory of matroids with coefficients in tracts to orthogonal matroids that are equivalent to even delta-matroids. We define orthogonal matroids with coefficients in tracts in terms of Wick functions, orthogonal signatures, circuit sets, and orthogonal vector sets, and establish basic properties on functoriality, duality, and minors. Our cryptomorphic definitions of orthogonal matroids over tracts provide proofs of several representation theorems for orthogonal matroids. In particular, we give a new proof that an orthogonal matroid is regular (i.e., representable over all fields) if and only if it is representable over ${\mathbb{F}}_2$ and ${\mathbb{F}}_3$, which was originally shown by Geelen (1996), and we prove that an orthogonal matroid is representable over the sixth-root-of-unity partial field if and only if it is representable over ${\mathbb{F}}_3$ and ${\mathbb{F}}_4$.

This is joint work with Tong Jin.

Tutte (1961) proved that every simple $3$-connected graph $G$ has an edge $e$ such that $G\setminus e$ or $G/e$ is simple $3$-connected, unless $G$ is isomorphic to a wheel. We call such an edge non-essential. Oxley and Wu (2000) proved that every simple $3$-connected graph has at least $2$ non-essential edges unless it is isomorphic to a wheel. Moreover, they proved that every simple $3$-connected graph has at least $3$ non-essential edges if and only if it is isomorphic to neither a twisted wheel nor a $k$-dimensional wheel with $k\ge 2$.

We prove analogous results for graphs with vertex-minors. For a vertex $v$ of a graph $G$, let $G\ast v$ be the graph obtained from $G$ by deleting all edges joining two neighbors of $v$ and adding edges joining non-adjacent pairs of two neighbors of $v$. This operation is called the local complementation at $v$, and we say two graphs are locally equivalent if one can be obtained from the other by applying a sequence of local complementations. A graph $H$ is a vertex-minor of a graph $G$ if $H$ is an induced subgraph of a graph locally equivalent to $G$. A split of a graph is a partition $(A,B)$ of its vertex set such that $|A|,|B|\ge 2$ and for some $A^{\prime }\subseteq A$ and $B^{\prime }\subseteq B$, two vertices $x\in A$ and $y\in B$ are adjacent if and only if $x\in A^{\prime }$ and $y\in B^{\prime }$. A graph is prime if it has no split.

A vertex $v$ of a graph is non-essential if at least two of three kinds of vertex-minor reductions at $v$ result in prime graphs. We prove that every prime graph with at least $5$ vertices has at least two non-essential vertices unless it is locally equivalent to a cycle. It is stronger than a theorem proved by Allys (1994), which states that every prime graph with at least $5$ vertices has a non-essential vertex unless it is locally equivalent to a cycle. As a corollary of our result, one can obtain the first result of Oxley and Wu. Furthermore, we show that every prime graph with at least $5$ vertices has at least $3$ non-essential vertices if and only if it is not locally equivalent to a graph with two specified vertices $x$ and $y$ consisting of at least two internally-disjoint paths from $x$ to $y$ in which $x$ and $y$ have no common neighbor.

This is joint work with Sang-il Oum.

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.