균일매트로이드

수학에서, 균일한 매트로이드는 일부 고정 정수 r에 대해 독립된 집합이 정확히 최대 r 원소를 포함하는 매트로이드다.다른 정의는 원소의 모든 순열은 대칭이라는 것이다.

정의

균일한 매트로이드 $U{\displaystyle }$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$ U${}_{n}^{r}}}$은(는) $n{\displaystyle }$ ${\displaystyle n}$ 요소$$ 집합에 걸쳐 정의된다$$.요소의 하위 집합은 최대 $r{\displaystyle }$ ${\displaystyle r}$ 요소를$$ 포함하는 경우에만 독립적이다.부분집합은 $정확히{\displaystyle }$ r ${\displaystyle r}$ 요소를$$ 가진 경우 기준이 되며, $정확히{\displaystyle }$r + ${\displaystyle 1}${\$displaystyle r+$1} $요소$를 가진 경우 회로가 된다.하위 집합 $S{\displaystyle }$ ${\displaystyle S}$의 순위는 ${\displaystyle 최소(S}$ ${\displaystyle ,}$ ${\displaystyle r}$) ${\displaystyle \min(S ,r)}$이고, 매트로이드의 $순위$는 r ${\displaystyle r}$이다$.$^[1][2]

순위 $r{\displaystyle }$ ${\displaystyle r}$의 매트로드는 모든 회로에 $r{\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle r+1}$ 요소가$$ 정확히 있는 경우에만 균일하다$$.^[3]

