ハイパーグラフのパッキング

数学において、ハイパーグラフのパッキングとは、ハイパーグラフの辺の集合を、各部分集合内の辺のペアが頂点を共有しないような、互いに素な部分集合の数に分割することです。k一様ハイパーグラフで漸近的に最適なパッキングを達成するための有名なアルゴリズムが 2 つあります。1 つはJoel Spencerが提案したランダムグリーディ アルゴリズムです。彼は分岐プロセスを使用して、いくつかの副条件下での達成可能な最適境界を正式に証明しました。もう 1 つのアルゴリズムは Rödl ニブルと呼ばれ、 Vojtěch Rödlらが提案しました。彼らは、Rödl ニブルによって達成可能なパッキングが、ある意味でランダム グリーディ アルゴリズムのパッキングに近いことを示しました。

k一様ハイパーグラフ内のそのような部分集合の数を見つける問題は、もともと1963 年にポール・エルデシュとハイム・ハナニによる予想によって動機づけられました。1985 年にVojtěch Rödl は、特定の条件下で彼らの予想を漸近的に証明しました。1989 年に Pippenger とJoel Spencer は、ランダム貪欲アルゴリズムを使用して Rödl の結果を一般化しました。

以下の定義では、ハイパーグラフはH =( V , E )で表されます。Eのすべての辺がちょうどk 個の頂点で構成されている場合、Hはk均一ハイパーグラフと呼ばれます。

${\displaystyle P}$H 内の辺の部分集合であって、共通の頂点を持つ異なる辺のペアが存在しないとき、それ はハイパーグラフ パッキングである。

${\displaystyle H}$すべての および に対してが存在し、次の条件が両方とも満たされる とき、 は( , )-良好なハイパーグラフ${\displaystyle D_{0}}$${\displaystyle \epsilon }$です。${\displaystyle D_{0}}$${\displaystyle x,y\in V}$${\displaystyle D\geq D_{0}}$

${\displaystyle D(1-\epsilon )\leq {\text{deg}}(x)\leq D(1+\epsilon )}$

${\displaystyle {\text{codeg}}(x,y)\leq \epsilon D}$

ここで、頂点の次数 は、2 つの異なる頂点を含む辺の数であり、共次数は、両方の頂点を含む辺の数です。 ${\displaystyle {\text{deg}}(x)}$${\displaystyle x}$${\displaystyle x}$ ${\displaystyle {\text{codeg}}(x,y)}$${\displaystyle x}$${\displaystyle y}$

次の2つの条件の下で、-一様超グラフ に対して少なくともサイズPの漸近的パッキングが存在する。${\displaystyle {\frac {n}{K+1}}(1-o(1))}$${\displaystyle (K+1)}$

1. すべての頂点には、無限大に近づく次数があります。${\displaystyle D(1+o(1))}$${\displaystyle D}$
2. すべての頂点のペアは共通の辺のみを共有します。${\displaystyle o(D)}$

ここで、 は頂点の総数です。この結果はピッペンガーによって示され、後にジョエル・スペンサーによって証明されました。漸近的ハイパーグラフパッキング問題を解決するために、ジョエル・スペンサーはランダム貪欲アルゴリズムを提案しました。このアルゴリズムでは、分岐プロセスが基礎として使用され、上記の副次条件下ではほぼ常に漸近的に最適なパッキングを達成することが示されました。 ${\displaystyle n}$

k-均一ハイパーグラフの漸近的パッキングには、分岐プロセスによるランダム貪欲アルゴリズムと Rödl ニブルという 2 つの有名なアルゴリズムがあります。

すべてのエッジには、独立して一様に、異なる実数「誕生時刻」が割り当てられます。エッジは、誕生時刻の順に 1 つずつ選択されます。エッジは、以前に受け入れられたどのエッジとも重ならない場合、受け入れられ、 に含められます。明らかに、サブセットはパッキングであり、そのサイズはほぼ確実に であることが示されます。それを示すために、新しいエッジを追加するプロセスを の時点で停止するとします。任意の について、任意の-good ハイパーグラフについて、 となるように選択します。ここで、 は、時刻 までの頂点の生存確率( のどのエッジにも含まれていない場合、頂点は生存します)を表します。明らかに、このような状況では、時刻 での生存の期待数は未満です。その結果、未満である生存確率はよりも高くなります。言い換えると、 には少なくとも個の頂点が含まれている必要があり、これは であることを意味します。 ${\displaystyle E\in H}$${\displaystyle t_{E}\in [0,D]}$${\displaystyle E}$${\displaystyle P}$${\displaystyle P}$${\displaystyle |P|={\frac {n}{K+1}}}$${\displaystyle c}$${\displaystyle \gamma >0}$${\displaystyle c,D_{0},\epsilon }$${\displaystyle (D_{0},\epsilon )}$${\displaystyle f_{x,H}(c)<\gamma ^{2}}$${\displaystyle f_{x,H}(c)}$${\displaystyle x}$${\displaystyle P}$${\displaystyle c}$${\displaystyle x}$${\displaystyle c}$${\displaystyle \gamma^{2}n}$${\displaystyle x}$${\displaystyle \gamma n}$${\displaystyle 1-\gamma }$${\displaystyle P_{c}}$${\displaystyle (1-\gamma )n}$${\displaystyle |P|\geq (1-\gamma ){\frac {n}{K+1}}}$

