Complementation, local complementation, and switching in binary matroids

DOI10.1016/J.AAM.2020.102041MaRDI QIDQ2020035zbMATH OpenOpenAlexFDO

Authors Jagdeep Singh, James Oxley

Publication date 23 April 2021

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

local complementationswitchingbinary matroidcomplementation

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph operations (line graphs, products, etc.) (05C76)

Abstract: In 2004, Ehrenfeucht, Harju, and Rozenberg showed that any graph on a vertex set $V$ can be obtained from a complete graph on $V$ via a sequence of the operations of complementation, switching edges and non-edges at a vertex, and local complementation. The last operation involves taking the complement in the neighbourhood of a vertex. In this paper, we consider natural generalizations of these operations for binary matroids and explore their behaviour. We characterize all binary matroids obtainable from the binary projective geometry of rank $r$ under the operations of complementation and switching. Moreover, we show that not all binary matroids of rank at most $r$ can be obtained from a projective geometry of rank $r$ via a sequence of the three generalized operations. We introduce a fourth operation and show that, with this additional operation, we are able to obtain all binary matroids.

Recommendations

• Binary matroids and local complementation
• Complementarity in Oriented Matroids
• Transitivity of local complementation and switching on graphs.
• scientific article; zbMATH DE number 4202305
• LINEAR COMPLEMENTARITY AND ORIENTED MATROIDS
• Completeness in oriented matroids
• On the cogirth of binary matroids
• On the circuit-spectrum of binary matroids
• Decomposition of binary matroids
• scientific article; zbMATH DE number 1168010

Cites work

• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 3547309 (Why is no real title available?)
• scientific article; zbMATH DE number 1478125 (Why is no real title available?)
• Transitivity of local complementation and switching on graphs.

Cited in

(4)

• Transitivity of local complementation and switching on graphs.
• Binary matroids and local complementation
• Binary symmetric matrix inversion through local complementation
• scientific article; zbMATH DE number 4183450 (Why is no real title available?)

This page was built for publication: Complementation, local complementation, and switching in binary matroids

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