Регулярный матроид

Матроид, который может быть представлен по всем полям

В математике регулярный матроид — это матроид , который можно представить над всеми полями .

Определение

Матроид определяется как семейство подмножеств конечного множества, удовлетворяющее определенным аксиомам. Множества в семействе называются «независимыми множествами». Один из способов построения матроида — выбрать конечное множество векторов в векторном пространстве и определить подмножество векторов как независимое в матроиде, когда оно линейно независимо в векторном пространстве. Каждое семейство множеств, построенное таким образом, является матроидом, но не каждый матроид может быть построен таким образом, и векторные пространства над различными полями приводят к различным множествам матроидов, которые могут быть построены из них.

Матроид является регулярным, когда для каждого поля , может быть представлен системой векторов над . ^{[1] [2]} ${\displaystyle M}$ ${\displaystyle F}$ ${\displaystyle M}$ ${\displaystyle F}$

Характеристики

Если матроид является регулярным, то его двойственный матроид также является регулярным , ^[1] и каждый из его миноров также является регулярным . ^[3] Каждая прямая сумма регулярных матроидов остается регулярной. ^[4]

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

Число баз в регулярном матроиде может быть вычислено как определитель связанной матрицы, обобщая теорему Кирхгофа о матричном дереве для графических матроидов . ^[7]

Характеристика

Равномерный матроид (четырехточечная линия) не является регулярным: он не может быть реализован над конечным полем GF(2) из ​​двух элементов , поэтому он не является бинарным матроидом , хотя он может быть реализован над всеми другими полями. Матроид плоскости Фано (матроид ранга три, в котором семь троек точек являются зависимыми) и его двойственный также не являются регулярными: они могут быть реализованы над GF(2) и над всеми полями характеристики два, но не над любыми другими полями, кроме этих. Как показал Тутт (1958), эти три примера являются основополагающими для теории регулярных матроидов: каждый нерегулярный матроид имеет по крайней мере один из этих трех в качестве минора . Таким образом, регулярные матроиды — это в точности те матроиды, которые не имеют одного из трех запрещенных миноров , плоскости Фано или ее двойственного. ^[8] ${\displaystyle U{}_{4}^{2}}$ ${\displaystyle U{}_{4}^{2}}$

Если матроид регулярен, он должен быть, очевидно, реализуем над двумя полями GF(2) и GF(3). Обратное верно: каждый матроид, реализуемый над обоими этими полями, является регулярным. Результат следует из запрещенной второстепенной характеризации матроидов, реализуемых над этими полями, части семейства результатов, кодифицированных гипотезой Роты . ^[9]

Регулярные матроиды — это матроиды, которые можно определить из полностью унимодулярной матрицы , матрицы, в которой каждая квадратная подматрица имеет определитель 0, 1 или −1. Векторы, реализующие матроид, можно взять в качестве строк матрицы. По этой причине регулярные матроиды иногда также называют унимодулярными матроидами . ^[10] Эквивалентность регулярных матроидов и унимодулярных матриц, а также их характеристика запрещенными минорами являются глубокими результатами В. Т. Тутта , первоначально доказанными им с помощью теоремы Тутта о гомотопии . ^[8] Позднее Джерардс (1989) опубликовал альтернативное и более простое доказательство характеризации унимодулярных матриц запрещенными минорами. ^[11]

Алгоритмы

Существует полиномиальный алгоритм для проверки регулярности матроида, при условии доступа к матроиду через оракул независимости . ^[12]

Ссылки

1. Fujishige, Satoru (2005), Субмодулярные функции и оптимизация , Annals of Discrete Mathematics, Elsevier, стр. 24, ISBN 9780444520869.
2. Оксли, Джеймс Г. (2006), Теория матроидов , Oxford Graduate Texts in Mathematics, т. 3, Oxford University Press, стр. 209, ISBN 9780199202508.
3. Оксли (2006), стр. 112.
4. Оксли (2006), стр. 131.
5. Tutte, WT (1965), «Лекции о матроидах», Журнал исследований Национального бюро стандартов , 69B : 1–47, doi : 10.6028/jres.069b.001 , MR  0179781.
6. Сеймур, PD (1980), «Разложение регулярных матроидов», Журнал комбинаторной теории , Серия B, 28 (3): 305–359, doi : 10.1016/0095-8956(80)90075-1, hdl : 10338.dmlcz/101946 , MR  0579077.
7. Маурер, Стивен Б. (1976), «Матричные обобщения некоторых теорем о деревьях, циклах и коциклах в графах», SIAM Journal on Applied Mathematics , 30 (1): 143–148, doi :10.1137/0130017, MR  0392635.
8. Tutte, WT (1958), "Теорема гомотопии для матроидов. I, II", Transactions of the American Mathematical Society , 88 (1): 144–174, doi :10.2307/1993244, JSTOR  1993244, MR  0101526.
9. Сеймур, PD (1979), «Представление матроида над GF(3)», Журнал комбинаторной теории , Серия B, 26 (2): 159–173, doi : 10.1016/0095-8956(79)90055-8 , MR  0532586.
10. Оксли (2006), стр. 20.
11. Gerards, AMH (1989), «Краткое доказательство характеристики Татта полностью унимодулярных матриц», Линейная алгебра и ее приложения , 114/115: 207–212, doi : 10.1016/0024-3795(89)90461-8.
12. Truemper, K. (1982), «Об эффективности тестов представимости для матроидов», European Journal of Combinatorics , 3 (3): 275–291, doi : 10.1016/s0195-6698(82)80039-5 , MR  0679212.