Matroid na objednávku - Base-orderable matroid

V matematice, a základní matroid je matroid který má následující další vlastnost související s základy matroidu.^[1]

Pro libovolné dvě základny ${ displaystyle A}$ a ${ displaystyle B}$ existuje a proveditelná výměna bijekce, definované jako bijekce ${ displaystyle f}$ z ${ displaystyle A}$ na ${ displaystyle B}$, tak, že pro každého ${ displaystyle a v A setminus B}$, oba ${ displaystyle (A setminus {a }) pohár {f (a) }}$ a ${ displaystyle (B setminus {f (a) }) pohár {a }}$ jsou základny.

Majetek představili Brualdi a Scrimger.^[2][3] A silně objednatelný matroid má následující silnější vlastnost:

Pro libovolné dvě základny ${ displaystyle A}$ a ${ displaystyle B}$, tady je silná proveditelná bijekce, definované jako bijekce ${ displaystyle f}$ z ${ displaystyle A}$ na ${ displaystyle B}$, tak, že pro každého ${ displaystyle X subseteq A}$, oba ${ displaystyle (A setminus X) pohár f (X)}$ a ${ displaystyle (B setminus f (X)) pohár X}$ jsou základny.

Vlastnost v kontextu

Základní objednávatelnost klade na funkci dva požadavky ${ displaystyle f}$:

1. Měla by to být bijekce;
2. Pro každého ${ displaystyle a v A setminus B}$, oba ${ displaystyle (A setminus {a }) pohár {f (a) }}$ a ${ displaystyle (B setminus {f (a) }) pohár {a }}$ by měly být základny.

Samotnou každou z těchto vlastností lze snadno uspokojit:

1. Všechny základy daného matroidu mají stejnou mohutnost, takže existují n! bijekce mezi nimi (kde n je běžná velikost základen). Není ale zaručeno, že jedna z těchto bijekcí splňuje vlastnost 2.
2. Všechny základny ${ displaystyle A}$ a ${ displaystyle B}$ matroid uspokojit vlastnost směny symetrické báze, což je pro každého ${ displaystyle a v A setminus B}$, existují nějaké ${ displaystyle f (a) v B setminus A}$, takže oba ${ displaystyle (A setminus {a }) pohár {f (a) }}$ a ${ displaystyle (B setminus {f (a) }) pohár {a }}$ jsou základny. Není však zaručeno, že výsledná funkce f bude bijekce - je možné, že několik ${ displaystyle a}$ se shodují se stejnými ${ displaystyle f (a)}$.

Matroidy, které nelze objednat na základně

Některé matroidy nelze objednat na základně. Pozoruhodným příkladem je grafický matroid na grafu K.₄, tj. matroid, jehož základny jsou kostry stromu klika na 4 vrcholech.^[1] Označte vrcholy K.₄ o 1,2,3,4 a jeho hrany o 12,13,14,23,24,34. Všimněte si, že základny jsou:

• {12,13,14}, {12,13,24}, {12,13,34}; {12,14,23}, {12,14,34}; {12,23,24}, {12,23,34}; {12,24,34};
• {13,14,23}, {13,14,24}; {13,23,24}, {13,23,34}; {13,24,34};
• {14,23,24}, {14,23,34}; {14,24,34}.

Zvažte dvě základny A = {12,23,34} a B = {13,14,24}, a předpokládejme, že existuje funkce F uspokojení směnného majetku (vlastnost 2 výše). Pak:

• F(12) musí se rovnat 14: to nemůže být 24, protože A {12} + {24} = {23,24,34} což není základ; nemůže to být 13, protože B {13} + {12} = {12,14,24}, což není základ.
• F(34) musí se rovnat 14: to nemůže být 24, protože B {24} + {34} = {13,14,34} což není základ; nemůže to být 13, protože A {34} + {13} = {12,13,23}, což není základ.

Pak F není bijekce - mapuje dva prvky A na stejný prvek B.

Existují matroidy, které lze objednat na základně, ale ne na silnou bázi.^[4][1]

Matroidy, které lze objednat na základně

Každý dělící matroid je možné objednat na základně. Každý příčný matroid je silně objednatelný.^[2]

Vlastnosti

V základně uspořádatelných matroidech existuje proveditelná směna bijekce nejen mezi základnami, ale také mezi libovolnými dvěma nezávislými sadami stejné mohutnosti, tj. Libovolnými dvěma nezávislými sadami ${ displaystyle A}$ a ${ displaystyle B}$ takhle ${ displaystyle | A | = | B |}$.

To lze dokázat indukcí rozdílu mezi velikostí množin a velikostí základny (připomeňme, že všechny základny matroidu mají stejnou velikost). Pokud je rozdíl 0, pak jsou množiny ve skutečnosti základnami a vlastnost vyplývá z definice základně uspořádatelných matroidů. Jinak můžeme vlastnost augmentace matroidu rozšířit ${ displaystyle A}$ do nezávislé množiny ${ displaystyle A cup {x }}$ a rozšířit ${ displaystyle B}$ do nezávislé množiny ${ displaystyle B cup {y }}$. Potom, podle indukčního předpokladu, existuje reálná směnná bijekce ${ displaystyle f}$ mezi ${ displaystyle A cup {x }}$ a ${ displaystyle B cup {y }}$. Li ${ displaystyle f (x) = y}$, pak omezení ${ displaystyle f}$ na ${ displaystyle A}$ a ${ displaystyle B}$ je proveditelná devizová bijekce. V opačném případě, ${ displaystyle f ^ {- 1} (y) v A}$ a ${ displaystyle f (x) v B}$, tak ${ displaystyle f}$ lze upravit nastavením: ${ displaystyle f (f ^ {- 1} (y)): = f (x)}$. Poté omezení upravené funkce na ${ displaystyle A}$ a ${ displaystyle B}$ je proveditelná devizová bijekce.

Úplnost

Třída základních uspořádatelných matroidů je kompletní. To znamená, že je uzavřen v rámci operací nezletilých, duálů, přímých součtů, zkrácení a indukce pomocí řízených grafů.^[1]:2 Je také uzavřen pod omezením, sjednocením a zkrácením.^[5]:410

Totéž platí pro třídu matroidů se silným uspořádáním.

Reference