Матроид минор

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

Определения

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

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

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

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

Запрещенные характеристики матроидов

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

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

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

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

Ширина ветки

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

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

Ширина ветвей является важным компонентом попыток распространить теорию миноров графа на матроиды: хотя ширину дерева также можно обобщить на матроиды, и играет большую роль, чем ширина ветвления в теории миноров графа, ширина ветвления имеет более удобные свойства в условиях матроида. Если минорно-замкнутое семейство матроидов, представимое в конечном поле, не включает графические матроиды всех планарных графов, то существует постоянная граница ширины ветвей матроидов в семействе, обобщающая аналогичные результаты для минорно-замкнутых семейств графов.

Ну-квази-упорядочение

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

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

Матроидные разложения

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

Алгоритмы и сложность

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

Ссылки

• Гилен, Дж. Ф. ; Джерардс, AMH; Капур, А. (2000), «Исключенные миноры для GF(4)-представимых матроидов» , Журнал комбинаторной теории , серия B, 79 (2): 247–299, doi : 10.1006/jctb.2000.1963 , MR   1769191 .
• Гилен, Джим ; Джерардс, Берт; Робертсон, Нил ; Уиттл, Джефф (2003), «Об исключенных минорах для матроидов с шириной ветвей k », Журнал комбинаторной теории , серия B, 88 (2): 261–265, doi : 10.1016/S0095-8956(02)00046 -1 .
• Гилен, Джим ; Джерардс, Берт; Уиттл, Джефф (2002), «Ширина ветвей и хороший квазиупорядочение в матроидах и графах» , Журнал комбинаторной теории , серия B, 84 (2): 270–290, doi : 10.1006/jctb.2001.2082 .
• Гилен, Джим ; Джерардс, Берт; Уиттл, Джефф (2006), «К теории структуры матриц и матроидов» (PDF) , Proc. Международный конгресс математиков , вып. III, стр. 827–842 .
• Гилен, Джим ; Джерардс, Берт; Уиттл, Джефф (2007), «Исключение плоского графа из GF( q )-представимых матроидов» (PDF) , Journal of Combinatorial Theory , Series B, 97 (6): 971–998, doi : 10.1016/j.jctb. 2007.02.005 , заархивировано из оригинала (PDF) 24 сентября 2010 г.
• Гилен, Джим ; Джерардс, Берт; Уиттл, Джефф (17 августа 2014 г.), «Решение гипотезы Роты» (PDF) , Уведомления Американского математического общества , 61 (7): 736–743, doi : 10.1090/noti1139
• Хикс, Илья В.; МакМюррей, Нолан Б. младший (2007), «Ширина ветвей графов и их матроиды циклов», Журнал комбинаторной теории , серия B, 97 (5): 681–692, doi : 10.1016/j.jctb.2006.12.007 .
• Хлинены, Петр (2003), «О свойствах матроида, определяемых в логике MSO», Proc. 28-й Международный симпозиум по математическим основам информатики (MFCS '03) , Конспекты лекций по информатике, том. 2747, Springer-Verlag, стр. 470–479, номер документа : 10.1007/978-3-540-45138-9_41.
• Хлиненый, Петр; Уиттл, Джефф (2006), «Ширина дерева матроидов» (PDF) , European Journal of Combinatorics , 27 (7): 1117–1128, doi : 10.1016/j.ejc.2006.06.005 , заархивировано из оригинала (PDF) 6 марта 2012 г. , получено 17 августа 2012 г. Дополнение и исправление: Хлиненый, Петр; Уиттл, Джефф (2009), «Дополнение к ширине дерева матроидов», European Journal of Combinatorics , 30 (4): 1036–1044, doi : 10.1016/j.ejc.2008.09.028 .
• Мазуа, Фредерик; Томассе, Стефан (2007), «Ширина графических матроидов», в Хилтоне, Энтони; Талбот, Джон (ред.), Обзоры по комбинаторике, 2007 г. (PDF) , Серия лекций Лондонского математического общества, том. 346, Издательство Кембриджского университета, с. 275 .
• Рота, Джан-Карло (1971), «Комбинаторная теория, старая и новая», Труды Международного конгресса математиков (Ницца, 1970), Том 3 , Париж: Готье-Виллар, стр. 229–233, МР   0505646 .
• Сеймур, П.Д. (1980), «Разложение правильных матроидов», Журнал комбинаторной теории , серия B, 28 (3): 305–359, doi : 10.1016/0095-8956(80)90075-1 , MR   0579077 .
• Сеймур, Полиция ; Уолтон, ПН (1981), «Обнаружение несовершеннолетних матроидов», Журнал Лондонского математического общества , вторая серия, 23 (2): 193–203, CiteSeerX   10.1.1.108.1426 , doi : 10.1112/jlms/s2-23.2.193 , МР   0609098 .
• Тутте, WT (1958), «Гомотопическая теорема для матроидов. I, II», Transactions of the American Mathematical Society , 88 (1): 144–174, doi : 10.2307/1993244 , JSTOR   1993244 , MR   0101526 .
• Вамос, П. (1978), «Недостающая аксиома теории матроидов утеряна навсегда», Журнал Лондонского математического общества , вторая серия, 18 (3): 403–408, doi : 10.1112/jlms/s2-18.3.403 , МР   0518224 .
• Уэлш, DJA (2010) [1976], «4.4 Несовершеннолетние и их представление в решетке», Теория Матроидов , Courier Dover Publications, стр. 65–67, ISBN  9780486474397 .