In mathematics, a delta-matroid or Δ-matroid is a family of sets obeying an exchange axiom generalizing an axiom of matroids. A non-empty family of sets is a delta-matroid if, for every two sets E and F in the family, and for every element e in their symmetric difference \( {\displaystyle E\triangle F} \), there exists an \( {\displaystyle f\in E\triangle F} \) such that \( {\displaystyle E\triangle \{e,f\}} \) is in the family. For the basis sets of a matroid, the corresponding exchange axiom requires in addition that \( e\in E \) and \( f\in F \), ensuring that E and F have the same cardinality. For a delta-matroid, either of the two elements may belong to either of the two sets, and it is also allowed for the two elements to be equal.[1] An alternative and equivalent definition is that a family of sets forms a delta-matroid when the convex hull of its indicator vectors (the analogue of a matroid polytope) has the property that every edge length is either one or the square root of two.
Delta-matroids were defined by André Bouchet in 1987.[2] Algorithms for matroid intersection and the matroid parity problem can be extended to some cases of delta-matroids.[3][4]
Delta-matroids have also been used to study constraint satisfaction problems.[5] As a special case, an even delta-matroid is a delta-matroid in which either all sets have even number of elements, or all sets have an odd number of elements. If a constraint satisfaction problem has a Boolean variable on each edge of a planar graph, and if the variables of the edges incident to each vertex of the graph are constrained to belong to an even delta-matroid (possibly a different even delta-matroid for each vertex), then the problem can be solved in polynomial time. This result plays a key role in a characterization of the planar Boolean constraint satisfaction problems that can be solved in polynomial time.[6]
References
Chun, Carolyn (July 13, 2016), "Delta-matroids: Origins", The Matroid Union
Bouchet, André (1987), "Greedy algorithm and symmetric matroids", Mathematical Programming, 38 (2): 147–159, doi:10.1007/BF02604639, MR 0904585
Bouchet, André; Jackson, Bill (2000), "Parity systems and the delta-matroid intersection problem", The Electronic Journal of Combinatorics, 7: R14:1–R14:22, MR 1741336
Geelen, James F.; Iwata, Satoru; Murota, Kazuo (2003), "The linear delta-matroid parity problem", Journal of Combinatorial Theory, Series B, 88 (2): 377–398, doi:10.1016/S0095-8956(03)00039-X, MR 1983366
Feder, Tomás; Ford, Daniel (2006), "Classification of bipartite Boolean constraint satisfaction through delta-matroid intersection", SIAM Journal on Discrete Mathematics, 20 (2): 372–394, CiteSeerX 10.1.1.124.8355, doi:10.1137/S0895480104445009, MR 2257268
Kazda, Alexandr; Kolmogorov, Vladimir; Rolínek, Michal (December 2018), "Even delta-matroids and the complexity of planar Boolean CSPs", ACM Transactions on Algorithms, 15 (2): 22:1–22:33, arXiv:1602.03124, doi:10.1145/3230649
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
