虹独立集合

グラフ理論において、レインボー独立集合( ISR ) は、グラフ内の各頂点が異なる色を持つ独立集合です。

形式的には、 $G = (V, E)$ をグラフとし、頂点集合 $V が「色」と呼ばれる$ $m$ 個の部分集合 $V$ $1$ $, \dots,$ $V$ $m$ に分割されているとする。頂点集合 $U$ は、次の条件を両方とも満たす場合、レインボー独立集合と呼ばれる: ^[1]

これは独立した集合です $。U$ 内のすべての 2 つの頂点は隣接していません (頂点間に辺はありません)。
これはレインボーセットです。Uには $、$ $各色V$ $i$ から最大で 1 つの頂点が含まれます。

文献で使用されている他の用語としては、独立した代表者集合^[2] 、独立した横断的^[3]、独立した代表者システム^[4]などがある。

応用例として、 $m$ 個の学部を持つ学部を考えてみましょう。学部には、互いに嫌い合っている教員がいます。学部長は、学部ごとに 1 名ずつ、ただし互いに嫌い合っている教員ペアは含めない、 $m名のメンバーで構成される委員会を編成したいと考えています。この問題は、ノードが教員、エッジが「嫌い」関係、サブセット$ $V 1 、\dots、 V m$ が学部であるグラフで ISR を見つけることとして表すことができます。^[3]

バリエーション

$便宜上、集合V 1, \dots, V m は$ 互いに素であると仮定する。一般に集合は交差することがあるが、この場合は素集合の場合に簡単に帰着できる。すなわち、すべての頂点 $x$ について、各 $iに対して$ $x$ のコピーを形成し、 $V$ $i が$ $x を$ 含むようにする。結果として得られるグラフでは、 $x$ のすべてのコピーを互いに接続します。新しいグラフでは、 $V$ $i は$ 互いに素であり、各 ISR は元のグラフの ISR に対応する。^[4]

ISR は、個別代表システム(SDR、横断的とも呼ばれる)の概念を一般化します。すべての横断は ISR であり、基礎となるグラフでは、異なるセットからの同じ頂点のすべてのコピーのみが接続されます。

虹独立集合の存在

ISR が存在するにはさまざまな十分条件があります。

頂点次数に基づく条件

直感的に、学部 $V i$ が大きく、教員間の対立が少ない場合、ISR が存在する可能性が高くなるはずです。「対立が少ない」条件は、グラフの頂点次数によって表されます。これは次の定理によって形式化されます: ^[5]^{: Thm.2}

$G$ 内のすべての頂点の次数が最大 $d$ であり、各カラーセットのサイズが少なくとも $2 d$ である場合、 $G$ にはISR があります。

2 $d$ が最良です。頂点次数が $k で$ 、サイズが 2 d – 1 の色 $を$ $持つ$ $グラフ$ $が$ ISR なしで存在します。^{[6]しかし、境界が} $d$ と $m$ の両方に依存するより正確なバージョンもあります。^[7]

支配集合に基づく条件

以下では、色の部分集合 $S （$ ${V 1, ..., V m}$ の部分集合）が与えられたとき、 $S$ 内のすべての部分集合（色が $S$ 内のいずれかの色であるすべての頂点）の和集合を $U S$ で表し、 $U$ $S$ によって誘導される $G$ の部分グラフを $G$ $S$ で表す。^[8]次の定理は、 ISR を持たないが、任意の辺を削除すると、残りのグラフに ISR が存在するという意味で辺が最小であるグラフの構造を記述する。

$G$ に ISR がないが、 E のすべての辺 e に対してGe $に$ ISR $が$ $ある$ 場合、 E のすべての辺 e = ( x , y ) に対して、 $色$ の $サブセット$ $S$ ${$ $V$ $1$ $,$ … , $V$ $m$ $}$ $と$ $、$ $G$ $S$ $の$ $辺$ $の$ 集合Z $が$ 存在し、次のようになります。
頂点 $x$ と $y は両方とも$ $U S$ 内にあります。

辺 $e = (x, y)は$ $Z$ にあります。

$Z$ に隣接する頂点の集合は $G$ $S を$ 支配します 。

$| Z | \leq | S | - 1$ ;

$Z は$ マッチングしており、その 2 つの辺は同じ頂点に隣接していません。

ホール型条件

