Nullity and loop complementation for delta-matroids

DOI10.1137/110854692MaRDI QIDQ5300507zbMATH OpenOpenAlexFDO

Authors Robert Brijder, Hendrik Jan Hoogeboom

Publication date 27 June 2013

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.4497

zbMATH Keywords

principal pivot transformlocal complementation4-regular graphdelta-matroidinterlace polynomial

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Theory of matrix inversion and generalized inverses (15A09) Combinatorial aspects of matroids and geometric lattices (05B35) Graph operations (line graphs, products, etc.) (05C76)

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.

Recommendations

• The delta-sum of matching delta-matroids
• Representability of \(\bigtriangleup\)-matroids over \(GF(2)\)
• Delta matroids whose fundamental graphs are bipartite
• Characterizing matroids whose bases form graphic delta-matroids
• Delta-matroids for graph theorists

Cited in

(12)

• Recombination faults in gene assembly in ciliates modeled using multimatroids
• The adjacency matroid of a graph
• Interlace polynomials for multimatroids and delta-matroids
• Inductive tools for connected delta-matroids and multimatroids
• The excluded 3-minors for vf-safe delta-matroids
• Partial-twuality polynomials of delta-matroids
• Isotropic matroids. II: Circle graphs
• How many delta-matroids are there?
• Isotropic matroids. I: Multimatroids and neighborhoods
• An activities expansion of the transition polynomial of a multimatroid
• Matroids, delta-matroids and embedded graphs
• Orienting transversals and transition polynomials of multimatroids

This page was built for publication: Nullity and loop complementation for delta-matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300507)