Двойной матроид

Матроид с дополненными базисными наборами

В теории матроидов двойственным к матроиду является другой матроид , имеющий те же элементы, что и , и в котором множество является независимым тогда и только тогда, когда имеет базисное множество, не пересекающееся с ним. ^{[1] [2] [3]} ${\displaystyle M}$ ${\displaystyle M^{\ast }}$ ${\displaystyle M}$ ${\displaystyle M}$

Двойственные матроиды восходят к оригинальной статье Хасслера Уитни , определяющей матроиды. ^[4] Они обобщают на матроиды понятия двойственности плоских графов .

Основные свойства

Двойственность — это инволюция : для всех , . ^{[1] [3] [4]} ${\displaystyle M}$ ${\displaystyle (M^{\ast })^{\ast }=M}$

Альтернативное определение дуального матроида заключается в том, что его базисные наборы являются дополнениями базисных наборов . Аксиома обмена базисами, используемая для определения матроидов из их базисов, является самодополнительной, поэтому дуал матроида обязательно является матроидом. ^[3] ${\displaystyle M}$

Квартиры являются дополнительными к циклическим множествам ( объединениям контуров) и наоборот. ^[3] ${\displaystyle M}$ ${\displaystyle M^{\ast }}$

Если — ранговая функция матроида на базовом множестве , то ранговая функция двойственного матроида равна . ^{[1] [3] [4]} ${\displaystyle r}$ ${\displaystyle M}$ ${\displaystyle E}$ ${\displaystyle r^{\ast }(S)=r(E\setminus S)+|S|-r(E)}$

Несовершеннолетние

Минор матроида формируется из большего матроида двумя операциями: ограничение удаляет элемент из без изменения независимости или ранга оставшихся множеств, а сокращение удаляет из после вычитания единицы из ранга каждого множества, к которому он принадлежит. Эти две операции являются двойственными: и . Таким образом, минор двойственного — это то же самое, что и двойственный минор. ^[5] ${\displaystyle M}$ ${\displaystyle M\setminus x}$ ${\displaystyle x}$ ${\displaystyle M}$ ${\displaystyle M/x}$ ${\displaystyle x}$ ${\displaystyle M}$ ${\displaystyle M\setminus x=(M^{\ast }/x)^{\ast }}$ ${\displaystyle M/x=(M^{\ast }\setminus x)^{\ast }}$

Самодвойственные матроиды

Отдельный матроид является самодвойственным (обобщая, например, самодвойственные многогранники для графических матроидов), если он изоморфен своему собственному двойственному. Изоморфизм может, но не обязан, оставлять элементы матроида фиксированными. Любой алгоритм, который проверяет, является ли данный матроид самодвойственным, имея доступ к матроиду через независимый оракул , должен выполнять экспоненциальное число запросов оракула и, следовательно, не может занимать полиномиальное время. ^[6]

Матроидные семьи

Многие важные семейства матроидов являются самодвойственными, что означает, что матроид принадлежит семейству тогда и только тогда, когда его дуал принадлежит. Многие другие семейства матроидов поступают в дуальных парах. Примеры этого явления включают:

• Бинарные матроиды (матроиды, представимые над GF(2) ), матроиды, представимые над любым другим полем, и регулярные матроиды — все это самодвойственные семейства. ^[7]
• Гаммоиды образуют самодвойственное семейство. Строгие гаммоиды дуальны трансверсальным матроидам . ^[8]
• Равномерные матроиды и матроиды разделов являются самодвойственными. Двойственным к равномерному матроиду является равномерный матроид . ^[9] ${\displaystyle U{}_{n}^{r}}$ ${\displaystyle U{}_{n}^{n-r}}$
• Двойственный графическому матроиду матроид сам является графическим тогда и только тогда, когда базовый граф является планарным; матроид двойственного планарного графа совпадает с двойственным матроиду матроида графа. Таким образом, семейство графических матроидов планарных графов является самодвойственным. ^[10]
• Среди графических матроидов и, в более общем смысле, среди бинарных матроидов, двудольные матроиды (матроиды, в которых каждый контур четный) являются дуальными эйлеровым матроидам (матроидам, которые можно разбить на непересекающиеся контуры). ^{[11] [12]}

Открытой проблемой является то, является ли семейство алгебраических матроидов самодвойственным.

Если V — векторное пространство , а V * — его ортогональное дополнение , то линейный матроид V и линейный матроид V * являются дуальными. Как следствие, дуальный матроид любого линейного матроида является линейным матроидом. ^[13]

Ссылки

1. Schrijver, Alexander (2003), Комбинаторная оптимизация: многогранники и эффективность. Том B: Матроиды, деревья, стабильные множества, алгоритмы и комбинаторика, том 24, Берлин: Springer-Verlag, стр. 652, ISBN 3-540-44389-4, г-н  1956925.
2. Валлийский, DJA (2010), Теория Матроидов, Courier Dover Publications, стр. 34, ISBN 9780486474397.
3. Оксли, Джеймс Г. (2006), Теория матроидов, Oxford Graduate Texts in Mathematics, т. 3, Oxford University Press, стр. 69–70, ISBN 9780199202508.
4. Уитни, Хасслер (1935), «Об абстрактных свойствах линейной зависимости», American Journal of Mathematics , 57 (3), Издательство Университета Джонса Хопкинса: 509–533, doi : 10.2307/2371182, hdl : 10338.dmlcz/100694 , JSTOR  2371182, MR  1507091. Перепечатано в Kung (1986), стр. 55–79. См. в частности раздел 11, «Двойственные матроиды», стр. 521–524.
5. Схрайвер (2003), стр. 653.
6. Йенсен, Пер М.; Корте, Бернхард (1982), «Сложность алгоритмов свойств матроидов», SIAM Journal on Computing , 11 (1): 184–190, doi :10.1137/0211014, MR  0646772.
7. Уитни (1935), Раздел 13, «Ортогональные гиперплоскости и двойственные матроиды».
8. Шрийвер (2003), стр. 659–661; Валлийский (2010), стр. 222–223.
9. Оксли (2006), стр. 77 и 111.
10. Tutte, WT (1965), «Лекции о матроидах», Журнал исследований Национального бюро стандартов , 69B : 1–47, doi : 10.6028/jres.069b.001 , MR  0179781.
11. Welsh, DJA (1969), «Эйлер и двудольные матроиды», Журнал комбинаторной теории , 6 (4): 375–377, doi : 10.1016/s0021-9800(69)80033-5 , MR  0237368.
12. Харари, Фрэнк ; Уэлш, Доминик (1969), «Матроиды против графов», The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) , Lecture Notes in Mathematics, т. 110, Берлин: Springer, стр. 155–170, doi :10.1007/BFb0060114, ISBN 978-3-540-04629-5, МР  0263666.
13. Федерико, Ардила (2012). «Матроиды. Лекция 9». Ютуб .

Цитируемые работы

• Кунг, Джозеф PSv, ред. (1986), Справочник по теории матроидов, Бостон: Birkhäuser, doi : 10.1007/978-1-4684-9199-9, ISBN 978-0-8176-3173-4, МР  0890330.