D間隔ハイパーグラフ

D-interval_hypergraph
区間グラフ
と混同しないでください グラフ理論、D -intervalハイパーグラフは、の一種であるハイパーグラフ実数直線の間隔を使用して構築します。パラメータdは正の整数です。頂点のD -intervalハイパーグラフは、の点であるD互いに素線(従って非可算多くの頂点があります)。グラフのエッジは、間隔のdタプルであり、実数直線ごとに1つの間隔です。
最も単純なケースはd = 1です。1間隔のハイパーグラフの頂点セットは、実数のセットです。このようなハイパーグラフの各エッジは、実数直線の間隔です。たとえば、セット{、、}は、1間隔のハイパーグラフを定義します。区間グラフとの違いに注意して区間グラフでは、頂点は区間(有限集合)です。1間隔のハイパーグラフでは、頂点はすべて実数直線の点です(非可算集合)。
別の例として、2間隔のハイパーグラフでは、頂点セットは2つの実線の非交和であり、各エッジは2つの間隔の和集合です。1つは行#1に、もう1つは行#2に
次の2つの概念は、有限ハイパーグラフの場合と同様に、d間隔ハイパーグラフに対して定義されています。
マッチングは、非交差縁部、すなわち、非交差の組の集合であるDの-intervals。たとえば、1間隔のハイパーグラフ{、、}では、集合{、}はサイズ2のマッチングですが、セット{、}は、その要素が交差しているため、マッチングではありません。Hの最大一致サイズは、で示されます。 ν (( H ) { 画像注釈 nu(H)} 被覆又は横断はすべての交差する点のすべてのエッジ、すなわち、集合交差頂点の集合であり、D -intervalを。たとえば、1区間ハイパーグラフ{、、}では、セット{-1.5、4}はサイズ2のカバーですが、セット{ −1.5、1}は、エッジと交差しないため、カバーではありません。Hの最小横サイズはで示されます τ (( H ) { 画像注釈 tau(H)} ν
(( H) ≤ τ (( H ) { 画像注釈 nu(H) leq tau(H)}
ハイパーグラフHに当てはまります。
Tibor Gallaiは、1間隔のハイパーグラフで、それらが等しいことを証明しました。 ν (( H) = τ (( H ) { 画像注釈 nu(H)= tau(H)}
。これは、2部グラフのケーニヒの定理に類似しています。
Gabor Tardos は、2区間のハイパーグラフで、 τ (( H) ≤ 2 ν (( H ) { 画像注釈 tau(H) leq 2 nu(H)}
、およびそれはタイトです(つまり、サイズmが一致するすべての2間隔ハイパーグラフは、2 mのポイントでカバーできます)。
Kaiser は、d区間ハイパーグラフで、 τ (( H) ≤ d (( d− 1 ) ν (( H ) { 画像注釈 tau(H) leq d(d-1) nu(H)}
、さらに、サイズmに一致するすべてのd間隔ハイパーグラフは、各線のd(d  − 1)mポイント、(d  − 1)mポイントでカバーできます。
フリックとゼルビブは、この定理のカラフルな(「虹」)バージョンを証明しました。
参考文献
^ a b Tardos、Gábor(1995-03-01)。「2間隔の横断、トポロジー的アプローチ」。組み合わせ論。15(1):123–134。土井:10.1007 / bf01294464。ISSN  0209から9683まで。 ^ カイザー、T。(1997-09-01)。「d間隔の横断」。Discrete&ComputationalGeometry。18(2):195–203。土井:10.1007 / PL00009315。ISSN 1432から0444まで。   ^ フリック、フロリアン; ゼルビブ、シラ(2019-06-01)。「ポリトープのカラフルなカバーとカラフルなd間隔のピアス数」。組み合わせ論。39(3):627–637。arXiv:1710.07722。土井:10.1007 / s00493-018-3891-1。ISSN 1439から6912まで。  

投稿日:
カテゴリー: D