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 [math]\displaystyle{ E }[/math] and [math]\displaystyle{ F }[/math] in the family, and for every element [math]\displaystyle{ e }[/math] in their symmetric difference [math]\displaystyle{ E\triangle F }[/math], there exists an [math]\displaystyle{ f\in E\triangle F }[/math] such that [math]\displaystyle{ E\triangle\{e,f\} }[/math] is in the family. For the basis sets of a matroid, the corresponding exchange axiom requires in addition that [math]\displaystyle{ e\in E }[/math] and [math]\displaystyle{ f\in F }[/math], ensuring that [math]\displaystyle{ E }[/math] and [math]\displaystyle{ F }[/math] 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.