以下では、色の部分集合 $S ($ ${V 1, \dots, V m}$ の部分集合) が与えられたとき、 $G$ $S$ の独立集合 $I Sが$ $S$ に対して特殊であるとは、最大で $|$ $S$ $| - 1 の$ 大きさの $G$ $S$ の頂点の独立部分集合 $Jごとに、$ $J$ $\cup {$ $v$ $}$ も独立であるような $I$ $S$ 内の $v が$ 存在する場合を言う。比喩的に言えば、 $I$ $S$ $は部門の集合S$ に対する「中立メンバー」のチームであり、十分に小さい衝突しないメンバーの集合を拡張して、より大きな集合を作成することができる。次の定理は、ホールの結婚定理に類似している: ^[9]

色のすべての部分集合 S に対して、グラフ $G S に$ $S$ に対して特別な独立集合 $I S が$ 含まれる場合、 $G$ には ISR が存在します。証明のアイデア。定理はスペルナーの補題を使用して証明されます。^[3]^{: Thm.4.2} $m$ 個の端点を持つ標準単体には、いくつかの特別な特性を持つ三角形分割が割り当てられます。単体の各端点 $i は$ 色集合 $V$ $i$ に関連付けられ、単体の各面 ${$ $i$ $1$ $, \dots,$ $i$ $k$ $}$ は色の集合 $S$ $= {$ $V$ $i$ $1$ $, \dots,$ $V$ $ik$ $}$ に関連付けられます。三角形分割の各点 $x には、$ $G$ の頂点 $g$ $($ $x$ $)$ というラベルが付けられ、次のようになります。(a)面 $S上の各点$ $x$ について、 $g$ $($ $x$ $) は$ $I$ $S$ $( S$ の特別な独立集合)の要素です。 (b)三角形分割の1 スケルトンで点 $x$ と $y$ が隣接している場合、 $g$ $($ $x$ $)$ と $g$ $($ $y$ $)は$ $G$ では隣接しません。スペルナーの補題により、各点 $x$ に対して $g$ $($ $x$ $) が$ 異なる色集合に属する部分単体が存在し、これらの $g$ $($ $x$ $)$ の集合はISR です。

上記の定理は、ホールの結婚条件を意味します。これを確認するには、 $G が$ 他のグラフ $Hの$ 線グラフである特別な場合の定理を述べると便利です。これは、 $Gのすべての頂点が$ $H$ の辺であり、 $Gのすべての独立集合が$ $H$ のマッチングであることを意味します。 $G$ の頂点カラーリングは $H$ の辺カラーリングに対応し、 $G$ のレインボー独立集合は $H$ のレインボーマッチングに対応します。 $H$ $S$ のマッチング $I$ $S$ $がS$ にとって特別であるためには、サイズが最大で $|$ $S$ $| - 1である$ $H$ $S$ のすべてのマッチング $Jに対して、$ $I$ $S$ に辺 $eが存在し、$ $J$ $\cup {$ $e$ $}が依然として$ $H$ $S$ のマッチングである場合です。

$H を$ 辺色付けされたグラフとします。色のすべての部分集合 S に対して、 $グラフ$ H $S に$ $S$ に特別なマッチング $M S が$ 含まれる場合、 $H$ にはレインボーマッチングが存在します。

$H = (X + Y, E)$ をホールの条件を満たす二部グラフとする。 $X$ の各頂点 $iに対して、$ $i$ に隣接する $H$ のすべての辺に一意の色 $V$ $i を$ $割り当てる。色のすべてのサブセットS$ に対して、ホールの条件は $S が$ $Y$ に少なくとも $|$ $S$ $| 個の隣接頂点を持つことを意味するため、$ $H$ の辺のうち $Y$ の異なる頂点に隣接するものが少なくとも $|$ $S$ $|$ 個ある。I $S を$ $その$ ような辺の集合 $|$ $S$ $|とする。$ $H$ における最大 $|$ $S$ $| - 1$ のサイズの任意のマッチング $Jに対して、$ $I$ $S$ の何らかの要素 $e は$ $Yにおいて$ $J$ のすべての要素とは異なるエンドポイントを持つため、 $J$ $\cup {$ $e$ $}$ もマッチングとなり、 $I$ $S は$ $S$ に対して特別となる。上記の定理は、 $H に$ レインボーマッチング $M$ $R を$ 持つことを意味する。色の定義により、 $M$ $R は$ $H$ における完全マッチングである。

上記の定理のもう一つの系は、頂点次数と周期長の両方を含む次の条件である: ^[3]^{: Thm.4.3}

