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

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

Позначення

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

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

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

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

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

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

• (C0) $\mathrm{\varnothing }\notin 𝒞$,
• (C1) $𝒞=-𝒞$,
• (C2) для будь-яких $X,Y\in 𝒞$, якщо $\underset{\_}{X}\subseteq \underset{\_}{Y}$, то $X=Y$ або $X=-Y$,
• (С3) для будь-яких $X,Y\in 𝒞,X\ne -Y$, і $e\in X^{+}\cap Y^{-}$ існує $Z\in 𝒞$ таке, що $Z^{+}\subseteq (X^{+}\cup Y^{+})\mathrm{\setminus }\{e\}$ і $Z^{-}\subseteq (X^{-}\cup Y^{-})\mathrm{\setminus }\{e\}$.

Література

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