一様マトロイド

数学において、一様マトロイドとは、ある固定された整数rに対して、独立集合が最大r個の要素を含む集合とまったく同じであるマトロイドです。別の定義では、要素のすべての順列は対称性です。

一様マトロイドは要素の集合に対して定義される。要素のサブセットが独立であるためには、そのサブセットに含まれる要素が最大で 個である必要がある。サブセットがちょうど 個の要素を持つ場合、そのサブセットは基底であり、ちょうど 個の要素を持つ場合、そのサブセットは回路である。サブセットの階数は であり、マトロイドの階数は である。^{[1] [2]}${\displaystyle U{}_{n}^{r}}$${\displaystyle n}$${\displaystyle r}$${\displaystyle r}$${\displaystyle r+1}$${\displaystyle S}$${\displaystyle \min(|S|,r)}$${\displaystyle r}$

階数のマトロイドが均一であるのは、その回路の全てがちょうど個の要素を持つ場合に限られます。^[3]${\displaystyle r}$${\displaystyle r+1}$

マトロイドは-点線と呼ばれます。 ${\displaystyle U{}_{n}^{2}}$${\displaystyle n}$

一様マトロイドの双対マトロイドは別の一様マトロイドである。一様マトロイドが自己双対となるのは、次の場合のみである。^[4]${\displaystyle U{}_{n}^{r}}$${\displaystyle U{}_{n}^{nr}}$${\displaystyle r=n/2}$

一様マトロイドのすべてのマイナーは一様である。一様マトロイドを1つの要素で制限すると（ である限り）、マトロイドが生成され 、それを1つの要素で縮小すると（ である限り）、マトロイド が生成される。^[5]${\displaystyle U{}_{n}^{r}}$${\displaystyle r<n}$${\displaystyle U{}_{n-1}^{r}}$${\displaystyle r>0}$${\displaystyle U{}_{n-1}^{r-1}}$

一様マトロイドは、次元ユークリッド空間の一般的な位置にある点のアフィン独立部分集合のマトロイドとして、または次元実ベクトル空間の一般的な位置にあるベクトルの線形独立部分集合のマトロイドとして表すことができます。 ${\displaystyle U{}_{n}^{r}}$${\displaystyle n}$${\displaystyle r}$${\displaystyle n}$${\displaystyle (r+1)}$

すべての一様マトロイドは、十分に大きい有限体全体の射影空間とベクトル空間でも実現できます。^[6]しかし、体は十分な数の独立ベクトルを含むのに十分大きくなければなりません。たとえば、点直線は以上の元の有限体上でのみ実現できます(そうでなければ、その体上の射影直線の点数が少なくなるため)。はバイナリマトロイドではなく、は三元マトロイドではありません。このため、一様マトロイドは、有限体上で実現できるマトロイドの禁じられたマイナー特徴付けに関するRota の予想において重要な役割を果たします。 ^[7]${\displaystyle n}$${\displaystyle U{}_{n}^{2}}$${\displaystyle n-1}$${\displaystyle n}$${\displaystyle U{}_{4}^{2}}$${\displaystyle U{}_{5}^{2}}$

重み付き一様マトロイドの最小重み基底を求める問題は、コンピュータサイエンスでは選択問題としてよく研究されている。これは線形時間で解ける可能性がある。^[8]

独立オラクルを介してマトロイドにアクセスし、与えられたマトロイドが均一であるかどうかをテストするアルゴリズムは、指数関数的な数のオラクルクエリを実行する必要があるため、多項式時間をかけることはできません。^[9]

でない限り、一様マトロイドは連結であり、2つの小さなマトロイドの直和ではありません。^{[10]一様マトロイド族（必ずしもすべてが同じパラメータを持つとは限らない）の直和は、}分割マトロイド と呼ばれます。 ${\displaystyle r\in \{0,n\}}$${\displaystyle U{}_{n}^{r}}$

すべての一様マトロイドは舗装マトロイド^[11]、横断マトロイド[ ^12]、および厳密なガモイド^[6]である。

すべての一様マトロイドがグラフィックであるとは限らず、一様マトロイドは非グラフィック マトロイドの最小の例 を提供します。一様マトロイドは -エッジ双極子グラフのグラフィック マトロイドであり、双対一様マトロイドはその双対グラフである-エッジサイクル グラフのグラフィック マトロイドです。は自己ループを持つグラフ のグラフィック マトロイドであり、 は- エッジフォレストのグラフィック マトロイドです。これらの例以外では、を持つすべての一様マトロイドはマイナーとして を含むため、グラフィックではありません。^[13]${\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}}$

点線はシルベスターマトロイドの一例であり、すべての線に3つ以上の点が含まれるマトロイドである。^[14]${\displaystyle n}$

• Kセット（ジオメトリ）