ライザーの推測

グラフ理論において、ライザー予想は、ハイパーグラフの最大マッチングサイズと最小横断サイズに関する予想である。

この予想は、ハーバート・ジョン・ライザーが指導教官であったJR・ヘンダーソンの博士論文の中で1971年に初めて登場した。^[1]

ハイパーグラフ内のマッチングは、各頂点が最大で 1 つのハイパーエッジにしか現れないようなハイパーエッジの集合です。ハイパーグラフH内のマッチングの最大サイズは で表されます。 ${\displaystyle \nu (H)}$

ハイパーグラフの横断線（または頂点カバー）は、各ハイパーエッジに少なくとも 1 つの頂点が含まれるような頂点の集合です。ハイパーグラフHの横断線の最小サイズは で表されます。 ${\displaystyle \tau (H)}$

あらゆるHについて、あらゆるカバーには、あらゆるマッチングにおける各エッジからの少なくとも 1 つの点が含まれている必要があるため、 ${\displaystyle \nu (H)\leq \tau (H)}$

H がr一様 (各ハイパーエッジにちょうどr 個の頂点がある) である場合、任意の最大マッチングからのエッジの和集合は、すべてのエッジと一致する最大rv個の頂点の集合であるため、となります。 ${\displaystyle \tau (H)\leq r\cdot \nu (H)}$

ライザーの予想は、H がr一様であるだけでなくr 部構成である（つまり、その頂点をr個の集合に分割でき、各辺に各集合の要素が 1 つずつ含まれる）場合、次のようになるというものです。

${\displaystyle \tau (H)\leq (r-1)\cdot \nu (H)}$

つまり、上記の不等式の乗数は1だけ減少する可能性がある。^[2]

ライザーの予想に対する極限ハイパーグラフとは、予想が等式で成り立つハイパーグラフ、つまり です。このようなハイパーグラフの存在は、係数r -1 が可能な限り最小であることを示しています。 ${\displaystyle \tau (H)=(r-1)\cdot \nu (H)}$

極値ハイパーグラフの例としては、切断された射影平面（頂点とそれを含むすべての直線が削除されたr -1次の射影平面）がある。 ^[3] r -1が素数のべき乗である ときはいつでも、切断された射影平面が存在することが知られている。

このような極値ハイパーグラフには他のファミリーも存在する。^[4]

r =2の場合、ハイパーグラフは二部グラフとなり、予想は となる。これはケーニッヒの定理によって真であることが知られている。 ${\displaystyle \tau (H)\leq \nu (H)}$

r =3の場合、この予想はロン・アハロニによって証明されている。^[5]この証明では、ハイパーグラフのマッチングに アハロニ-ハクセル定理が用いられる。

r =4とr =5 の場合、ペニー・ハクセルとスコットによって次の弱いバージョンが証明されている。 ^[6] ε > 0が存在し、

${\displaystyle \tau (H)\leq (r-\varepsilon )\cdot \nu (H)}$。

さらに、 r =4 およびr =5の場合、Ryser の予想は特別なケースで Tuza (1978) によって証明されています。${\displaystyle \nu (H)=1}$

${\displaystyle \nu (H)=1\implies \tau (H)\leq r-1}$。

ハイパーグラフにおける分数マッチングとは、各ハイパーエッジに重みを割り当て、各頂点付近の重みの合計が最大で 1 になるようにすることです。ハイパーグラフHにおける分数マッチングの最大サイズは で表されます。 ${\displaystyle \nu ^{*}(H)}$

ハイパーグラフの分数横断とは、各ハイパーエッジの重みの合計が少なくとも 1 になるように各頂点に重みを割り当てることです。ハイパーグラフHの分数横断の最小サイズは で表されます。線形計画法の双対性は であることを意味します。 ${\displaystyle \tau ^{*}(H)}$${\displaystyle \nu ^{*}(H)=\tau ^{*}(H)}$

フーレディは、ライザー予想の分数版を次のように証明した。Hがr部かつr正則（各頂点がちょうどr個の超辺に現れる）である場合、^[7]

${\displaystyle \tau ^{*}(H)\leq (r-1)\cdot \nu (H)}$。

ロヴァスは^[8]

${\displaystyle \tau (H)\leq {\frac {r}{2}}\cdot \nu ^{*}(H)}$。