Представление матроида
В математической теории матроидов — представление матроида это семейство векторов которых , линейное отношение независимости такое же, как и у данного матроида. Представления матроидов аналогичны представлениям групп ; оба типа представления предоставляют абстрактные алгебраические структуры (матроиды и группы соответственно) с конкретным описанием в терминах линейной алгебры .
Линейный матроид — это матроид, имеющий представление, а F - линейный матроид (для поля F — это матроид, имеющий представление с использованием векторного пространства над F. ) Теория представлений матроидов изучает существование представлений и свойства линейных матроидов.
Определения
[ редактировать ](Конечный) матроид определяется конечным множеством (элементы матроида) и непустое семейство из подмножеств , называемые независимыми множествами матроида. Требуется удовлетворить свойства, согласно которым каждое подмножество независимого множества само по себе является независимым и что если одно независимое множество больше, чем второй независимый набор тогда существует элемент что можно добавить в чтобы сформировать более крупный независимый набор. Одним из ключевых мотивирующих примеров при формулировке матроидов было понятие линейной независимости векторов в векторном пространстве : если представляет собой конечное множество или мультимножество векторов, а — семейство линейно независимых подмножеств , затем это матроид. [1] [2]
В более общем смысле, если — любой матроид, то представление может быть определена как функция это отображает в векторное пространство , обладающий тем свойством, что подмножество из независим тогда и только тогда, когда является инъективным и линейно независима. Матроид с представлением называется линейным матроидом, и если является векторным пространством над полем F , то матроид называется F -линейным матроидом. Таким образом, линейные матроиды — это в точности матроиды, изоморфные матроидам, определенным из множеств или мультимножеств векторов. Функция будет взаимно однозначным тогда и только тогда, когда базовый матроид прост (не имеет двухэлементных зависимых множеств). Представления матроида также могут быть описаны более конкретно с использованием матриц над полем F , с одним столбцом на элемент матроида и с набором элементов, независимых в матроиде тогда и только тогда, когда соответствующий набор столбцов матрицы линейно независим. Функция ранга линейного матроида задается матричным рангом подматриц этой матрицы или, что то же самое, размерностью линейной оболочки подмножеств векторов. [3]
Характеристика линейных матроидов
[ редактировать ]Не каждый матроид линеен; восьмиэлементный матроид Вамоса — один из самых маленьких матроидов, который непредставим во всех полях. [4] Если матроид линеен, его можно представить в некоторых, но не во всех полях.Например, девятиэлементный матроид третьего ранга, определенный конфигурацией Перля, представим в действительных числах , но не в рациональных числах .
Бинарные матроиды — это матроиды, которые могут быть представлены в конечном поле GF(2) ; это именно те матроиды, у которых нет единого матроида как несовершеннолетний . [5] Унимодулярные или регулярные матроиды — это матроиды, которые могут быть представлены во всех полях; [6] их можно охарактеризовать как матроидов, у которых нет ни одного , плоскость Фано (двоичный матроид с семью элементами) или двойственный матроид плоскости Фано как миноры. [5] [7] Альтернативно, матроид является регулярным тогда и только тогда, когда его можно представить полностью унимодулярной матрицей . [8]
Гипотеза Роты утверждает, что для каждого конечного поля F F -линейные матроиды могут характеризоваться конечным набором запрещенных миноров, аналогично описанным выше характеристикам для бинарных и регулярных матроидов. [9] По состоянию на 2012 год это было доказано только для полей из четырех и менее элементов. [5] [10] [11] [12] Для бесконечных полей (таких как поле действительных чисел ) такая характеристика невозможна. [13]
Область определения
[ редактировать ]Для каждого поля алгебраических чисел и каждого конечного поля F существует матроид M, для которого F является минимальным подполем его алгебраического замыкания, над которым M может быть представлено : M можно взять рангом 3. [14]
Набор характеристик
[ редактировать ]Характеристический набор линейного матроида определяется как набор характеристик полей, над которыми он линеен. [15] Для каждого простого числа p существует бесконечно много матроидов, характеристическим набором которых является одноэлементное множество { p }, [16] и для каждого конечного набора простых чисел существует матроид, характеристическое множество которого является заданным конечным множеством. [17]
Если характеристическое множество матроида бесконечно, оно содержит ноль; а если оно содержит ноль, то оно содержит все простые числа, кроме конечного числа. [18] Следовательно, единственными возможными характеристическими множествами являются конечные множества, не содержащие нуля, и коконитные множества, содержащие ноль. [19] Действительно, все такие множества встречаются. [20]
Родственные классы матроидов
[ редактировать ]матроида Униформа имеет элементов, а его независимые множества состоят из всех подмножеств размером до элементов. Однородные матроиды могут быть представлены наборами векторов общего положения в -мерное векторное пространство. Поле репрезентации должно быть достаточно большим, чтобы существовало векторы общего положения в этом векторном пространстве, поэтому равномерные матроиды F кроме конечного числа -линейны для всех полей F, . [21] То же самое верно и для матроидов разбиения , прямых сумм однородных матроидов, поскольку прямая сумма любых двух F -линейных матроидов сама по себе является F -линейной.
Графический матроид — это матроид, определенный из ребер неориентированного графа путем определения набора ребер, которые будут независимыми тогда и только тогда, когда он не содержит цикла . Каждый графический матроид является регулярным и, следовательно, - линейным для любого поля F. F [8]
Матроиды жесткости описывают степени свободы механических связей, образованных жесткими стержнями, соединенными на концах гибкими шарнирами. Связь этого типа можно описать как граф с ребром для каждого стержня и вершиной для каждого шарнира, а для одномерных связей матроиды жесткости являются в точности графическими матроидами. Матроиды жесткости более высокой размерности могут быть определены с использованием матриц действительных чисел со структурой, аналогичной структуре матрицы инцидентности основного графа, и, следовательно, являются -линейный. [22] [23]
Подобно однородным матроидам и матроидам разбиения, гаммоиды , матроиды, представляющие достижимость в ориентированных графах , линейны в каждом достаточно большом поле. Точнее, гаммоид с элементы могут быть представлены в каждом поле, имеющем хотя бы элементы. [24]
Алгебраические матроиды — это матроиды, определенные из наборов элементов расширения поля с использованием понятия алгебраической независимости . Каждый линейный матроид является алгебраическим, и для полей нулевой характеристики (например, действительных чисел) линейные и алгебраические матроиды совпадают, но для других полей могут существовать алгебраические матроиды, которые не являются линейными. [25]
Ссылки
[ редактировать ]- ^ Оксли, Джеймс Г. (2006), Теория матроидов , Тексты для выпускников Оксфорда по математике, том. 3, Издательство Оксфордского университета, с. 8, ISBN 9780199202508 . О ранговой функции см. с. 26.
- ^ Уэлш, DJA (2010), Теория Матроидов , Courier Dover Publications, стр. 10, ISBN 9780486474397 .
- ^ Оксли (2006) , с. 12.
- ^ Оксли (2006) , стр. 170–172, 196.
- ^ Jump up to: а б с Тутте, В.Т. (1958), «Гомотопическая теорема для матроидов. I, II», Труды Американского математического общества , 88 : 144–174, doi : 10.2307/1993244 , MR 0101526 .
- ^ Белый (1987) стр.2
- ^ Белый (1987) стр.12
- ^ Jump up to: а б Тутте, WT (1965), «Лекции по матроидам» , Журнал исследований Национального бюро стандартов , 69B : 1–47, doi : 10.6028/jres.069b.001 , MR 0179781 .
- ^ Рота, Джан-Карло (1971), «Комбинаторная теория, старая и новая», Труды Международного конгресса математиков (Ницца, 1970), Том 3 , Париж: Готье-Виллар, стр. 229–233, МР 0505646 .
- ^ Биксби, Роберт Э. (1979), «О характеристике Ридом троичных матроидов», Журнал комбинаторной теории , серия B, 26 (2): 174–204, doi : 10.1016/0095-8956(79)90056-X , МР 0532587 .
- ^ Сеймур, П.Д. (1979), «Матроидное представление над GF(3)», Журнал комбинаторной теории , серия B, 26 (2): 159–173, doi : 10.1016/0095-8956(79)90055-8 , MR 0532586 .
- ^ Гилен, Дж. Ф. ; Джерардс, AMH; Капур, А. (2000), «Исключенные миноры для GF(4)-представимых матроидов» (PDF) , Journal of Combinatorial Theory , Series B, 79 (2): 247–299, doi : 10.1006/jctb.2000.1963 , MR 1769191 , заархивировано из оригинала (PDF) 24 сентября 2010 г.
- ^ Вамос, П. (1978), «Недостающая аксиома теории матроидов утеряна навсегда», Журнал Лондонского математического общества , вторая серия, 18 (3): 403–408, doi : 10.1112/jlms/s2-18.3.403 , МР 0518224 .
- ^ Уайт, Нил, изд. (1987), Комбинаторная геометрия , Энциклопедия математики и ее приложений, том. 29, Кембридж: Издательство Кембриджского университета , с. 18 , ISBN 0-521-33339-3 , Збл 0626.00007
- ^ Инглтон, AW (1971), «Представление матроидов», на валлийском языке, DJA (ред.), Комбинаторная математика и ее приложения. Слушания, Оксфорд, 1969 , Academic Press, стр. 149–167, ISBN. 0-12-743350-3 , Збл 0222.05025
- ^ Оксли, Джеймс; Семпл, Чарльз; Вертиган, Дирк; Уиттл, Джефф (2002), «Бесконечные антицепи матроидов с набором характеристик { p }», Discrete Mathematics , 242 (1–3): 175–185, doi : 10.1016/S0012-365X(00)00466-0 , hdl : 10092/13245 , МР 1874763 .
- ^ Кан, Джефф (1982), «Характеристические наборы матроидов», Журнал Лондонского математического общества , Вторая серия, 26 (2): 207–217, doi : 10.1112/jlms/s2-26.2.207 , MR 0675165 , Zbl 0468.05020 .
- ^ Оксли (2006) , с. 225.
- ^ Оксли (2006) , с. 226.
- ^ Оксли (2006) , с. 228.
- ^ Оксли (2006) , с. 100.
- ^ Грейвер, Джек Э. (1991), «Матроиды жесткости», SIAM Journal on Discrete Mathematics , 4 (3): 355–368, doi : 10.1137/0404032 , MR 1105942 .
- ^ Уайтли, Уолтер (1996), «Некоторые матроиды из дискретной прикладной геометрии», Теория матроидов (Сиэтл, Вашингтон, 1995) , Contemporary Mathematics, vol. 197, Провиденс, Род-Айленд: Американское математическое общество, стр. 171–311, doi : 10.1090/conm/197/02540 , MR 1411692 .
- ^ Линдстрем, Бернт (1973), «О векторных представлениях индуцированных матроидов», Бюллетень Лондонского математического общества , 5 : 85–90, doi : 10.1112/blms/5.1.85 , MR 0335313 .
- ^ Инглтон, AW (1971), «Представление матроидов», Комбинаторная математика и ее приложения (Proc. Conf., Oxford, 1969) , Лондон: Academic Press, стр. 149–167, MR 0278974 .