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

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

Определение

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

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

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

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

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

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

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

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

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

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

Алгоритмы

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

Рекомендации

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