매트로이드 $U{\displaystyle }$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ ${\$을 $n{\displaystyle }$ ${\displaystyle n}$ -point$$ line이라고 한다$$.

이중성과 미성년자

균일한 매트로이드 $U{\displaystyle }$ n ${\displaystyle {}_{}^{}}$ ${\$${\displaystyle {\_}_{}^{}}$${n}^{r}}$의 이중 매트로이드 U $n$ -$$r {\$displaystyle$ U${}_{n}^{n-r$의 다른 균일한 매트로이드의 경우, 그리고 $r{\displaystyle }$= ${\displaystyle n}$ / ${\displaystystyle r=n/2}$인 경우에만 자가 이중이다$.$^[4]

제복의 단조로운 매트는 모두 균일하다.하나의 요소(한 r<>로 n{\displaystyle r<, n})에 의해 일정한matroid U와 r{\displaystyle U{}_{n}^{r}}를 제한하고 하나의 요소(한 r을로;0{\displaystyle r>0})로 옮기는 것 −은matroid Un1을 만들어 내는matroid Un− 1r{\displaystyle U{}_{n-1}^{r}}을 생산한다. r1−${\displaystyle$ U${}_{n-1}^{r-1$^[5]

실현

균일한 매트로이드 $U{\displaystyle }$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$은(는) $r{\displaystyle }$ ${\displaystyle r}$ -차원$$ 유클리드 공간에서 일반 위치에 $있는{\displaystyle }$ n ${\displaystyle n$$}$ 지점의$$ 부착형 독립 서브셋 또는 $유전자{\displaystyle }$내 n {\$displaysty$ n$$} 벡터의 선형 독립 서브셋의 매트로 나타낼 수 있다$$.ral 위치(${\displaystyle r}$+ ${\displaystyle 1}$) ${\displaystyle(r+1)}$ -차원$$ 실제 벡터 공간.

모든 균일한 매트로이드도 충분히 큰 모든 유한한 장의 투영 공간과 벡터 공간에서 실현될 수 있다.^[6]그러나 이 필드는 독립 벡터를 충분히 포함할 수 있을 만큼 커야 한다.예를 들어, $n{\displaystyle }$ ${\displaystyle n}$ -point$$ $line{\displaystyle }$ U ${\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$}}$개$는${\displaystyle }$n - ${\displaystyle 1}${\$displaystyn-1}$개$$ 이상의 유한 필드에서만 실현할 수 있다$$(그렇지 않으면 해당 필드 위의 투영 라인은 $n{\displaystyle }$ ${\displaystyle$ n}$포인트보다$작기$$ 때문이다).${\displaystyle U}$ ${\displaystyle {}_{\mathrm{}}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ ${\$은 바이너리 매트로이드, $U{\displaystyle }$ ${\displaystyle {\mathrm{}}_{}^{}}$ 2 ${\$은 테너리 매트로이드 등이 아니다$$$$.이 때문에, 한정된 분야에 걸쳐 실현될 수 있는 매트로이드의 금지된 사소한 특성화에 관한 로타의 추측에 획일적인 매트로이드가 중요한 역할을 한다.^[7]

알고리즘

가중치 균일모직의 최소체중 기준을 찾는 문제는 선택문제로서 컴퓨터 공학에서 잘 연구되고 있다.그것은 선형적인 시간에 해결될 수 있다.^[8]

주어진 매트로이드의 균일성 여부를 시험하는 알고리즘은 독립성 오라클을 통해 매트로이드에 대한 접근 권한을 부여받으면 기하급수적인 수의 오라클 쿼리를 수행해야 하므로 다항식 시간은 소요될 수 없다.^[9]

관련매트로이드

$r{\displaystyle \in \{0\},}$ ${\displaystyle n}$}$${\$displaystyle$r\$in$\{${\displaystyle {}_{}^{}}$$,n\}}}$이(^[10]가$)$ 연결되지 않는 한, $동일$한 매트리스 U n r {\$displaystyle U{}_{n}^{r}}}}$이(가) 두 개의 작은 매트리스의 직접 합이 아니다.균일한 매트로이드 계열의 직접적인 합을 칸막이 매트로이드라고 한다.

모든 균일한 매트로이드는 포장매트로이드,^[11] 횡단매트로이드^[12], 그리고 엄격한 가모이드다.^[6]

모든 균일한 매트로이드가 그래픽은 아니며, 균일한 매트로이드가 비그래픽 ${\displaystyle {}_{}^{}}$의 ${\displaystyle {}_{\mathrm{}}^{}}$ 작은 예인 U 4 2 {\$displaystyle$ U${}_{4$$2$}}.균일한 매트로이드 ${\displaystyle {}_{}^{}}$ $1 {\$ U${}_{n}^{1$}:{1$}:{$1}은$$(는) $n{\displaystyle }$ ${\displaystyle n}$ - edge$$$$ dipole 그래프의 그래픽 매트로이드 $U{\displaystyle }$ ${\displaystyle {}_{}^{}}$- ${\displaystyle 1_{}^{}}$ ${\$ U${}_{n}^{n-1}$는 해당$$ 이중 그래프의 그래픽 $매트로이드$인$n {\$daystycycycycycycycyledraid.${\displaystyle {}_{}^{}}$ ${\displaystyle {\mathrm{}}_{}^{}}$ ${\displaystyle$ U${}_{n}^{0}}$은(는) ${\displaystyle n}$self-lups가$$ 있는 그래프의 그래픽 매트로이드, ${\displaystyle {}_{}^{}}$ ${\$ {\$displaystyle$ U${}_$${$n}^{$n}}}}}}}}}$은(는) 에지$$ 포리스트의 그래픽 매트로이다.이러한 예시들을 하고, <${\displaystyle {}_{}^{}}$ < - {\$displaystyle 1><r<n-1$$}{n}^{$r}}}{$r}}}}{$r$}}}}$이(가) 있는$$ 모든 균일한 매트로이드 $U{\displaystyle }$ n r ${\$}}을 ${\displaystyle {}_{}^{}}$로서 포함하므로 그래픽이 아니다.^[13]

$n{\displaystyle }$ ${\displaystyle n}$ -point$$ 라인은 모든 라인이 3개 이상의 점을 포함하는 Matroid인 Sylvester matroid의 예를 제공한다.^[14]

참고 항목

• K 집합(지오메트리)

참조