証明を完了するには、 であることが示されなければなりません。そのためには、生存の漸近的動作を連続分岐プロセスによってモデル化します。 を固定し、誕生日が であるイブから始めます。時間が逆戻りし、単位密度ポアソン分布での区間でイブが出産すると仮定します。イブが出産する確率は です。 を条件とすることにより、出産時刻は上で独立かつ一様に分布します。イブによるすべての出産は、すべて同じ出産時刻、たとえば の子孫で構成されます。このプロセスは各子孫に対して繰り返されます。すべてに対してが存在し、よりも高い確率でイブには最大で 人の子孫がいることが示されます。 ${\displaystyle \lim _{c\rightarrow \infty }\lim _{x,H}f_{x,H}(c)=0}$${\displaystyle x}$${\displaystyle c>0}$${\displaystyle c}$${\displaystyle [0,c)}$${\displaystyle k}$${\displaystyle {\frac {e^{-c}c^{k}}{k!}}}$${\displaystyle k}$${\displaystyle x_{1},...,x_{k}}$${\displaystyle [0,c)}$${\displaystyle Q}$${\displaystyle a}$${\displaystyle \epsilon >0}$${\displaystyle K}$${\displaystyle (1-\epsilon )}$${\displaystyle K}$

親、子、ルート、出生順、同胞の概念を持つ根付きツリーは、親ツリーと呼ばれます。有限の親ツリーが与えられた場合、各頂点は生き残るか死ぬかを言います。子のいない頂点は生き残ります。頂点が死ぬのは、その頂点に少なくとも 1 つの子孫がいて、その子孫全員が生き残る場合のみです。上記のプロセスによって与えられた親ツリーでイブが生き残る確率を とします。目的は を示し、その後、任意の固定された に対して であることが示されます。これら 2 つの関係で議論は完了します。 ${\displaystyle T}$${\displaystyle f(c)}$${\displaystyle T}$${\displaystyle \lim _{c\rightarrow \infty }f(c)=0}$${\displaystyle c}$${\displaystyle \lim^{*}f_{x,H}(c)=f(c)}$

を示すために、 とします。 として小さいについて、おおよそ、時間に始まるイブは時間間隔で を出産し、その子供はすべて生き残りますが、 にはイブは出産せず、その子供はすべて生き残ります。 とすると、微分方程式が得られます。初期値によって一意の解が得られます。実際 であることに注意してください。 ${\displaystyle f(c)=0}$${\displaystyle c\geq 0,\Delta c>0}$${\displaystyle \Delta c}$${\displaystyle f(c+\Delta c)-f(c)\approx -(\Delta c)f(c)^{Q+1}}$${\displaystyle c+\Delta c}$${\displaystyle [c,c+\Delta c)}$${\displaystyle [0,c)}$${\displaystyle \Delta c\rightarrow 0}$${\displaystyle f'(c)=-f(c)^{Q+1}}$${\displaystyle f(0)=1}$${\displaystyle f(c)=(1+Qc)^{-1/Q}}$${\displaystyle \lim _{c\rightarrow \infty }f(c)=0}$

を証明するために、中止するかブロードツリーを生成する History という手順を考えます。History には、最初は の頂点の集合が含まれています。は、ルートを含むブロードツリー構造を持ちます。は、処理済みか未処理かのいずれかであり、最初は未処理です。それぞれに誕生時刻が割り当てられ、 を初期化します。History は、未処理の を取り、次のように処理します。 を持つが はすでに処理されていない のすべての の値について、一部にとがあるか、一部にとがある場合、History は中止されます。それ以外の場合、 を持つ各 について、すべてを に、親と共通の誕生日を持つ wombmates として追加します。これで は処理済みとみなされます。中止されない場合は、すべてが処理されたときに History は停止します。History が中止されない場合、ルートがブロードツリーで生き残るのは、 が時刻 で生き残る場合のみです。固定されたブロードツリーについて、が分岐プロセスでブロードツリー が生成される確率を表すものとします。この場合、History が中止されない確率は です。分岐過程の有限性により、すべての親木と履歴の合計は中止されません。その親木の分布は分岐過程の分布に近づきます。したがって。 ${\displaystyle \lim^{*}f_{x,H}(c)=f(c)}$${\displaystyle T}$${\displaystyle T=\{x\}}$${\displaystyle T}$${\displaystyle x}$${\displaystyle y\in T}$${\displaystyle x}$${\displaystyle y\in T}$${\displaystyle t_{y}}$${\displaystyle t_{x}=c}$${\displaystyle y\in T}$${\displaystyle t_{E}}$${\displaystyle y\in E}$${\displaystyle x\in E}$${\displaystyle E}$${\displaystyle t_{E}<t_{y}}$${\displaystyle y,z\in E}$${\displaystyle z\in T}$${\displaystyle E,E'}$${\displaystyle t_{E},t_{E'}<t_{y}}$${\displaystyle y\in E,E'}$${\displaystyle |E\cup E'|>1}$${\displaystyle E}$${\displaystyle t_{E}<t_{y}}$${\displaystyle z\in E-\{y\}}$${\displaystyle T}$${\displaystyle y}$${\displaystyle t_{E}}$${\displaystyle y}$${\displaystyle y\in T}$${\displaystyle x}$${\displaystyle T}$${\displaystyle x}$${\displaystyle c}$${\displaystyle f(T,c)}$${\displaystyle T}$${\displaystyle f(T,c)}$${\displaystyle \sum f(T,c)=1}$${\displaystyle T}$${\displaystyle lim^{*}}$${\displaystyle \lim ^{*}f_{x,H}(c)=f(c)}$

