Uniform matroid

редактировать

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

In ma тематики, унифицированный матроид - это матроид , в котором независимые множества - это в точности наборы, содержащие не более r элементов для некоторого фиксированного целого числа r. Альтернативное определение состоит в том, что каждая перестановка элементов является симметрией .

Содержание

1 Определение
2 Двойственность и миноры
3 Реализация
4 Алгоритмы
5 Связанные матроиды
6 См. Также
7 Ссылки

Определение

Унифицированный матроид $U nr {\ displaystyle U {} _ {n} ^ {r}}$ $U {} _ {n} ^ {r}$ определяется над набором элементов $n {\ displaystyle n}$ $n$ . Подмножество элементов является независимым тогда и только тогда, когда оно содержит не более $r {\ displaystyle r}$ $r$ элементов. Подмножество является основой, если оно имеет ровно $r {\ displaystyle r}$ $r$ элементов, и является схемой, если оно имеет ровно $r + 1 {\ displaystyle r + 1}$ $r + 1$ элементов. ранг подмножества $S {\ displaystyle S}$ $S$ равен $min (| S |, r) {\ displaystyle \ min (| S |, r) }$ $\ min (| S |, r)$ и ранг матроида равен $r {\ displaystyle r}$ $r$ .

Матроид ранга $r {\ displaystyle r}$ $r$ является однородным тогда и только если все его схемы имеют ровно $r + 1 {\ displaystyle r + 1}$ $r + 1$ элементов.

Матроид $U n 2 {\ displaystyle U {} _ { n} ^ {2}}$ $U {} _ {n} ^ {2}$ называется $n {\ displaystyle n}$ $n$ -point line .

Двойственность и несовершеннолетние

двойной матроид однородного матроида $U nr {\ displaystyle U {} _ {n} ^ {r}}$ $U {} _ {n} ^ {r}$ - еще один однородный матроид $U nn - r { \ Displaystyle U {} _ {n} ^ {nr}}$ $U {} _ {n} ^ {{nr}}$ . Однородный матроид самодуален тогда и только тогда, когда $r = n / 2 {\ displaystyle r = n / 2}$ $r = n / 2$ .

Каждый второстепенный однородного матроида однороден. Если ограничить однородный матроид $U nr {\ displaystyle U {} _ {n} ^ {r}}$ $U {} _ {n} ^ {r}$ одним элементом (до тех пор, пока $r < n {\displaystyle r$ $r <n$ ), получается матроид $U n - 1 r {\ displaystyle U {} _ {n-1} ^ {r}}$ $U {} _ {{n-1}} ^ {r}$ и сжатие на один элемент (до тех пор, пока $r>0 {\ displaystyle r>0}$ $r>0$ ) создает матроид $U n - 1 r - 1 {\ displaystyle U {} _ {n-1} ^ {r-1}}$ $U {} _ {{n-1}} ^ {{r-1}}$ .

Реализация

унифицированный матроид $U nr {\ displaystyle U {} _ {n} ^ {r}}$ $U {} _ {n} ^ {r}$ может быть представлен как матроид аффинно независимых подмножеств $n {\ displaystyle n}$ $n$ точки в общем положении в $r {\ displaystyle r}$ $r$ -мерном евклидовом пространстве, или как матроид линейно независимых подмножеств $n {\ displaystyle n}$ $n$ векторы в общем положении в $(r + 1) {\ displaystyle (r + 1)}$ $(r + 1)$ -мерном вещественном векторном пространстве.

Ева Равномерный матроид также может быть реализован в проективных пространствах и векторных пространствах по всем достаточно большим конечным полям. Однако поле должно быть достаточно большим, чтобы включать достаточно независимых векторов. Например, $n {\ displaystyle n}$ $n$ -point line $U n 2 {\ displaystyle U {} _ {n} ^ {2}}$ $U {} _ {n} ^ {2}$ может реализовываться только над конечными полями из $n - 1 {\ displaystyle n-1}$ $n-1$ или более элементов (потому что в противном случае проективная линия над этим полем имела бы меньше, чем $n {\ displaystyle n }$ $n$ очков): $U 4 2 {\ displaystyle U {} _ {4} ^ {2}}$ $U {} _ {4} ^ {2}$ не является двоичным матроидом, $U 5 2 {\ displaystyle U {} _ {5} ^ {2}}$ $U {} _ {5} ^ {2}$ не является тройным матроидом и т. Д. По этой причине однородные матроиды играют важную роль в гипотезе Роты. относительно запрещенной второстепенной характеристики матроидов, которые могут быть реализованы над конечными полями.

Алгоритмы

Проблема нахождения базиса минимального веса взвешенный однородный матроид хорошо изучен в информатике как задача выбора. Это может быть решено за линейное время.

. Любой алгоритм, который проверяет, является ли данный матроид однородным, при наличии доступа к матроиду через независимый оракул, должен выполнять экспоненциальное количество запросов оракула и поэтому не может принимать полиномиальное время.

Связанные матроиды

Если только $r ∈ {0, n} {\ displaystyle r \ in \ {0, n \}}$ $r \ in \ {0, n \}$ однородный матроид $U nr {\ displaystyle U {} _ {n} ^ {r}}$ $U {} _ {n} ^ {r}$ связан: это не прямая сумма двух меньших матроидов. Прямая сумма семейства однородных матроидов (не обязательно все с одинаковыми параметрами) называется матроидом разбиения.

Каждый однородный матроид - это матроид для мощения, поперечный матроид и строгий гаммоид.

Не каждый однородный матроид является графическим, а однородные матроиды представляют собой наименьший пример неграфического матроида, $U 4 2 {\ displaystyle U {} _ {4} ^ {2}}$ $U {} _ {4} ^ {2}$ . Унифицированный матроид $U n 1 {\ displaystyle U {} _ {n} ^ {1}}$ $U {} _ {n} ^ {1}$ является графическим матроидом $n {\ displaystyle n}$ $n$ -ребень дипольный граф, а двойственный однородный матроид $U nn - 1 {\ displaystyle U {} _ {n} ^ {n-1}}$ $U {} _ {n} ^ {{n-1}}$ - графический матроид его двойного графа, $n {\ displaystyle n}$ $n$ -edge граф цикла. $U n 0 {\ displaystyle U {} _ {n} ^ {0}}$ $U {} _ {n} ^ {0}$ - графический матроид графа с $n {\ displaystyle n}$ $n$ петли, а $U nn {\ displaystyle U {} _ {n} ^ {n}}$ $U {} _ {n} ^ {n}$ - графический матроид $n {\ displaystyle n}$ $n$ -ребень лес. Кроме этих примеров, каждый унифицированный матроид $U nr {\ displaystyle U {} _ {n} ^ {r}}$ $U {} _ {n} ^ {r}$ с $1 < r < n − 1 {\displaystyle 1$ $1 <r <n-1$ содержит $U 4 2 {\ displaystyle U { } _ {4} ^ {2}}$ $U {} _ {4} ^ {2}$ как второстепенное и поэтому не является графическим.

Строка с точкой $n {\ displaystyle n}$ $n$ предоставляет пример матроида Сильвестра, матроида, в котором каждая строка содержит три или более точек.

См. также

K-set (geometry)

Ссылки