マトロイドランク

マトロイドの数学的理論では、マトロイドのランクはマトロイド内の独立集合の最大サイズです。マトロイドの要素のサブセットSのランクは、同様に、 Sの独立サブセットの最大サイズであり、マトロイドのランク関数は要素の集合をそのランクにマッピングします。

ランク関数はマトロイド理論の基本概念の 1 つであり、これを介してマトロイドが公理化されます。マトロイドランク関数は、サブモジュラー集合関数の重要なサブクラスを形成します。無向グラフ、行列、フィールド拡張などの他の特定の種類の数学的オブジェクトから定義されたマトロイドのランク関数は、これらのオブジェクトの研究において重要です。

例

すべての例において、E はマトロイドの基本集合であり、B はEのサブセットです。

M を自由マトロイドとし、独立集合がすべてEのサブセットであるとします。このとき、 Mのランク関数は単純に r ( B ) = | B | となります。
M を一様マトロイドとし、独立集合がEのk要素以下の部分集合(ある整数kに対して) であるとします。このとき、 Mのランク関数はr ( B ) = min( k , | B |)となります。
M を分割マトロイドとします。E の要素はカテゴリに分割され、各カテゴリcの容量はk _cで、独立セットはカテゴリcの要素を最大でk _c含むセットです。このとき、 Mのランク関数はr ( B ) = sum _c min( k _c , | B _c |)です。ここで、 B _{c は}カテゴリcに含まれるサブセットBです。
M をグラフィックマトロイドとし、独立集合が固定された無向グラフGのすべての非巡回エッジ集合（フォレスト）であるとします。ランク関数r ( B ) は、グラフの頂点の数からBの接続コンポーネントの数（単一頂点コンポーネントを含む）を引いた数になります。

性質と公理化

マトロイドのランク関数は次の特性に従います。

(R1) ランク関数の値は常に負でない整数であり、空集合のランクは 0 です。

(R2) の任意の2つの部分集合およびに対して、となる。つまり、階数はサブモジュラ集合関数となる。 $A$ $B$ $E$ $r(A\cup B)+r(A\cap B)\leq r(A)+r(B)$

(R3) 任意の集合と要素について、。 $A$ $x$ $r(A)\leq r(A\cup \{x\})\leq r(A)+1$

これらの性質は、マトロイドのランク関数を特徴付ける公理として使用できます。マトロイドのランク関数とは、有限集合の部分集合上のすべての整数値のサブモジュラー集合関数であり、すべてに対して不等式に従い、マトロイドのランク関数です。^[1]^[2] $r(A)\leq r(A\cup \{x\})\leq r(A)+1$ $A$ $x$

上記のプロパティは追加のプロパティを意味します:

ならば。つまり、ランクは単調関数です。 $A\subset B\subset E$ $r(A)\leq r(B)\leq r(E)$
$r(A)\leq |A|$ 。

ランクからのその他のマトロイド特性

ランク関数はマトロイドの他の重要な特性を決定するために使用できます。

集合が独立であるのは、その順位が濃度に等しい場合のみであり、従属であるのは、その順位よりも濃度が大きい場合のみである。^[3]
空でない集合は、その濃度が1プラスそのランクに等しく、集合から1つの要素を取り除いて形成されるすべての部分集合のランクが等しい場合、回路である。^[3]
集合の階数がその基数とマトロイドの階数に等しい場合、その集合は基底となる。^[3]
集合がそのランクに対して最大である場合、つまり同じランクを維持しながら追加できる別の要素が存在しない場合には、その集合は閉じています。
この差は部分集合の零点と呼ばれる。これは独立集合を得るためにから除去しなければならない要素の最小数である。 ^[4] $|A|-r(A)$ $A$ $A$
サブセットのコランクは、少なくとも 2 つの異なる量を参照できます。一部の著者は、これを双対マトロイドののランクを参照するために使用し、他の著者は、コランクを差を参照するために使用します。 $A$ $A$ $r^{*}(A)=|A|+r(E\setminus A)-r(E)$ $r(E)-r(A)$

特殊マトロイドのランク

グラフ理論では、グラフの回路ランク（またはサイクロマティック数）は、関連するグラフィックマトロイドの共ランクであり、残りのエッジがフォレストを形成するためにグラフから削除する必要があるエッジの最小数を測定します。^{[5]いくつかの著者は、この数によってパラメータ化されたグラフアルゴリズムの}パラメータ化された複雑さを研究しました。^[6]^[7]

線型代数学では、行列の列からの線形独立性によって定義される線型マトロイドの階数は行列の階数であり、 ^[8]列によって張られるベクトル空間の次元でもあります。

抽象代数学では、体拡大 L / Kの要素の集合から代数的独立性によって定義されるマトロイドの階数は超越次数として知られている。^[9]

マトロイドランク関数を効用関数として

マトロイド順位関数 (MRF) は、公平なアイテム割り当ての問題におけるエージェントの効用関数を表すために使用されてきました。エージェントの効用関数が MRF である場合、次のことを意味します。

エージェントの効用は収穫逓減の法則に従います（これはMRFがサブモジュラ関数であるという事実から生じます）。
各アイテムに対するエージェントの限界効用は二値（バイナリ）で、0 または 1 のいずれかです。つまり、バンドルにアイテムを追加すると、効用はまったく追加されないか、効用が 1 追加されます。

この設定には次の解決策が知られています。

