Duální matroid - Dual matroid

v teorie matroidů, dvojí matroidu ${displaystyle M}$ je další matroid ${displaystyle M ^ {ast}}$ který má stejné prvky jako ${displaystyle M}$, a ve kterém je sada nezávislá právě tehdy ${displaystyle M}$ má základnu disjunktní od ní.^[1][2][3]

Matroid duals se vrátí na původní papír o Hassler Whitney definování matroidů.^[4] Zobecňují na matroidy pojmy dualita grafu dualita.

Základní vlastnosti

Dualita je involuce: pro všechny ${displaystyle M}$, ${displaystyle (M ^ {ast}) ^ {ast} = M}$.^[1][3][4]

Alternativní definicí duálního matroidu je, že jeho základními sadami jsou doplňuje základních sad ${displaystyle M}$. Axiom základny směny, který se používá k definování matroidů z jejich základen, je komplementární, takže duál matroidu je nutně matroid.^[3]

The byty z ${displaystyle M}$ jsou komplementární k cyklickým množinám (svazkům obvodů) z ${displaystyle M ^ {ast}}$a naopak.^[3]

Li ${displaystyle r}$ je hodnostní funkce matroidu ${displaystyle M}$ na zemi ${displaystyle E}$, pak je hodnostní funkce duálního matroidu ${displaystyle r ^ {ast} (S) = r (Esetminus S) + | S | -r (E)}$.^[1][3][4]

Nezletilí

A matroid menší je vytvořen z většího matroidu ${displaystyle M}$ dvěma operacemi: omezením ${displaystyle Msetminus x}$ odstraní prvek ${displaystyle x}$ z ${displaystyle M}$ beze změny nezávislosti nebo hodnosti zbývajících sad a kontrakce ${displaystyle M / x}$ odstraní ${displaystyle x}$ z ${displaystyle M}$ po odečtení jednoho z řady každé sady, do které patří. Tyto dvě operace jsou dvojí: ${displaystyle Msetminus x = (M ^ {ast} / x) ^ {ast}}$ a ${displaystyle M / x = (M ^ {ast} setminus x) ^ {ast}}$. Nezletilý duál je tedy totéž jako duál nezletilého.^[5]

Self-dual matroidy

Individuální matroid je sebe-duální (zobecňující např self-dual mnohostěn pro grafické matroidy), pokud je izomorfní s vlastní dvojkou. Izomorfismus může, ale nemusí, ponechat prvky matroidu pevné. Libovolný algoritmus, který testuje, zda je daný matroid duální, přístup k matroidu prostřednictvím věštba nezávislosti, musí provést exponenciální počet věšteckých dotazů, a proto nemůže trvat polynomiální čas.^[6]

Matroidové rodiny

Mnoho důležitých rodin matroidů je samo-duální, což znamená, že matroid patří do rodiny právě tehdy, když ano. Mnoho dalších rodin matroidů přichází ve dvojicích. Mezi příklady tohoto jevu patří:

• The binární matroidy (matroidy reprezentovatelné nad GF (2) ), matroidy reprezentovatelné nad jakýmkoli jiným polem a pravidelné matroidy, jsou všechny sebe-dvojité rodiny.^[7]
• The gammoids tvoří samostatnou rodinu. Přísné gammoidy jsou dvojí příčné matroidy.^[8]
• The jednotné matroidy a rozdělit matroidy jsou sebe-duální. Duální až uniformní matroid ${displaystyle U {} _ {n} ^ {r}}$ je jednotný matroid ${displaystyle U {} _ {n} ^ {n-r}}$.^[9]
• Dvojí a grafický matroid je sám o sobě grafický, právě když je podkladový graf rovinný; matroid duálu rovinného grafu je stejný jako duál matroidu grafu. Rodina grafických matroidů rovinných grafů je tedy sebe-duální.^[10]
• Mezi grafickými matroidy a obecněji mezi binárními matroidy bipartitní matroidy (matroidy, ve kterých je každý obvod rovnoměrný) jsou dvojí Eulerianské matroidy (matroidy, které lze rozdělit do disjunktních obvodů).^[11][12]

Je otevřeným problémem, zda rodina algebraické matroidy je dvojí.

Reference