$G$ のすべての頂点の次数が最大で 2 であり、 $G$ の各サイクルの長さが 3 で割り切れ、各カラーセットのサイズが少なくとも 3 である場合、 $G に$ はISR が存在します。証明。色のすべてのサブセット $S$ について、グラフ $G$ $S$ には少なくとも $3|$ $S$ $| の$ 頂点が含まれ、長さが 3 で割り切れるサイクルとパスの和集合です。I $S を$ 、各サイクルと各パスの 3 つおきの頂点を含む $G$ $S$ の独立セットとします。したがって、 $|$ $I$ $S$ $|$ には少なくとも $3|$ $S$ $|$ $⁄$ $3$ $= |$ $S$ $|の頂点$ $が$ 含まれます。J $を$ 、サイズが最大で $|$ $S$ $| - 1の$ $G$ $S$ の独立セットとします。I $S$ の各 2 つの頂点間の距離は少なくとも 3 であるため $、$ J のすべての頂点は $I$ $S$ $の$ 最大で 1 つの頂点に隣接します。したがって、 $J$ のどの頂点にも隣接しない $I$ $S$ の頂点が少なくとも 1 つあります。したがって、 $I$ $S は$ $S$ に対して特別です。前の定理により、 $G に$ は ISR があります。

$.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}$

相同接続に基づく条件

条件の 1 つのファミリーは、サブグラフの独立複合体のホモロジー接続に基づいています。条件を記述するには、次の表記法が使用されます。

$Ind(G)は$ グラフ $Gの$ 独立複体（つまり、 $G$ 内の独立集合を面とする抽象単体複体）を表す。
$η H (X) は$ 、単体複体 $Xの$ ホモロジー接続性(つまり、 $X$ の最初の $k 個の$ ホモロジー群最大の整数 $k$ ) に 2 を加えた値を表します。
$[m] は$ 色のインデックスの集合 ${1, \dots, n} です。$ $[$ $m$ $]$ の任意の部分集合 $J$ について、 $V$ $J は$ $J$ 内の $J$ の色 $V$ $J$ の和集合です。
$G [V J] は$ $V$ $J$ の頂点によって誘導される $G$ のサブグラフです。

以下の条件は^{[9]では暗黙的に示されており、}^[10]では明示的に証明されている。

$[$ $m$ $]$ のすべての部分集合 $J$ について、
$\eta _{H}({\text{Ind}}(G[V_{J}]))\geq |J|$
パーティション $V 1 、\dots、 V m は$ ISRを許可します。

例として、^[4] $Gが$ 二部グラフで、その部分が $V 1$ と $V 2$ であるとします。この場合、 $[m] = {1,2}なので、$ $J$ には4つの選択肢があります。

$J = {}:$ すると $G [J] = {}$ かつ $Ind(G [J]) = {}$ となり、接続性は無限大となるため、条件は自明に成り立ちます。
$J = {1}:$ すると、 $G [J]は頂点$ $V 1$ を持ち、辺を持たないグラフになります $。ここで、すべての頂点集合は独立しているので、 Ind(G [J])は$ $V 1$ の冪集合です $。つまり、単一のn$ 単体 (およびそのすべての部分集合)を持ちますすべての整数 $kに対して$ $k$ 連結であることが知られています(単体ホモロジーを参照)。したがって、条件は成り立ちます。
$J = {2}:$ このケースは前のケースと類似しています。
$J = {1,2} の場合、$ $G [J] = G$ であり、 $Ind(G)$ には2 つの単体 $V 1$ と $V 2$ (およびそれらのすべての部分集合) が含まれます。条件 $η H (Ind(G)) \geq 2は、$ $Ind(G)$ のホモロジー接続性が少なくとも 0 であるという条件に相当し自明群であるという条件に相当します $。これは、複体Ind($ $G$ $)に 2 つの単体$ $V$ $1$ と $V$ $2$ の間の接続が含まれる $場合に限り成立します。このような接続は、1 つの頂点がV$ $1から、もう 1 つの頂点が$ $V$ $2$ からある独立集合に相当します。したがって、この場合、定理の条件は十分であるだけでなく、必要でもあります。 ${\チルダ {H_{0}}}({\text{Ind}}(G))$

その他の条件

彩色数 $x$ の適切に色付けされた三角形のないグラフには、少なくとも $x$ $⁄$ $2$ の大きさの虹独立集合が含まれます。^[11]

数多くの著者が、様々なグラフのクラスにおける大きなレインボー独立集合の存在条件を研究してきた。^[1]^[12]

計算

