Delta-matroid

I matematik är en delta-matroid eller Δ-matroid en familj av uppsättningar som lyder ett utbyteaxiom som generaliserar ett axiom av matroider . En icke-tom familj av uppsättningar är en delta-matroid om, för varje två uppsättningar $E$ och $F$ i familjen, och för varje element $e$ i deras symmetriska skillnad ${\displaystyle E\triangle F} ,$$E\triangel \{e,f \}$ finns en $f\in E\triangle F$ så att är i familjen. För basuppsättningarna för en matroid kräver det motsvarande utbytesaxiomet dessutom att $e\in E$ och $f\in F$ , vilket säkerställer att $E$ och $F$ har samma kardinalitet. För en delta-matroid kan endera av de två elementen tillhöra någon av de två uppsättningarna, och det är också tillåtet att de två elementen är lika. En alternativ och likvärdig definition är att en familj av uppsättningar bildar en delta-matroid när det konvexa skrovet av dess indikatorvektorer (analogen till en matroidpolytop ) har egenskapen att varje kantlängd är antingen en eller kvadratroten ur två .

Delta-matroider definierades av André Bouchet 1987. Algoritmer för matroid-korsning och matroid-paritetsproblemet kan utvidgas till vissa fall av delta-matroider.

Delta-matroider har också använts för att studera problem med tillfredsställelse av begränsningar . Som ett specialfall är en jämn delta-matroid en delta-matroid där antingen alla uppsättningar har ett jämnt antal element eller alla uppsättningar har ett udda antal element. Om ett problem med begränsningstillfredsställelse har en boolesk variabel på varje kant av en plan graf, och om variablerna för kanterna som faller in på varje vertex av grafen är begränsade till att tillhöra en jämn delta-matroid (möjligen en annan jämn delta-matroid för varje vertex), då kan problemet lösas i polynomtid . Detta resultat spelar en nyckelroll i en karakterisering av de plana booleska begränsningsproblemen som kan lösas i polynomtid.