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

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.{{Citation needed|reason=I cannot find any reference where this is proved|date=June 2025}}

Delta-matroids were defined by André Bouchet in 1987.{{r|bouchet}}

Algorithms for matroid intersection and the matroid parity problem can be extended to some cases of delta-matroids.{{r|bj|gim}}

Delta-matroids have also been used to study constraint satisfaction problems.{{r|ff}} 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.{{r|kkr}}