Униформа матроида

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

Определение

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

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

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

Двойственность и миноры

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

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

Реализация

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

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

Алгоритмы

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

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

Родственные матроиды

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

Каждый однородный матроид — это матроид брусчатки . поперечный матроид и строгий гаммоид .

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

The $n$Линия -point представляет собой пример матроида Сильвестра , матроида, в котором каждая линия содержит три или более точек.

См. также

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