ISR決定問題は、与えられたグラフ $G = (V, E)と、与えられた$ $Vの$ $m$ 色への分割がレインボー独立集合を許容するかどうかを決定する問題です。この問題はNP 完全です。証明は、3 次元マッチング問題 (3DM) からの還元により行われます。^[4] 3DM への入力は、3 部ハイパーグラフ $(X + Y + Z 、 F)$ です。ここで、 $X$ 、 $Y$ 、 $Z は、サイズ$ $m$ の頂点集合であり、 $Fは、$ $X$ 、 $Y$ 、 $Z$ のそれぞれの頂点を 1 つずつ含む 3 つ組の集合です。3DM への入力は、次のように ISR への入力に変換できます。

$F$ の各辺 $(x, y, z)に対して、$ $V$ には頂点 $v$ $x,y,z$ が存在します。
$Z$ の各頂点 $z$ について、 $V$ $z$ $= {$ $v$ $x,y,z$ $|$ $x$ $\in$ $X$ $,$ $y$ $\in$ $Y$ $} とします。$
各 $x$ 、 $y 1$ 、 $y 2$ 、 $z 1$ 、 $z 2$ $に対して、 E$ には辺 $(v x 、 y 1 、 z 1 、 v x 、 y 2 、 z 2)$ が存在します。
各 $x 1$ 、 $x 2$ 、 $y$ 、 $z 1$ 、 $z 2$ $に対して、 E$ に辺 $(v x 1 、 y 、 z 1 、 v x 2 、 y 、 z 2)$ が存在します。

結果として得られるグラフ $G = (V, E)では、 ISR は次のような 3 つの要素$ $(x, y, z)$ の集合に対応します。

各トリプレットは異なる $z$ 値を持ちます (各トリプレットは異なるカラーセット $V z$ に属しているため)。
各トリプレットには異なる $x$ 値と異なる $y$ 値があります (頂点は独立しているため)。

したがって、結果のグラフは、元のハイパーグラフが 3DM を許可する場合にのみ、ISR を許可します。

別の証明はSATからの還元によるものである。^[3]

参照

参考文献

^ ab Aharoni, Ron; Briggs, Joseph; Kim, Jinha; Kim, Minki (2019-09-28). 「特定のグラフクラスにおけるレインボー独立集合」. arXiv : 1909.13143 [math.CO].
^ アハロニ、ロン;バーガー、イーライ。コトラー、ダニ。ジヴ、ラン (2017-10-01)。「スタインの推測について」。ハンブルク大学アブハンドルゲン数学セミナー。87 (2): 203–211。土井：10.1007/s12188-016-0160-3。ISSN 1865-8784。S2CID 119139740。
^ abcdef Haxell, P. (2011-11-01). 「委員会の設立について」.アメリカ数学月刊誌. 118 (9): 777–788. doi :10.4169/amer.math.monthly.118.09.777. ISSN 0002-9890. S2CID 27202372.
^ abcd アハロニ、ロン;バーガー、イーライ。ジヴ、ラン (2007-05-01)。「加重グラフにおける代表者の独立したシステム」。コンビナトリカ。27 (3): 253–267。土井：10.1007/s00493-007-2086-y。ISSN 1439-6912。S2CID 43510417。
^ E, HaxellP (2001-07-01). 「頂点リストカラーリングに関する注記」.組合せ論、確率および計算. 10 (4): 345–347. doi :10.1017/s0963548301004758. S2CID 123033316.
^ Szabó*, Tibor; Tardos†, Gábor (2006-06-01). 「有界次数グラフの横断に関する極値問題」. Combinatorica . 26 (3): 333–351. doi :10.1007/s00493-006-0019-9. hdl : 20.500.11850/24692 . ISSN 1439-6912. S2CID 15413015.
^ Haxell, Penny; Szabó, Tibor (2006-01-01). 「奇数の独立横断は奇数である」.組合せ論、確率、計算. 15 (1–2): 193–211. doi :10.1017/S0963548305007157 (2024年11月1日非アクティブ). ISSN 1469-2163. S2CID 6067931.{{cite journal}}: CS1 maint: DOI inactive as of November 2024 (link)
^ Berke, Robert; Haxell, Penny; Szabó, Tibor (2012). 「多部グラフの有界横断」. Journal of Graph Theory . 70 (3): 318–331. doi :10.1002/jgt.20618. ISSN 1097-0118. S2CID 17608344.
^ ab Aharoni, Ron; Haxell, Penny (2000). 「ハイパーグラフのホールの定理」. Journal of Graph Theory . 35 (2): 83–88. doi :10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V. ISSN 1097-0118.
^ ab Meshulam, Roy (2001-01-01). 「クリーク複合体とハイパーグラフマッチング」. Combinatorica . 21 (1): 89–94. doi :10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.
^ アラビンド、NR;カンビー、スタイン。ファン・バテンブルク、ウーター・カムス。ド・ヴェルクロ、レミ・ド・ジョアニス。カン、ロス J.パテル、ヴィレシュ (2020-03-15)。「三角形のないグラフの構造と色」。arXiv : 1912.13328 [math.CO]。
^ Kim, Jinha; Kim, Minki; Kwon, O.-joung (2020-02-05). 「密なグラフクラス上のレインボー独立集合」. arXiv : 2001.10566 [math.CO].
^ ロン、アハロニ;ブリッグス、ジョセフ。ロン、ホルツマン。江、紫林（2021）。「レインボー・オッド・サイクル」。離散数学に関する SIAM ジャーナル。35 (4): 2293–2303。arXiv : 2007.09719。土井：10.1137/20M1380557。S2CID 220647170。

