Унифицированный матроид - Uniform matroid

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

Определение

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

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

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

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

В двойной матроид однородного матроида ${\displaystyle U{}_{n}^{r}}$ еще один однородный матроид ${\displaystyle U{}_{n}^{n-r}}$. Равномерный матроид самодвойственен тогда и только тогда, когда ${\displaystyle r=n/2}$.^[4]

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

Реализация

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

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

Алгоритмы

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

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

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

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

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

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

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

Смотрите также

• K-набор (геометрия)

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

1. Оксли, Джеймс Г. (2006), «Пример 1.2.7», Теория матроидов, Тексты для выпускников Оксфорда по математике, 3, Oxford University Press, стр. 19, ISBN  9780199202508. Относительно функции ранга см. Стр. 26.
2. Валлийский, Д. Дж. А. (2010), Теория матроидов, Courier Dover Publications, стр. 10, ISBN  9780486474397.
3. Оксли (2006), п. 27.
4. Оксли (2006), стр.77 и 111.
5. Оксли (2006), стр. 106–107 и 111.
6. Оксли (2006), п. 100.
7. Оксли (2006) С. 202–206.
8. Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001), «Глава 9: Медианы и статистика порядка», Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, стр. 183–196, ISBN  0-262-03293-7.
9. Jensen, Per M .; Корте, Бернхард (1982), "Сложность алгоритмов свойств матроидов", SIAM Журнал по вычислениям, 11 (1): 184–190, Дои:10.1137/0211014, МИСТЕР  0646772.
10. Оксли (2006), п. 126.
11. Оксли (2006), п. 26).
12. Оксли (2006) С. 48–49.
13. Валлийский (2010), п. 30.
14. Валлийский (2010), п. 297.