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

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

Позначення

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

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

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

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

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

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

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