In mathematics, a delta-matroid or Δ-matroid is a

family of sets In set theory and related branches of mathematics, a collection F of subsets of a given set S is called a family of subsets of S, or a family of sets over S. More generally, a collection of any sets whatsoever is called a family of sets, set fam ...

obeying an exchange axiom generalizing an axiom of

matroid In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...

s. 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 In mathematics, the symmetric difference of two sets, also known as the disjunctive union, is the set of elements which are in either of the sets, but not in their intersection. For example, the symmetric difference of the sets \ and \ is \. Th ...

E\triangle F

, there exists an

f\in E\triangle F

such that

E\triangle\

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. An alternative and equivalent definition is that a family of sets forms a delta-matroid when the

convex hull In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...

of its

indicator vector In mathematics, the indicator vector or characteristic vector or incidence vector of a subset ''T'' of a Set (mathematics), set ''S'' is the vector x_T := (x_s)_ such that x_s = 1 if s \in T and x_s = 0 if s \notin T. If ''S'' is countable set, cou ...

s (the analogue of a

matroid polytope In mathematics, a matroid polytope, also called a matroid basis polytope (or basis matroid polytope) to distinguish it from other polytopes derived from a matroid, is a polytope constructed via the bases of a matroid. Given a matroid M, the matroid ...

) has the property that every edge length is either one or the

square root of two The square root of 2 (approximately 1.4142) is a positive real number that, when multiplied by itself, equals the number 2. It may be written in mathematics as \sqrt or 2^, and is an algebraic number. Technically, it should be called the princip ...

. Delta-matroids were defined by André Bouchet in 1987. Algorithms for

matroid intersection In combinatorial optimization, the matroid intersection problem is to find a largest common independent set in two matroids over the same ground set. If the elements of the matroid are assigned real weights, the weighted matroid intersection proble ...

and the

matroid parity problem In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by as a common generalization of graph matching and matroid intersection. It ...

can be extended to some cases of delta-matroids. Delta-matroids have also been used to study

constraint satisfaction problem Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constra ...

s. 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 In computer science, the Boolean (sometimes shortened to Bool) is a data type that has one of two possible values (usually denoted ''true'' and ''false'') which is intended to represent the two truth values of logic and Boolean algebra. It is name ...

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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

. This result plays a key role in a characterization of the planar Boolean constraint satisfaction problems that can be solved in polynomial time.

References

{{reflist, refs= {{citation , last1 = Bouchet , first1 = André , last2 = Jackson , first2 = Bill , journal =

Electronic Journal of Combinatorics The ''Electronic Journal of Combinatorics'' is a peer-reviewed open access scientific journal covering research in combinatorial mathematics. The journal was established in 1994 by Herbert Wilf (University of Pennsylvania) and Neil Calkin (Georgi ...

, mr = 1741336 , page = R14:1–R14:22 , title = Parity systems and the delta-matroid intersection problem , url = https://www.combinatorics.org/Volume_7/Abstracts/v7i1r14.html , volume = 7 , year = 2000 {{citation , last = Bouchet , first = André , doi = 10.1007/BF02604639 , issue = 2 , journal =

Mathematical Programming Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...

, mr = 904585 , pages = 147–159 , title = Greedy algorithm and symmetric matroids , volume = 38 , year = 1987 {{citation, url=http://matroidunion.org/?p=1882, title=Delta-matroids: Origins, date=July 13, 2016, first=Carolyn, last=Chun, work=The Matroid Union {{citation , last1 = Feder , first1 = Tomás , last2 = Ford , first2 = Daniel , doi = 10.1137/S0895480104445009 , issue = 2 , journal =

SIAM Journal on Discrete Mathematics '' SIAM Journal on Discrete Mathematics'' is a peer-reviewed mathematics journal published quarterly by the Society for Industrial and Applied Mathematics (SIAM). The journal includes articles on pure and applied discrete mathematics. It was estab ...

, mr = 2257268 , pages = 372–394 , title = Classification of bipartite Boolean constraint satisfaction through delta-matroid intersection , volume = 20 , year = 2006, citeseerx = 10.1.1.124.8355 {{citation , last1 = Geelen , first1 = James F. , authorlink = Jim Geelen , last2 = Iwata , first2 = Satoru , last3 = Murota , first3 = Kazuo , doi = 10.1016/S0095-8956(03)00039-X , issue = 2 , journal =

Journal of Combinatorial Theory The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicat ...

, mr = 1983366 , pages = 377–398 , series = Series B , title = The linear delta-matroid parity problem , volume = 88 , year = 2003, doi-access = free {{citation , last1 = Kazda , first1 = Alexandr , last2 = Kolmogorov , first2 = Vladimir , last3 = Rolínek , first3 = Michal , arxiv = 1602.03124 , date = December 2018 , doi = 10.1145/3230649 , issue = 2 , journal =

ACM Transactions on Algorithms ''ACM Transactions on Algorithms'' (''TALG'') is a quarterly peer-reviewed scientific journal covering the field of algorithms. It was established in 2005 and is published by the Association for Computing Machinery. The editor-in-chief is Edith Co ...

, pages = 22:1–22:33 , title = Even delta-matroids and the complexity of planar Boolean CSPs , volume = 15 Matroid theory