[:0-1] Aharoni, Ron; Briggs, Joseph; Kim, Jinha; Kim, Minki (2019-09-28). 「特定のグラフクラスにおけるレインボー独立集合」. arXiv : 1909.13143 [math.CO].

[2] アハロニ、ロン;バーガー、イーライ。コトラー、ダニ。ジヴ、ラン (2017-10-01)。「スタインの推測について」。ハンブルク大学アブハンドルゲン数学セミナー。87 (2): 203–211。土井：10.1007/s12188-016-0160-3。ISSN 1865-8784。S2CID 119139740。

[:2-3] Haxell, P. (2011-11-01). 「委員会の設立について」.アメリカ数学月刊誌. 118 (9): 777–788. doi :10.4169/amer.math.monthly.118.09.777. ISSN 0002-9890. S2CID 27202372.

[:1-4] アハロニ、ロン;バーガー、イーライ。ジヴ、ラン (2007-05-01)。「加重グラフにおける代表者の独立したシステム」。コンビナトリカ。27 (3): 253–267。土井：10.1007/s00493-007-2086-y。ISSN 1439-6912。S2CID 43510417。

[5] E, HaxellP (2001-07-01). 「頂点リストカラーリングに関する注記」.組合せ論、確率および計算. 10 (4): 345–347. doi :10.1017/s0963548301004758. S2CID 123033316.

[6] Szabó*, Tibor; Tardos†, Gábor (2006-06-01). 「有界次数グラフの横断に関する極値問題」. Combinatorica . 26 (3): 333–351. doi :10.1007/s00493-006-0019-9. hdl : 20.500.11850/24692 . ISSN 1439-6912. S2CID 15413015.

[7] Haxell, Penny; Szabó, Tibor (2006-01-01). 「奇数の独立横断は奇数である」.組合せ論、確率、計算. 15 (1–2): 193–211. doi :10.1017/S0963548305007157 (2024年11月1日非アクティブ). ISSN 1469-2163. S2CID 6067931.{{cite journal}}: CS1 maint: DOI inactive as of November 2024 (link)

[8] Berke, Robert; Haxell, Penny; Szabó, Tibor (2012). 「多部グラフの有界横断」. Journal of Graph Theory . 70 (3): 318–331. doi :10.1002/jgt.20618. ISSN 1097-0118. S2CID 17608344.

[:4-9] Aharoni, Ron; Haxell, Penny (2000). 「ハイパーグラフのホールの定理」. Journal of Graph Theory . 35 (2): 83–88. doi :10.1002/1097-0118(200010)35:2<83::AID-JGT2>3.0.CO;2-V. ISSN 1097-0118.

[:3-10] Meshulam, Roy (2001-01-01). 「クリーク複合体とハイパーグラフマッチング」. Combinatorica . 21 (1): 89–94. doi :10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.

[11] アラビンド、NR;カンビー、スタイン。ファン・バテンブルク、ウーター・カムス。ド・ヴェルクロ、レミ・ド・ジョアニス。カン、ロス J.パテル、ヴィレシュ (2020-03-15)。「三角形のないグラフの構造と色」。arXiv : 1912.13328 [math.CO]。

[12] Kim, Jinha; Kim, Minki; Kwon, O.-joung (2020-02-05). 「密なグラフクラス上のレインボー独立集合」. arXiv : 2001.10566 [math.CO].

[13] ロン、アハロニ;ブリッグス、ジョセフ。ロン、ホルツマン。江、紫林（2021）。「レインボー・オッド・サイクル」。離散数学に関する SIAM ジャーナル。35 (4): 2293–2303。arXiv : 2007.09719。土井：10.1137/20M1380557。S2CID 220647170。