半分のグラフ

数学の一分野であるグラフ理論において、半グラフは特殊なタイプの二部グラフである。これらのグラフは、完全な二部グラフの辺の約半分が同じ頂点上にあるため、半グラフと呼ばれる。この名前は、ポール・エルデシュとアンドラーシュ・ハイナルによってこれらのグラフに付けられた。^[1]

頂点と上の半グラフを定義するには、を辺で接続します。^[1]${\displaystyle 2n}$${\displaystyle u_{1},\dots u_{n}}$${\displaystyle v_{1},\dots v_{n}}$${\displaystyle u_{i}}$${\displaystyle v_{j}}$${\displaystyle i\leq j}$

同じ概念は、任意の頂点の順序付き集合の2つのコピー上の無限グラフに対しても同様に定義できます。^[1]自然数上の半グラフ（通常の順序）は、各頂点が有限次数、最大 という特性を持ちます。二分割の反対側の頂点は無限次数です。^[2]${\displaystyle v_{j}}$${\displaystyle j}$

半グラフでは、2 つの頂点間の距離はそれぞれ 1、2、または 3 です。任意の 2 つの頂点と は、を通る経路を介して距離 2 にあり、任意の 2 つの頂点 とは、を通る経路を介して距離 2 にあります。二分グラフの反対側にある 2 つの頂点が隣接していない場合 (距離 1)、それらの頂点は、と の両方を通る経路を介して距離 3 にあります。半グラフは、二部連鎖グラフ (二分グラフの各側で、頂点を近傍包含によって順序付けることができる二部グラフ) の特殊なケースであり、二部連鎖グラフは、二部距離遺伝グラフの特殊なケースです。したがって、半グラフは距離遺伝的です。つまり、半グラフのすべての接続された誘導サブグラフでは、距離は半グラフ自体と同じです。^[3]${\displaystyle u_{i}}$${\displaystyle u_{j}}$${\displaystyle v_{n}}$${\displaystyle v_{i}}$${\displaystyle v_{j}}$${\displaystyle u_{1}}$${\displaystyle u_{1}}$${\displaystyle v_{n}}$

半グラフには唯一の完全マッチングがある。これは帰納法で簡単にわかる。 は唯一の隣接 とマッチングする必要があり、残りの頂点は別の半グラフを形成する。さらに強い言い方をすれば、唯一の完全マッチングを持つすべての二部グラフは半グラフのサブグラフである。^[4]${\displaystyle u_{n}}$${\displaystyle v_{n}}$

グラフの彩色数が非可算である場合、そのグラフには必然的に自然数上の半グラフがサブグラフとして含まれる。この半グラフには、二分法の片側が有限でもう一方が可算無限である完全な二部グラフがすべて含まれる。 ^[5]

半グラフの応用例の 1 つに、セメレディ正則性補題がある。これは、任意のグラフの頂点を、ほとんどの部分集合のペアが正則である (ペアを接続する辺が、特定の密度のランダム グラフのように特定の方法で動作する) ように、等しいサイズの部分集合の定数に分割できるというものである。半グラフがこのように部分集合に分割される場合、不規則なペアの数は少なくとも に比例する。したがって、すべてのペアが正則である分割の存在を示すために正則性補題を強化することは不可能である。^[6]一方、任意の整数 に対して、誘導部分グラフとして -頂点半グラフを持たないグラフは、不規則なペアを持たない正則性補題のより強力なバージョンに従う。^[7]${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle 2k}$

サハロン・シェラのモデル理論における不安定式定理は、安定理論（数少ない種類の完全理論）を可算無限半グラフの非存在によって特徴付ける。シェラは、理論のモデル、自由変数との有限組 2 つに関する式、およびこれらの変数に対する可算多数の値とシステムが存在し、そのペアが頂点と上の可算半グラフの辺を形成する場合、完全理論は順序特性を持つと定義する。直感的には、これらの半グラフの存在により、モデル内で無限の順序集合を構築できる。不安定式定理は、完全理論が安定であるためには、順序特性を持たないことが必要であると述べている。^[8]${\displaystyle M}$${\displaystyle \phi ({\bar {x}},{\bar {y}})}$${\displaystyle {\bar {x}}}$${\displaystyle {\bar {y}}}$${\displaystyle {\bar {x}}_{i}}$${\displaystyle {\bar {y}}_{i}}$${\displaystyle {\bigl \{}({\bar {x}}_{i},{\bar {y}}_{i})\mid M\models \phi ({\bar {x}}_{i},{\bar {y}}_{j}){\bigr \}}}$${\displaystyle {\bar {x}}_{i}}$${\displaystyle {\bar {y}}_{i}}$

指数時間仮説の一種によれば、半グラフのサイズによってパラメータ化された場合、より大きな二部グラフ内の与えられたサイズの半グラフを、サブグラフまたは誘導サブグラフとして見つけるための固定パラメータで扱いやすいアルゴリズムは存在しない。^[9]