Delta-matroid
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 formula_1 and formula_2 in the family, and for every element formula_3 in their symmetric difference formula_4, there exists an formula_5 such that formula_6 is in the family. For the basis sets of a matroid, the corresponding exchange axiom requires in addition that formula_7 and formula_8, ensuring that formula_1 and formula_2 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. 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. Algorithms for matroid intersection and the matroid parity problem can be extended to some cases of delta-matroids. Delta-matroids have also been used  to study constraint satisfaction problems. 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.