Обычный матроид

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

Определение

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

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

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

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

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

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

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

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

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

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

Алгоритмы

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

Ссылки

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

[sfo-1] Jump up to: ^а ^б Фудзисигэ, Сатору (2005), Субмодулярные функции и оптимизация , Анналы дискретной математики, Elsevier, стр. 24, ISBN 9780444520869 .

[2] Оксли, Джеймс Г. (2006), Теория матроидов , Тексты для выпускников Оксфорда по математике, том. 3, Издательство Оксфордского университета, с. 209, ISBN 9780199202508 .

[3] Оксли (2006) , с. 112.

[4] Оксли (2006) , с. 131.

[5] Тутте, WT (1965), «Лекции по матроидам» , Журнал исследований Национального бюро стандартов , 69B : 1–47, doi : 10.6028/jres.069b.001 , MR 0179781 .

[6] Сеймур, П.Д. (1980), «Разложение правильных матроидов», Журнал комбинаторной теории , серия B, 28 (3): 305–359, doi : 10.1016/0095-8956(80)90075-1 , hdl : 10338.dmlcz /101946 , МР 0579077 .

[7] Маурер, Стивен Б. (1976), «Матричные обобщения некоторых теорем о деревьях, циклах и коциклах в графах», SIAM Journal on Applied Mathematics , 30 (1): 143–148, doi : 10.1137/0130017 , MR 0392635 .

[t58-8] Jump up to: ^а ^б Тутте, WT (1958), «Гомотопическая теорема для матроидов. I, II», Transactions of the American Mathematical Society , 88 (1): 144–174, doi : 10.2307/1993244 , JSTOR 1993244 , MR 0101526 .

[9] Сеймур, П.Д. (1979), «Матроидное представление над GF(3)», Журнал комбинаторной теории , серия B, 26 (2): 159–173, doi : 10.1016/0095-8956(79)90055-8 , MR 0532586 .

[10] Оксли (2006) , с. 20.

[11] Джерардс, AMH (1989), «Краткое доказательство характеристики Тутте полностью унимодулярных матриц», Линейная алгебра и ее приложения , 114/115: 207–212, doi : 10.1016/0024-3795(89)90461-8 .

[12] Трумпер, К. (1982), «Об эффективности тестов представимости матроидов», European Journal of Combinatorics , 3 (3): 275–291, doi : 10.1016/s0195-6698(82)80039-5 , MR 0679212 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]