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

Абстракция независимости векторов по модулю 2

В теории матроидов бинарный матроид — это матроид, который может быть представлен над конечным полем GF(2) . ^[1] То есть, с точностью до изоморфизма, это матроиды, элементы которых являются столбцами (0,1)-матрицы и наборы элементов которых независимы тогда и только тогда, когда соответствующие столбцы линейно независимы в GF(2).

Альтернативные характеристики

Матроид является бинарным тогда и только тогда, когда ${\displaystyle M}$

• Это матроид, определенный из симметричной (0,1)-матрицы. ^[2]
• Для каждого набора контуров матроида симметричная разность контуров в может быть представлена ​​как непересекающееся объединение контуров. ^{[3] [4]} ${\displaystyle {\mathcal {S}}}$ ${\displaystyle {\mathcal {S}}}$
• Для каждой пары контуров матроида их симметричная разность содержит другой контур. ^[4]
• Для каждой пары , где есть контур и есть контур двойственного матроида , есть четное число. ^{[4] [5]} ${\displaystyle C,D}$ ${\displaystyle C}$ ${\displaystyle M}$ ${\displaystyle D}$ ${\displaystyle M}$ ${\displaystyle |C\cap D|}$
• Для каждой пары , где есть базис и есть контур , есть симметричная разность фундаментальных контуров, индуцированных в элементами . ^{[4] [5]} ${\displaystyle B,C}$ ${\displaystyle B}$ ${\displaystyle M}$ ${\displaystyle C}$ ${\displaystyle M}$ ${\displaystyle C}$ ${\displaystyle B}$ ${\displaystyle C\setminus B}$
• Ни один матроидный минор не является равномерным матроидом , четырехточечной линией. ^{[6] [7] [8]} ${\displaystyle M}$ ${\displaystyle U{}_{4}^{2}}$
• В геометрической решетке, связанной с матроидом, каждый интервал высоты два имеет не более пяти элементов. ^[8]

Связанные матроиды

Каждый регулярный матроид и каждый графический матроид являются бинарными. ^[5] Двоичный матроид является регулярным тогда и только тогда, когда он не содержит плоскость Фано (семиэлементный нерегулярный бинарный матроид) или ее дуальный матроид в качестве минора . ^[9] Двоичный матроид является графическим тогда и только тогда, когда его миноры не включают дуальный матроид графического матроида ни . ^[10] Если каждый контур бинарного матроида имеет нечетную мощность, то все его контуры должны быть непересекающимися друг с другом; в этом случае он может быть представлен как графический матроид графа кактуса . ^[5] ${\displaystyle K_{5}}$ ${\displaystyle K_{3,3}}$

Дополнительные свойства

Если — бинарный матроид, то таковым является и его двойственный матроид, а также каждый минор из . ^[5] Кроме того, прямая сумма бинарных матроидов является бинарной. ${\displaystyle M}$ ${\displaystyle M}$

Harary & Welsh (1969) определяют двудольный матроид как матроид, в котором каждый контур имеет четную мощность, а эйлеров матроид как матроид, в котором элементы могут быть разделены на непересекающиеся контуры. В классе графических матроидов эти два свойства описывают матроиды двудольных графов и эйлеровых графов (не обязательно связных графов, в которых все вершины имеют четную степень) соответственно. Для планарных графов (и, следовательно, также для графических матроидов планарных графов) эти два свойства являются двойственными: планарный граф или его матроид является двудольным тогда и только тогда, когда его двойственный является эйлеровым. То же самое верно и для бинарных матроидов. Однако существуют небинарные матроиды, для которых эта двойственность нарушается. ^{[5] [11]}

Любой алгоритм, который проверяет, является ли заданный матроид бинарным, при наличии доступа к матроиду через независимый оракул , должен выполнить экспоненциальное число запросов оракула и, следовательно, не может занять полиномиальное время. ^[12]

Ссылки

1. Welsh, DJA (2010) [1976], "10. Двоичные матроиды", Теория матроидов , Courier Dover Publications, стр. 161–182, ISBN 9780486474397.
2. Jaeger, F. (1983), «Симметричные представления бинарных матроидов», Комбинаторная математика (Марсель-Люмини, 1981) , North-Holland Math. Stud., т. 75, Амстердам: North-Holland, стр. 371–376, MR  0841317.
3. Уитни, Хасслер (1935), «Об абстрактных свойствах линейной зависимости», American Journal of Mathematics , 57 (3), Издательство Университета Джонса Хопкинса: 509–533, doi : 10.2307/2371182, hdl : 10338.dmlcz/100694 , JSTOR  2371182, MR  1507091.
4. Welsh (2010), Теорема 10.1.3, стр. 162.
5. Харари, Фрэнк ; Уэлш, Доминик (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.
6. Tutte, WT (1958), «Гомотопическая теорема для матроидов. I, II», Transactions of the American Mathematical Society , 88 (1): 144–174, doi :10.2307/1993244, JSTOR  1993244, MR  0101526.
7. Tutte, WT (1965), «Лекции о матроидах», Журнал исследований Национального бюро стандартов , 69B : 1–47, doi : 10.6028/jres.069b.001 , MR  0179781.
8. Welsh (2010), Раздел 10.2, «Исключенный второстепенный критерий бинарного характера матроида», стр. 167–169.
9. Уэлш (2010), Теорема 10.4.1, стр. 175.
10. Уэлш (2010), Теорема 10.5.1, стр. 176.
11. Welsh, DJA (1969), «Эйлер и двудольные матроиды», Журнал комбинаторной теории , 6 (4): 375–377, doi : 10.1016/s0021-9800(69)80033-5 , MR  0237368/
12. Сеймур, PD (1981), «Распознавание графических матроидов», Combinatorica , 1 (1): 75–78, doi :10.1007/BF02579179, MR  0602418, S2CID  35579707.