1985年、ロードルはポール・エルデシュの予想をロードル・ニブルと呼ばれる方法で証明した。ロードルの結果は、パッキング問題または被覆問題のどちらかの形で定式化できる。で表される被覆数は、すべての- 元集合が少なくとも1つの に含まれるという性質を持つ- 元部分集合の族の最小サイズを示す。ポール・エルデシュらの予想は ${\displaystyle 2\leq l<k<n}$${\displaystyle M(n,k,l)}$${\displaystyle \kappa }$${\displaystyle k}$${\displaystyle \{1,...,n\}}$${\displaystyle l}$${\displaystyle A\in \kappa }$

${\displaystyle \lim _{n\rightarrow \infty }{\frac {M(n,k,l)}{{n \choose l}/{k \choose l}}}=1}$。

ここで、 です。この予想は、大まかに言って、戦術的構成が漸近的に達成可能であることを意味します。同様に、パッキング数を、すべての要素セットが最大で 1 つの に含まれるという特性を持つの 要素サブセットの族の最大サイズとして定義することもできます。 ${\displaystyle 2\leq l<k}$${\displaystyle m(n,k,l)}$${\displaystyle \kappa }$${\displaystyle k}$${\displaystyle \{1,...,n\}}$${\displaystyle l}$${\displaystyle A\in \kappa }$

1997 年には、Noga Alon、Jeong Han Kim、Joel Spencerも、より強いコード度条件の下で、すべての異なるペアが最大で 1 つのエッジを共有するという 優れた境界を示しました。${\displaystyle \gamma }$${\displaystyle v,v'\in V}$

n頂点のk一様、D正則ハイパーグラフについて、k > 3 であれば、最大 を除くすべての頂点をカバーするパッキングPが存在します。k = 3 であれば、最大 を除くすべての頂点をカバーするパッキング P が存在します。 ${\displaystyle O(nD^{-1/(k-1)})}$${\displaystyle O(nD^{-1/2}\ln ^{3/2}D)}$

この境界は、シュタイナー三重システムなどのさまざまなアプリケーションで望ましいものです。シュタイナー三重システムは、すべての頂点のペアが正確に 1 つのエッジに含まれる 3 均一の単純なハイパーグラフです。シュタイナー三重システムは明らかにd =( n -1)/2 正則であるため、上記の境界により、次の漸近的な改善が実現されます。

n頂点上の任意のシュタイナー三重系には、最大 を除くすべての頂点をカバーするパッキングが含まれます。 ${\displaystyle O(n^{1/2}\ln ^{3/2}n)}$

これはその後^[1]と^{[2]に改善されました。}${\displaystyle n/3-O({\frac {\log n}{\log \log n}})}$${\displaystyle {\frac {n-4}{3}}}$

• 分岐プロセス
• 独立集合
• グラフの色付け
• カバー番号
• セット梱包
• ラムゼーの定理
• セットカバーの問題
• 球詰め
• シュタイナーシステム