Nullity and Loop Complementation for Delta-Matroids

Abstract

We show that the symmetric difference distance measure for set systems, and more specifically for delta-matroids, corresponds to the notion of nullity for symmetric and skew-symmetric matrices. In particular, as graphs (i.e., symmetric matrices over GF(2)) may be seen as a special class of delta-matroids, this distance measure generalizes the notion of nullity in this case. We characterize delta-matroids in terms of equicardinality of minimal sets with respect to inclusion (in addition we obtain similar characterizations for matroids). In this way, we find that, e.g., the delta-matroids obtained after loop complementation and after pivot on a single element together with the original delta-matroid fulfill the property that two of them have equal "null space" while the third has a larger dimension.

Changes w.r.t. v4: different style, Section 8 is extended, and in addition a few small changes are made in the rest of the paper. 15 pages, no figures

References in corpus (3)

• The Group Structure of Pivot and Loop Complementation on Graphs and Set Systems
• Interlace Polynomials for Multimatroids and Delta-Matroids
• Maximal Pivots on Graphs with an Application to Gene Assembly

Cited by in corpus (12)

• Interlace Polynomials for Multimatroids and Delta-Matroids
• On the interplay between embedded graphs and delta-matroids
• Matroids, Delta-matroids and Embedded Graphs
• Quaternary Bicycle Matroids and the Penrose Polynomial for Delta-Matroids
• Partial-twuality polynomials of delta-matroids
• How many delta-matroids are there?
• Inductive tools for connected ribbon graphs, delta-matroids and multimatroids
• The adjacency matroid of a graph
• Quaternary matroids are vf-safe
• Orienting Transversals and Transition Polynomials of Multimatroids
• Isotropic matroids II: Circle graphs
• The excluded 3-minors for vf-safe delta-matroids