Бинарный матроид

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

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

Матроид $M$ является двоичным тогда и только тогда, когда

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

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

Каждый обычный матроид и каждый графический матроид являются двоичными. Бинарный матроид является регулярным тогда и только тогда, когда он не содержит в качестве минора плоскости Фано (семиэлементный нерегулярный бинарный матроид) или ее двойственной плоскости . Бинарный матроид является графическим тогда и только тогда, когда его миноры не включают двойственный графический матроид $K_{5}$ ни из $K_{3,3}$. Если каждая схема бинарного матроида имеет нечетную мощность, то все его схемы должны быть непересекающимися друг с другом; в этом случае его можно представить как графический матроид графа кактуса .

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

Если $M$ является бинарным матроидом, то и его двойник тоже, и таков минор каждый $M$. Кроме того, прямая сумма бинарных матроидов является двоичной.

Харари и Уэлш (1969) определяют двудольный матроид как матроид, в котором каждая схема имеет четную мощность, а эйлеров матроид — как матроид, элементы которого могут быть разделены на непересекающиеся схемы. В классе графических матроидов эти два свойства описывают матроиды двудольных графов и эйлеровых графов (необязательно связных графов, в которых все вершины имеют четную степень) соответственно. Для планарных графов (а, следовательно, и для графических матроидов планарных графов) эти два свойства двойственны: планарный граф или его матроид двудольен тогда и только тогда, когда его двойственный граф является эйлеровым. То же самое справедливо и для бинарных матроидов. Однако существуют небинарные матроиды, для которых эта двойственность нарушается.

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