Matroide delta

En matemáticas, un delta-matroide o Δ-matroide es una familia de conjuntos que obedece un axioma de intercambio que generaliza un axioma de matroides . Una familia de conjuntos no vacía es un delta-matroide si, para cada dos conjuntos${\displaystyle E}$y${\displaystyle F}$en la familia y para cada elemento${\displaystyle e}$en su diferencia simétrica${\displaystyle E\triangle F}$, existe un${\displaystyle f\in E\triangle F}$de tal manera que${\displaystyle E\triangle \{e,f\}}$pertenece a la familia. Para los conjuntos base de un matroide, el axioma de intercambio correspondiente requiere además que${\displaystyle e\in E}$y${\displaystyle f\in F}$, asegurando que${\displaystyle E}$y${\displaystyle F}$tienen la misma cardinalidad. Para un delta-matroide, cualquiera de los dos elementos puede pertenecer a cualquiera de los dos conjuntos, y también se permite que los dos elementos sean iguales. ^{[ 1 ]} Una definición alternativa y equivalente es que una familia de conjuntos forma un delta-matroide cuando la envoltura convexa de sus vectores indicadores (el análogo de un politopo matroide ) tiene la propiedad de que la longitud de cada arista es uno o la raíz cuadrada de dos .

Los delta-matroides fueron definidos por André Bouchet en 1987. ^{[ 2 ]} Los algoritmos para la intersección de matroides y el problema de paridad de matroides pueden extenderse a algunos casos de delta-matroides. ^{[ 3 ] [ 4 ]}

Los delta-matroides también se han utilizado para estudiar problemas de satisfacción de restricciones . ^{[ 5 ]} Como caso especial, un delta-matroide par es un delta-matroide en el que todos los conjuntos tienen un número par de elementos, o todos los conjuntos tienen un número impar de elementos. Si un problema de satisfacción de restricciones tiene una variable booleana en cada arista de un grafo planar, y si las variables de las aristas incidentes a cada vértice del grafo están restringidas a pertenecer a un delta-matroide par (posiblemente un delta-matroide par diferente para cada vértice), entonces el problema puede resolverse en tiempo polinomial . Este resultado juega un papel clave en una caracterización de los problemas de satisfacción de restricciones booleanas planares que pueden resolverse en tiempo polinomial. ^{[ 6 ]}