Малый матроид

В математической теории матроидов минор матроида M — это другой матроид N , который получается из M последовательностью операций ограничения и сжатия. Миноры матроида тесно связаны с минорами графа , а операции ограничения и сжатия, с помощью которых они образуются, соответствуют операциям удаления ребер и сжатия ребер в графах. Теория миноров матроида приводит к структурным разложениям матроидов и характеристикам семейств матроидов запрещенными минорами, аналогичным соответствующей теории в графах.

Если M — матроид на множестве E , а S — подмножество E , то ограничение M на S , записанное как M  | S , — это матроид на множестве S , независимые множества которого являются независимыми множествами M , содержащимися в S. Его контуры являются контурами M , содержащимися в S , а его ранговая функция — это функция M, ограниченная подмножествами S.

Если T является независимым подмножеством E , то свертка M по T , обозначаемая как M / T , является матроидом на базовом множестве E − T, чьи независимые множества являются множествами, объединение которых с T является независимым в M. Это определение можно распространить на произвольный T , выбрав базис для T и определив множество как независимое в свертке, если его объединение с этим базисом остается независимым в M. Ранговая функция свертывания равна${\displaystyle r'(A)=r(A\cup T)-r(T).}$

Матроид N является минором матроида M , если он может быть построен из M с помощью операций ограничения и сжатия.

С точки зрения геометрической решетки, образованной плоскостями матроида, взятие минора матроида соответствует взятию интервала решетки, части решетки, лежащей между заданным нижним граничным элементом и верхним граничным элементом. ^[1]

Многие важные семейства матроидов замкнуты относительно операции взятия миноров: если матроид M принадлежит семейству, то каждый минор M также принадлежит семейству. В этом случае семейство может быть охарактеризовано его множеством «запрещенных матроидов», минорно-минимальных матроидов, которые не принадлежат семейству. Матроид принадлежит семейству тогда и только тогда, когда он не имеет запрещенного матроида в качестве минора. Часто, но не всегда, множество запрещенных матроидов конечно, что соответствует теореме Робертсона–Сеймура , которая утверждает, что множество запрещенных миноров минорно-замкнутого семейства графов всегда конечно.

Примером этого явления являются регулярные матроиды , матроиды, которые представимы над всеми полями. Эквивалентно матроид является регулярным, если он может быть представлен полностью унимодулярной матрицей (матрицей, все квадратные подматрицы которой имеют определители, равные 0, 1 или −1). Тутт (1958) доказал, что матроид является регулярным тогда и только тогда, когда он не имеет одного из трех запрещенных миноров: равномерного матроида (четырехточечной прямой), плоскости Фано или двойственного матроида плоскости Фано. Для этого он использовал свою сложную теорему о гомотопии . С тех пор были найдены более простые доказательства.${\displaystyle U{}_{4}^{2}}$

Графические матроиды , матроиды, независимые множества которых являются лесными подграфами графа, имеют пять запрещённых миноров: три для регулярных матроидов и два двойственных к графическим матроидам для графов K ₅ и K _3,3 , которые по теореме Вагнера являются запрещёнными минорами для планарных графов .

Бинарные матроиды , матроиды, представимые над конечным полем из двух элементов , включают как графические, так и регулярные матроиды. Тутт снова показал, что эти матроиды имеют запрещённую минорную характеристику: это матроиды, которые не имеют четырёхточечной прямой в качестве минора. Рота предположил , что для любого конечного поля матроиды, представимые над этим полем, имеют конечное число запрещённых миноров. ^[2] Доказательство этой гипотезы было объявлено, но не опубликовано, Джиленом, Джерардсом и Уиттлом в 2014 году. ^[3] Матроиды, которые могут быть представлены над действительными числами, имеют бесконечно много запрещённых миноров. ^[4]

Ветвевые разложения матроидов могут быть определены аналогично их определению для графов. Ветвевая разложение матроида — это иерархическая кластеризация элементов матроида, представленная в виде некорневого бинарного дерева с элементами матроида в его листьях. Удаление любого ребра этого дерева разбивает матроиды на два непересекающихся подмножества; такое разбиение называется e-разделением. Если r обозначает ранговую функцию матроида, то ширина e-разделения определяется как r ( A ) + r ( B ) − r ( M ) + 1 . Ширина разложения — это максимальная ширина любого из его e-разделений, а ширина ветви матроида — это минимальная ширина любого из его ветвевых разложений.

Ширина ветвления графа и ширина ветвления соответствующего графического матроида могут различаться: например, граф трехреберного пути и звезда с тремя ребрами имеют разную ширину ветвления, 2 и 1 соответственно, но они оба индуцируют один и тот же графический матроид с шириной ветвления 1. ^[5] Однако для графов, которые не являются деревьями, ширина ветвления графа равна ширине ветвления его связанного графического матроида. ^[6] Ширина ветвления матроида всегда равна ширине ветвления его дуального. ^[5]

Branchwidth является важным компонентом попыток расширить теорию графовых миноров на матроиды: хотя treewidth также может быть обобщена на матроиды, ^[7] и играет большую роль, чем branchwidth в теории графовых миноров, branchwidth имеет более удобные свойства в условиях матроидов. ^[8] Если семейство матроидов, замкнутое по минорам, представимое над конечным полем, не включает графические матроиды всех планарных графов, то существует постоянная граница для branchwidth матроидов в семействе, обобщающая аналогичные результаты для семейств графов, замкнутых по минорам. ^[9]

Теорема Робертсона–Сеймура подразумевает, что каждое свойство матроида графических матроидов, характеризуемое списком запрещенных миноров, может быть характеризовано конечным списком. Другой способ сказать то же самое состоит в том, что частичный порядок на графических матроидах, образованный операцией минора, является вполне квазиупорядоченным . Однако пример действительно представимых матроидов, которые имеют бесконечно много запрещенных миноров, показывает, что минорное упорядочение не является вполне квазиупорядоченным на всех матроидах.

Робертсон и Сеймур предположили, что матроиды, представимые над любым конкретным конечным полем, являются хорошо квазиупорядоченными. Пока это доказано только для матроидов ограниченной ширины ветвления. ^[10]

Теорема о структуре графа является важным инструментом в теории миноров графа, согласно которой графы в любом замкнутом по минорам семействе могут быть построены из более простых графов с помощью операций кликовой суммы . Некоторые аналогичные результаты известны также в теории матроидов. В частности, теорема Сеймура о разложении утверждает, что все регулярные матроиды могут быть построены простым способом как кликовая сумма графических матроидов, их дуальных и одного специального 10-элементного матроида. ^[11] Как следствие, линейные программы, определяемые полностью унимодулярными матрицами, могут быть решены комбинаторно путем объединения решений набора задач минимального остовного дерева, соответствующих графической и кографической частям этого разложения.

Одним из важных компонентов теории миноров графов является существование алгоритма для проверки того, является ли граф H минором другого графа G , требующего времени, полиномиального по G для любого фиксированного выбора H (и более строго фиксированного параметра, если размер H может изменяться). Объединив этот результат с теоремой Робертсона–Сеймура, можно распознать членов любого семейства графов с замкнутыми минорами за полиномиальное время . Соответственно, в теории матроидов было бы желательно разработать эффективные алгоритмы для распознавания того, является ли заданный фиксированный матроид минором входного матроида. К сожалению, такой сильный результат невозможен: в модели оракула матроида единственными минорами, которые могут быть распознаны за полиномиальное время, являются однородные матроиды с рангом или корангом один. ^[12] Однако, если задача ограничена матроидами, которые представимы над некоторым фиксированным конечным полем (и представлены в виде матрицы над этим полем), то, как и в случае с графом, предполагается, что можно распознать матроиды, содержащие любой фиксированный минор, за полиномиальное время. ^[8]