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

Regular matroid

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

Определение

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

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

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

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

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

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

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

В униформа матроид (четырехточечная линия) не является регулярной: она не может быть реализована над двухэлементной конечное поле GF (2), так что это не двоичный матроид, хотя это может быть реализовано и во всех остальных областях. Матроид Самолет Фано (матроид ранга три, в котором семь троек точек зависимы) и его двойственный также не являются регулярными: они могут быть реализованы над GF (2) и над всеми полями характеристики два, но не над любыми другими полями, кроме те. В качестве Тутте (1958) Как было показано, эти три примера являются фундаментальными для теории регулярных матроидов: каждый нерегулярный матроид имеет хотя бы один из этих трех в качестве незначительный. Таким образом, обычные матроиды - это именно те матроиды, у которых нет одного из трех запрещенных миноров. , плоскость Фано или ее двойник.[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.