Loading article…
グラフ理論という数学の分野では、エッジカラーグラフのレインボーマッチングは、すべてのエッジが異なる色を持つ マッチングです。
意味
辺色グラフG = ( V , E )が与えられた場合、 G内のレインボーマッチングM は、隣接しない辺のペアの集合です。つまり、2 つの辺が共通の頂点を共有せず、集合内のすべての辺が異なる色を持ちます。
最大レインボー マッチングは、可能な限り最大数のエッジを含むレインボー マッチングです。
歴史
レインボーマッチングは、ラテン方陣の横断との関連を考えると特に興味深いものです。
K n , nによって、n + n頂点の完全二部グラフを表します。 K n , nのすべての適切なn辺の色付けは、次数nのラテン方陣に対応します。レインボー マッチングは、ラテン方陣の横断、つまり各行と各列に 1 つずつ、異なるエントリを含むn個の位置の選択に対応します。
ラテン方陣の横断とKn , nにおけるレインボーマッチングとの関連は、三角形のないグラフにおけるレインボーマッチングの研究へのさらなる関心を呼び起こした。[1]
各エッジが単一の色である場合の存在
各辺が単一の色を持ち、同じ色の 2 つの辺に共通の頂点がない場合、 その辺の色付けは適切であると呼ばれます。
適切な辺の色付けは、完全なレインボー マッチングの存在を保証するものではありません。たとえば、グラフK 2,2 ( 2+2 頂点の完全な二部グラフ) を考えてみましょう。辺( x 1、y 1 )と( x 2、y 2 )が緑色、辺( x 1、y 2 )と( x 2、y 1 )が青色であるとします。これは適切な色付けですが、完全なマッチングは 2 つしかなく、それぞれが単一の色で色付けされています。これにより、大きなレインボー マッチングの存在が保証されるのはいつなのかという疑問が生じます。
頂点の数のみに依存する境界
この問題に関する研究の多くは、ラテン方陣のラテン横断線の用語を使用して発表されました。レインボーマッチングの用語に翻訳すると次のようになります。
- 1967年、HJライザーはnが奇数のとき、 Kn , nのすべての適切な辺彩色にはサイズnのレインボーマッチングが存在すると予想した。[2 ]
- 1975年、SKスタインとブルーディは、nが偶数のとき、 Kn 、nのすべての適切な辺彩色にはサイズn -1のレインボーマッチングが存在すると予想しました。[3] （この場合、サイズnのレインボーマッチングが存在する必要がないことは知られています）。
スタインのより一般的な予想は、サイズn -1のレインボーマッチングは、適切なエッジカラーリングだけでなく、各色がちょうどn個のエッジに現れる任意のカラーリングに対しても存在するというものである。[2]
これらの推測のより弱いバージョンがいくつか証明されています。
- Kn , nの適切な辺彩色には、サイズ2n /3のレインボーマッチングが存在する。[4]
- K n , nの任意の適切な辺彩色には、大きさが のレインボーマッチングが存在する[5]
- Kn , nの任意の適切な辺彩色には、サイズn -11log22 ( n )のレインボーマッチングが存在する。[6]
- Kn , nの適切な辺彩色には、サイズn – O(logn / loglogn )のレインボーマッチングが存在する。[7]
- K n , nのすべての適切な辺彩色には、サイズn – 1のレインボーマッチングが存在する。[8] (プレプリント)
最小次数に応じた境界
王は、最小次数dで少なくともf ( d )個の頂点を持つ適切に辺色付けされたグラフGのすべてに、サイズdのレインボーマッチングが存在するような関数f ( d )が存在するかどうかを尋ねた。[9]明らかに少なくとも2d個の頂点が必要であるが、何個あれば十分なのだろうか？
- Diemunschらはこの質問に肯定的に答え、最小次数dと少なくともf ( d )=98δ/23の適切に辺色付けされたグラフGが与えられた場合、 G内にサイズdのレインボーマッチングが存在することを示した。[10]
- この境界は後にアンドラス・ギャルファスとガボール・N・サルコジによってf ( d )= 4d -3に改良された。 [11]彼らはまた、少なくとも2dの頂点を持つグラフには、少なくともd - 2d2 / 3の大きさのレインボーマッチングが存在することを示した。これらは現在までに知られている最も優れた推定値である。
同じエッジが異なる色を持つ可能性がある場合の存在
各辺には複数の異なる色がある可能性があると仮定します。ただし、同じ色の 2 つの辺には共通の頂点が存在しない必要があります。つまり、各色はマッチングです。レインボー マッチングの存在を保証するには、何色必要でしょうか。
完全二部グラフでは
Drisko [12]は、ラテン長方形の用語を使用してこの問題を研究しました。彼は、任意のn ≤ kに対して、完全二部グラフKn、kにおいて、サイズnの2n-1個のマッチング（=色）の任意の族には、サイズnの完全なレインボーマッチングが存在することを証明しました。彼はこの定理を群作用と差集合に関する問題に適用しました。
Drisko は、 2 n – 1 個のマッチングが必要になる場合もあることも示しました。2 n – 2 個のマッチングの族を考えます。そのうちのn – 1 個は{( x 1 , y 1 ), ( x 2 , y 2 ), ..., ( x n , y n )}で、他のn – 1 個は{( x 1 , y 2 ), ( x 2 , y 3 ), …, ( x n , y 1 ) }です。この場合、最大のレインボー マッチングのサイズはn – 1になります(たとえば、最初のn – 1 個のマッチングからそれぞれ 1 つのエッジを取得します)。
アロン[13]は、ドリスコの定理が加法数論における古い結果[14]を意味することを示した。
一般的な二部グラフでは
AharoniとBerger [15]はDriskoの定理を任意の二部グラフに一般化した。すなわち、二部グラフ内のサイズnの2n -1マッチングの任意の族には、サイズnのレインボーマッチングが存在する。
Aharoni、Kotlar、Ziv [16]は、Driskoの極値例がどの二部グラフでも一意であることを示した。
一般的なグラフでは
一般的なグラフでは、2 n – 1 個のマッチングではもはや十分ではありません。nが偶数の場合、Drisko の例にマッチング{ ( x 1 , x 2 ), ( y 1 , y 2 ), ( x 2 , x 3 ), ( y 2 , y 3 ), … }を追加して、レインボー マッチングのない 2 n – 1 個のマッチングの族を得ることができます。
アハロニ、バーガー、チュドノフスキー、ハワード、シーモア[17]は、一般的なグラフでは、3n -2のマッチング（＝色）が常に十分であることを証明した。これが厳密であるかどうかは不明である。現在、偶数nの場合の最良の下限は2nであり、奇数nの場合は2n - 1である。[18]
レインボー分数マッチング
分数マッチングは、各エッジに負でない重みが割り当てられたエッジのセットで、各頂点に隣接する重みの合計は最大で 1 になります。分数マッチングのサイズは、すべてのエッジの重みの合計です。これはマッチングの一般化であり、色とレインボー マッチングの両方を一般化するために使用できます。
- 各色がサイズnのマッチングであることを要求する代わりに、要件は緩和されます。各「色」は任意のエッジ セットにすることができますが、少なくともサイズnの部分マッチングを許可する必要があります。
- レインボー マッチングを探す代わりに、レインボー部分マッチング(正の重みを持つ各エッジが異なる色になる部分マッチング) を探します。
二部グラフでは、最大分数マッチングサイズは最大マッチングサイズに等しいことが知られています。したがって、AharoniとBergerの定理[15]は次の式と同等です。nを任意の正の整数とします。二部グラフ内のサイズnの2n -1個の分数マッチング（=色）の任意の族が与えられた場合、サイズnのレインボー分数マッチングが存在します。
Aharoni、Holzman、Jiangはこの定理を次のように任意のグラフに拡張する。nを任意の正の整数または半整数とする。任意のグラフ内の少なくともn個のサイズを持つ2n個の分数マッチング（=色）の族には、サイズnのレインボー分数マッチングが存在する。[18] ：Thm.1.5 2nは任意のグラフ内の分数マッチングの最小値である。極端な場合は奇数長のサイクルを使用して構築される。
部分的な証明
完全な分数マッチングの場合、上記の両方の定理は、カラフルなカラテオドリの定理から導くことができます。
Eのすべての辺eについて、1 eをサイズ| V |のベクトルとします。ここで、Vの各頂点vについて、 1 eの要素v は、 e がvに隣接している場合は 1 、そうでない場合は 0 です (したがって、各ベクトル1 eには 2 つの 1 と| V | -2 つの 0 が含まれます)。すべての分数マッチングは、各要素が最大で 1 である辺の円錐結合に対応します。各要素がちょうど1 である円錐結合は、完全分数マッチングに対応します。言い換えると、1 v ( | V |個の 1 のベクトル) がFのeについてのベクトル1 eの円錐包に含まれる場合のみ、辺のコレクションFは完全分数マッチングを許容します。
2 n個の頂点を持つグラフを考えてみましょう。2 n個のエッジのサブセットがあり、それぞれが完全分数マッチング (サイズn ) を許容するとします。これは、ベクトル1 v がこれらのn個のサブセットのそれぞれの円錐包にあることを意味します。カラフルなカラテオドリの定理により、円錐包に1 vが含まれる2 n 個のエッジ (各サブセットから 1 つ)の選択が存在します。これは、レインボー完全分数マッチングに対応します。式2 n はベクトル1 eの次元です。各ベクトルには2 n個の要素があります。
ここで、グラフが二部グラフであると仮定します。二部グラフでは、ベクトル1 eに制約があります。グラフの各部分に対応する要素の合計は 1 でなければなりません。したがって、ベクトル1 e は(2 n – 1)次元空間に存在します。したがって、エッジのサブセットが2 n – 1 個しかない場合も、上記と同じ議論が当てはまります。
ハイパーグラフにおけるレインボーマッチング
r-ユニフォームハイパーグラフは、それぞれがちょうどr個の頂点を含むハイパーエッジの集合です (したがって、2-ユニフォームハイパーグラフは自己ループのない単なるグラフです)。Aharoni、Holzman、Jiang は、次のようにその定理をそのようなハイパーグラフに拡張しました。n を任意の正の有理数とします。r-ユニフォームハイパーグラフ内のサイズが少なくとも n の ⌈ r ⋅ n ⌉ 分数マッチング (=色) の族には、サイズがnのレインボー分数マッチングがあります。[ 18] : Thm.1.6 nが整数のとき、 ⌈ r ⋅ n ⌉は最小です。
r部ハイパーグラフは、頂点が r 個の互いに素な集合に分割され、各ハイパーエッジが各集合の頂点を 1 つだけ含む r 一様ハイパーグラフです(したがって、2 部ハイパーグラフは単なる 2 部グラフです)。n を任意の正の整数とします。r部ハイパーグラフ内のサイズが少なくともnであるrn – r + 1 個の分数マッチング (= 色) の族には、サイズがnのレインボー分数マッチングがあります。[18] : Thm.1.7 rn – r + 1は可能な限り小さいです。極端な場合は、n = r – 1が素数冪で、すべての色が順序nの切断された射影平面のエッジである場合です。したがって、各色にはn 2 = rn – r + 1 個のエッジとサイズnの分数マッチングがありますが、そのサイズの部分マッチングにはすべてのrn – r + 1個のエッジが必要です。[19]
部分的な証明
完全分数マッチングの場合、上記の定理は両方とも、前のセクションのカラフルなカラテオドリー定理から導くことができます。一般的なr -一様ハイパーグラフ（サイズnの完全マッチングを許容）の場合、ベクトル1 e は( rn ) -次元空間に存在します。 r -一様 r -部構成ハイパーグラフの場合、 r -部構成制約により、ベクトル1 e は( rn – r + 1) -次元空間に存在することになります。
注記
上記の結果は、レインボー分数マッチングにのみ当てはまります。対照的に、 r -一様ハイパーグラフにおけるレインボー積分マッチングのケースは、あまり理解されていません。サイズnのレインボー マッチングに必要なマッチングの数は、nとともに少なくとも指数関数的に増加します。
計算
ガリーとジョンソンは、最大レインボーマッチングの計算は、エッジカラー二部グラフの場合でもNP完全であることを示した。[20]
アプリケーション
レインボーマッチングはパッキング問題を解くために応用されてきた。[21]
参照
参考文献
- ^ ウェスト、DB（2009）、レインボーマッチング
- ^ ab アハロニ、ロン;バーガー、イーライ。コトラー、ダニ。ジヴ、ラン(2017-01-04)。 「スタインの推測について」。ハンブルク大学アブハンドルゲン数学セミナー。87 (2): 203–211。土井：10.1007/s12188-016-0160-3。ISSN 0025-5858。S2CID 119139740。
- ^ スタイン、シャーマン (1975-08-01). 「ラテン方陣の横断とその一般化」.太平洋数学ジャーナル. 59 (2): 567–575. doi : 10.2140/pjm.1975.59.567 . ISSN 0030-8730.
- ^ Koksma, Klaas K. (1969-07-01). 「ラテン方陣における部分横断の順序の下限値」. Journal of Combinatorial Theory . 7 (1): 94–95. doi : 10.1016/s0021-9800(69)80009-8 . ISSN 0021-9800.
- ^ Woolbright, David E (1978-03-01). 「n × n ラテン方陣には少なくとも n−n 個の異なる記号を含む横断線がある」. Journal of Combinatorial Theory, Series A . 24 (2): 235–237. doi : 10.1016/0097-3165(78)90009-2 . ISSN 0097-3165.
- ^ Hatami, Pooya; Shor, Peter W. (2008-10-01). 「ラテン方陣の部分横断線の長さの下限値」. Journal of Combinatorial Theory, Series A . 115 (7): 1103–1113. doi : 10.1016/j.jcta.2008.01.002 . ISSN 0097-3165.
- ^ Keevash, Peter; Pokrovskiy, Alexey; Sudakov, Benny; Yepremyan, Liana (2022-04-15). 「Ryserの予想と関連問題に対する新しい境界」.アメリカ数学会誌、シリーズB. 9 ( 8): 288–321. arXiv : 2005.00526 . doi : 10.1090/btran/92 . ISSN 2330-0000.
- ^ Montgomery, Richard (2023). 「大きな偶数 nに対するRyser-Brualdi-Stein予想の証明」arXiv : 2310.19779 [math.CO].
- ^ 王光輝 (2009)、「適切にエッジカラー化されたグラフにおけるレインボーマッチング」、電子組合せ論ジャーナル、18 (1): 162
- ^ Diemunsch, Jennifer; Ferrara, Michael; Lo, Allan; Moffatt, Casey; Pfender, Florian; Wenger, Paul S. (2012)、「適切にエッジカラー化されたグラフにおけるサイズ δ(G) のレインボーマッチング」、The Electronic Journal of Combinatorics、19 (2): 52、arXiv : 1108.2521、doi : 10.37236/2443、S2CID 119177198
- ^ Gyarfas, Andras; Sarkozy, Gabor N. (2012). 「Rainbow matchings and partial transversals of Latin squares」. arXiv : 1208.5670 [CO math. CO].
- ^ Drisko, Arthur A. (1998-11-01). 「行ラテン長方形の横断」. Journal of Combinatorial Theory, Series A. 84 ( 2): 181–195. doi : 10.1006/jcta.1998.2894 . ISSN 0097-3165.
- ^ Alon, Noga (2011). 「ハイパーグラフにおける多色マッチング」.モスクワ組合せ論および数論ジャーナル. 1 : 3–10.
- ^ フローレス、カルロス; オルダス、オスカー (1996-05-01). 「エルデシュ-ギンツブルグ-ジフの定理について」.離散数学. 152 (1–3): 321–324. doi : 10.1016/0012-365x(94)00328-g . ISSN 0012-365X.
- ^ ab Aharoni, Ron; Berger, Eli (2009-09-25). 「$r$-Partite $r$-Graphs におけるレインボーマッチング」. The Electronic Journal of Combinatorics . 16 (1). doi : 10.37236/208 . ISSN 1077-8926.
- ^ ロン、アハロニ;コトラー、ダニ。ジヴ、ラン(2018-01-01)。 「Drisko と Erdős-Ginzburg-Ziv の定理における極端な場合の一意性」。欧州組合せ論ジャーナル。67 : 222–229。土井：10.1016/j.ejc.2017.08.008。ISSN 0195-6698。S2CID 38268762。
- ^ ロン、アハロニ;バーガー、イーライ。チュドノフスキー、マリア。ハワード、デイビッド。ポール・シーモア (2019-06-01)。 「一般的なグラフにおける大きな虹の一致」。欧州組合せ論ジャーナル。79 : 222–227。arXiv : 1611.03648。土井：10.1016/j.ejc.2019.01.012。ISSN 0195-6698。S2CID 42126880。
- ^ abcd アハロニ、ロン;ロン、ホルツマン。江、紫林（2019-10-29）。 「レインボーの分数マッチング」。コンビナトリカ。39 (6): 1191–1202。arXiv : 1805.09732。土井：10.1007/s00493-019-4019-y。ISSN 0209-9683。S2CID 119173114。
- ^ Füredi, Zoltán (1989-05-01). 「パーティションによる完全グラフのカバー」.離散数学. 75 (1–3): 217–226. doi : 10.1016/0012-365x(89)90088-5 . ISSN 0012-365X.
- ^ Garey, M. R. ; Johnson, D. S. (1979)。Victor Klee (編)。コンピュータとイントラクタビリティ: NP完全性理論ガイド。数学科学シリーズ。サンフランシスコ、カリフォルニア州: W. H. Freeman and Co. pp. x+ 338。ISBN 0-7167-1045-5. MR 0519066.
- ^ Bannach, Max; Berndt, Sebastian; Maack, Marten; Mnich, Matthias; Lassota, Alexandra; Rau, Malin; Skambath, Malte (2020-07-06). 「Rainbow Matchings を使用した少数の小さなアイテムの梱包問題の解決」. arXiv : 2007.02660 [cs.DS].