Орієнтований матроїд

Орієнтований матроїд — математична структура, яка узагальнює властивості орієнтованих графів, розташувань векторів у впорядкованому полі, а також розташувань гіперплощин у впорядкованому полі, за аналогією з тим, як звичайний матроїд узагальнює властивості звичайних графів, розташувань векторів або гіперплощин у звичайному полі.

Позначення

Орієнтована множина ${\displaystyle X}$ — множина ${\displaystyle {\underline {X}}}$ із розбиттям її елементів на дві підмножини: підмножина «додатних елементів» ${\displaystyle X^{+}}$і підмножина «від'ємних» — ${\displaystyle X^{-}}$.

Множину ${\displaystyle {\underline {X}}=X^{+}\cup X^{-}}$називають опорою орієнтованої множини ${\displaystyle X}$.

Порожня орієнтована множина ${\displaystyle \emptyset }$ — орієнтована множина з опорою ${\displaystyle {\underline {\emptyset }}}$ (відповідно, з порожньою множиною «додатних» елементів і порожньою множиною «від'ємних»).

Орієнтована множина ${\displaystyle Y}$ є протилежною орієнтованій множині ${\displaystyle X}$, якщо ${\displaystyle Y^{+}=X^{-}}$і ${\displaystyle Y^{-}=X^{+}}$.

Визначення в термінах циклів

Множина ${\displaystyle {\mathcal {C}}}$ орієнтованих підмножин множини ${\displaystyle E}$ буде набором циклів орієнтованого матроїда, якщо виконуються такі аксіоми:

• (C0) ${\displaystyle \emptyset \notin {\mathcal {C}}}$,
• (C1) ${\displaystyle {\mathcal {C}}=-{\mathcal {C}}}$,
• (C2) для будь-яких ${\displaystyle X,Y\in {\mathcal {C}}}$, якщо ${\displaystyle {\underline {X}}\subseteq {\underline {Y}}}$, то ${\displaystyle X=Y}$ або ${\displaystyle X=-Y}$,
• (С3) для будь-яких ${\displaystyle X,Y\in {\mathcal {C}},X\neq -Y}$, і ${\displaystyle e\in X^{+}\cap Y^{-}}$ існує ${\displaystyle Z\in {\mathcal {C}}}$ таке, що ${\displaystyle Z^{+}\subseteq (X^{+}\cup Y^{+})\backslash \{e\}}$ і ${\displaystyle Z^{-}\subseteq (X^{-}\cup Y^{-})\backslash \{e\}}$.

Література

Björner, A., Las Vergnas, M., Sturmfels, B., White, N., & Ziegler, G. M. (1999). Oriented matroids (No. 46). Cambridge University Press