分割マトロイド

数学において、分割マトロイドまたは分割マトロイドは、一様マトロイドの直和であるマトロイドです。^[1]これは、要素が異なるカテゴリに分割されている基本セットに対して定義されます。各カテゴリには、容量制約、つまりこのカテゴリから許可される要素の最大数があります。分割マトロイドの独立セットは、各カテゴリの要素の数が最大でカテゴリ容量であるセットとまったく同じです。

を互いに素な集合（「カテゴリ」）の集合とします。を（「容量」）を持つ整数とします。すべてのインデックス に対して のとき、サブセットを「独立」であると定義します。この条件を満たす集合は、マトロイドの独立集合（パーティションマトロイドと呼ばれる）を形成します。 ${\displaystyle C_{i}}$${\displaystyle d_{i}}$${\displaystyle 0\leq d_{i}\leq |C_{i}|}$${\displaystyle I\subset \bigcup _{i}C_{i}}$${\displaystyle i}$${\displaystyle |I\cap C_{i}|\leq d_{i}}$

これらの集合は、カテゴリまたは分割マトロイドの ブロックと呼ばれます。${\displaystyle C_{i}}$

分割マトロイドの基底は、すべてのブロックとの交差がちょうど の大きさである集合である。マトロイドの回路は、ちょうど の大きさの単一ブロックのサブセットである。マトロイドのランクは である。^[2]${\displaystyle C_{i}}$${\displaystyle d_{i}}$${\displaystyle C_{i}}$${\displaystyle d_{i}+1}$${\displaystyle \sum d_{i}}$

すべての一様マトロイドは 、要素の単一のブロックを持ち、 である分割マトロイドです。すべての分割マトロイドは、各ブロックごとに 1 つずつある一様マトロイドの集合の直和です。 ${\displaystyle U{}_{n}^{r}}$${\displaystyle C_{1}}$${\displaystyle n}$${\displaystyle d_{1}=r}$

いくつかの出版物では、分割マトロイドの概念は、より制限的に定義され、すべての となる。このより制限的な定義に従う分割は、そのブロックによって与えられる分離集合の族の横断マトロイドである。^[3]${\displaystyle d_{i}=1}$

それらが形成される均一マトロイドと同様に、分割マトロイドの双対マトロイドも分割マトロイドであり、分割マトロイドのすべてのマイナーも分割マトロイドです。分割マトロイドの直和も分割マトロイドです。

グラフにおける最大マッチングとは、 2 つの辺が端点を共有しないという条件のもとで、可能な限り大きい辺の集合のことである。二分割 の二部グラフでは、 において 2 つの辺が端点を共有しないという条件を満たす辺の集合は、 において頂点ごとに 1 つのブロックを持ち、それぞれの数が1 に等しい分割マトロイドの独立集合である。 において 2 つの辺が端点を共有しないという条件を満たす辺の集合は、 2 番目の分割マトロイドの独立集合である。したがって、二部最大マッチング問題は、これら 2 つのマトロイドのマトロイド交差として表すことができる。^[4]${\displaystyle (U,V)}$${\displaystyle U}$${\displaystyle U}$${\displaystyle d_{i}}$${\displaystyle V}$

より一般的には、グラフのマッチングは、グラフ内のすべての奇数サイクルが2つ以上の次数2の頂点を含む三角形である場合にのみ、2つのマトロイドの交差として表すことができます。^[5]

クリーク複合体は、グラフの頂点集合の族であり、グラフの完全な部分グラフを誘導する。クリーク複合体がマトロイドを形成するのは、 が完全な多部グラフである場合のみであり、この場合、結果として得られるマトロイドは分割マトロイドである。クリーク複合体は、あらゆる となる分割マトロイドの族の共通部分として形成できる集合系そのものである。^[6]${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle d_{i}=1}$

ラベル付き要素の集合に対して定義できる異なる分割マトロイドの数は、 ${\displaystyle n}$${\displaystyle n=0,1,2,\dots }$

1、2、5、16、62、276、1377、7596、45789、298626、2090910、...（OEISの配列A005387）。

この数列の指数生成関数はである。^[7]${\displaystyle f(x)=\exp(e^{x}(x-1)+2x+1)}$