Babaioff、Ezra、Feige ^[10]は、Prioritized Egalitarianと呼ばれる決定論的多項式時間の誠実なメカニズムを設計しました。これは、結果的にEFX ₀でもあるローレンツ優位の割り当てを出力し、効用の積を最大化し、1/2分数の最大シェアを達成し、評価が加算的である場合に完全な最大シェアを達成します。ランダムな優先順位では、このメカニズムは事前の羨望フリーでもあります。彼らはまた、限界効用が非正であるか範囲[1,1+ e ]にあるe二分法評価を研究しました。
Benabbou、Chakraborty、Igarashi、Zick ^[11]は、この設定では、すべてのパレート最適割り当てが効用合計（功利主義的福祉）を最大化し、すべての最大和割り当てにわたって対称な厳密に凹関数 f を最大化する割り当ての集合はfの選択に依存せず、これらすべてのf最大化割り当ては EF1 であることを示しています。これは、最大積割り当てがレキシミン最適割り当てであり、それらはすべて最大和かつ EF1 であることを意味します。彼らはまた、最大和かつ EF1 割り当て（必ずしも凹関数を最大化するわけではない）を計算する多項式時間アルゴリズムと、二部グラフの最大濃度マッチングに基づく MRF の特殊なケースに対して凹関数を最大化する多項式時間アルゴリズムを提示しています。

マトロイドランク関数は、総代替評価のサブクラスです。

参照

ランクオラクル

参考文献

^ Shikare, MM; Waphare, BN (2004)、組み合わせ最適化、Alpha Science Int'l Ltd.、p. 155、ISBN 9788173195600。
^ ウェールズ語、DJA (2010)、マトロイド理論、Courier Dover Publications、p. 8、ISBN 9780486474397。
^ abc Oxley (2006)、25ページ。
^ オクスリー（2006）、34ページ。
^ ベルジュ、クロード（2001）、「サイクロマティック数」、グラフ理論、クーリエ・ドーバー出版、pp. 27-30、ISBN 9780486419756。
^ コッパースミス、ドン;ヴィシュキン、ウジ(1985)、「'almost trees' における NP 困難問題の解決: 頂点カバー」、離散応用数学、10 (1): 27–45、doi : 10.1016/0166-218X(85)90057-5、Zbl 0573.68017。
^ フィアラ、イジー;クロクス、トン。 Kratochvíl、Jan (2001)、「Fixed-parameter complexity of λ-labelings」、離散応用数学、113 (1): 59–72、doi : 10.1016/S0166-218X(00)00387-5、Zbl 0982.05085。
^ オクスリー、ジェームズ G. (2006)、「マトロイド理論」、オックスフォード大学院数学テキスト第 3 巻、オックスフォード大学出版局、p. 81、ISBN 9780199202508。
^ Lindström, B. (1988)、「Matroids, algebraic and non-algebraic」、Algebraic, extremal and metric combinatorics、1986 (Montreal, PQ, 1986)、London Math. Soc. Lecture Note Ser.、vol. 131、Cambridge: Cambridge Univ. Press、pp. 166–174、MR 1052666。
^ Babaioff, Moshe; Ezra, Tomer; Feige, Uriel (2020-07-27). 「二分法評価のための公正かつ真実のメカニズム」arXiv : 2002.10704 [cs.GT].
^ Benabbou, Nawal; Chakraborty, Mithun; Igarashi, Ayumi; Zick, Yair (2020).評価が合わない場合に公正かつ効率的な配分を見つける. コンピュータサイエンスの講義ノート. Vol. 12283. pp. 32–46. arXiv : 2003.07060 . doi :10.1007/978-3-030-57980-7_3. ISBN 978-3-030-57979-1.S2CID 208328700 。

[1] Shikare, MM; Waphare, BN (2004)、組み合わせ最適化、Alpha Science Int'l Ltd.、p. 155、ISBN 9788173195600。

[2] ウェールズ語、DJA (2010)、マトロイド理論、Courier Dover Publications、p. 8、ISBN 9780486474397。

[o25-3] Oxley (2006)、25ページ。

[4] オクスリー（2006）、34ページ。

[5] ベルジュ、クロード（2001）、「サイクロマティック数」、グラフ理論、クーリエ・ドーバー出版、pp. 27-30、ISBN 9780486419756。

[6] コッパースミス、ドン;ヴィシュキン、ウジ(1985)、「'almost trees' における NP 困難問題の解決: 頂点カバー」、離散応用数学、10 (1): 27–45、doi : 10.1016/0166-218X(85)90057-5、Zbl 0573.68017。

[7] フィアラ、イジー;クロクス、トン。 Kratochvíl、Jan (2001)、「Fixed-parameter complexity of λ-labelings」、離散応用数学、113 (1): 59–72、doi : 10.1016/S0166-218X(00)00387-5、Zbl 0982.05085。

[8] オクスリー、ジェームズ G. (2006)、「マトロイド理論」、オックスフォード大学院数学テキスト第 3 巻、オックスフォード大学出版局、p. 81、ISBN 9780199202508。

[9] Lindström, B. (1988)、「Matroids, algebraic and non-algebraic」、Algebraic, extremal and metric combinatorics、1986 (Montreal, PQ, 1986)、London Math. Soc. Lecture Note Ser.、vol. 131、Cambridge: Cambridge Univ. Press、pp. 166–174、MR 1052666。

[10] Babaioff, Moshe; Ezra, Tomer; Feige, Uriel (2020-07-27). 「二分法評価のための公正かつ真実のメカニズム」arXiv : 2002.10704 [cs.GT].

[11] Benabbou, Nawal; Chakraborty, Mithun; Igarashi, Ayumi; Zick, Yair (2020).評価が合わない場合に公正かつ効率的な配分を見つける. コンピュータサイエンスの講義ノート. Vol. 12283. pp. 32–46. arXiv : 2003.07060 . doi :10.1007/978-3-030-57980-7_3. ISBN 978-3-030-57979-1.S2CID 208328700 。