ヘリー一家

組合せ論において、位数kのヘリー族とは、交差が空であるすべての極小部分族にk個以下の集合が含まれる集合族のことである。同様に、すべてのk重交差が空でない有限部分族には、全交差が空でないことも含まれる。^[1] kヘリー特性とは、位数kのヘリー族であるという特性である。^[2]

k = 2の場合、これらの名前では数値kが省略されることがよくあります。したがって、集合族は、族内の任意のn個の集合に対して、であれば である場合、 Helly プロパティを持ちます。 ${\displaystyle s_{1},\ldots ,s_{n}}$${\displaystyle \forall i,j\in [n]:s_{i}\cap s_{j}\neq \emptyset }$${\displaystyle s_{1}\cap \cdots \cap s_{n}\neq \emptyset }$

これらの概念はエドゥアルト・ヘリー（1884-1943）にちなんで名付けられました。この概念を生み出したヘリーの凸集合に関する定理は、 n次元のユークリッド空間の凸集合はn + 1の位数のヘリー族であると述べています。^[1]

• 集合 { a , b , c , d } のすべての部分集合の族において、部分族 {{ a , b , c }, { a , b , d }, { a , c , d }, { b , c , d }} には空の交差がありますが、この部分族から任意の集合を削除すると、空でない交差を持つことになります。したがって、これは空の交差を持つ極小部分族です。これには 4 つの集合が含まれており、空の交差を持つ最大の極小部分族であるため、集合 { a , b , c , d } のすべての部分集合の族は、位数 4 の Helly 族です。
• I を、交差が空である実数直線の閉区間の有限集合とする。A を左端点aが可能な限り大きい区間とし、Bを右端点bが可能な限り小さい区間とする。すると、 aがb以下であれば、範囲 [ a , b ] 内のすべての数はIのすべての区間に属することになり、 Iの交差が空であるという仮定に反するため、 a  >  bでなければならない。したがって、2 つの区間のサブファミリー { A , B } には交差が空であり、 I  = { A , B } でない限り、ファミリーI は最小にはならない。したがって、交差が空である区間のすべての最小ファミリーには 2 つ以下の区間が含まれるため、すべての区間の集合は位数 2 の Helly ファミリーであることが示される。^[3]
• 整数の無限等差数列の族には2-ヘリー特性もある。つまり、有限の等差数列の集合に、互いに素な数列が2つ存在しないという特性がある場合、そのすべてに属する整数が存在する。これが中国剰余定理である。^[2]

より正式には、位数kのヘリー族は集合系( V , E )であり、 EはVの部分集合の集まりであり、任意の有限G⊆Eに対して 、

${\displaystyle \bigcap _{X\in G}X=\varnothing ,}$

H ⊆ G が次のように 成り立つことがわかる。

${\displaystyle \bigcap _{X\in H}X=\varnothing }$

そして

${\displaystyle \left|H\right|\leq k.}$^[1]

場合によっては、有限性に関係なく、すべての部分集合Gに対して同じ定義が当てはまります。ただし、これはより制限的な条件です。たとえば、実数直線の開区間は有限部分集合に対しては Helly 特性を満たしますが、無限部分集合に対しては満たしません。つまり、区間 (0,1/ i ) ( i = 0, 1, 2, ...) には、2 つの空でない交差がありますが、全体の交差は空です。

集合族が位数kのヘリー族である場合、その族はヘリー数 kを持つと言われる。距離空間のヘリー次元は、その空間内の計量球族のヘリー数より 1 小さい。ヘリーの定理は、ユークリッド空間のヘリー次元がその実ベクトル空間としての次元に等しいことを意味している。^[4]

多面体などのユークリッド空間の部分集合Sのヘリー次元は、Sの平行移動の族のヘリー数より1小さい。[ 5 ]たとえば^、超立方体のヘリー次元は1ですが、そのような形状ははるかに高い次元のユークリッド空間に属している可能性があります。^[6]

ヘリー次元は他の数学的対象にも適用されている。例えば、ドモコス（2007）は、群（可逆かつ結合的な二項演算によって形成される代数構造）のヘリー次元を、群の左剰余類族のヘリー数より1小さいものと定義している。^[7]

空でない集合の族が空の交差を持つ場合、そのヘリー数は少なくとも 2 でなければならないため、k-ヘリー特性が自明でない最小の k は k = 2 である。2-ヘリー特性はヘリー特性 とも呼ばれる。2-ヘリー族はヘリー族とも呼ばれる。^{[1] [2]}

閉じた球が 2-ヘリー特性（つまり、無限部分集合のヘリー次元のより強い変形である、ヘリー次元が 1 の空間）を持つ凸 距離空間は、単射または超凸と呼ばれます。^[8]タイトスパンの存在により、任意の距離空間をヘリー次元が 1 の空間に等長的に埋め込むことができます。^[9]

ハイパーグラフは集合族と同値である。ハイパーグラフの用語では、ハイパーグラフH = ( V , E )は、 E内の任意のn個のハイパーエッジに対して、 ならばとなる場合、ヘリー特性を持つ。^{[10] : 467}すべてのハイパーグラフ H に対して、以下は同値である: ^{[10] : 470–471}${\displaystyle e_{1},\ldots ,e_{n}}$${\displaystyle \forall i,j\in [n]:e_{i}\cap e_{j}\neq \emptyset }$${\displaystyle e_{1}\cap \cdots \cap e_{n}\neq \emptyset }$

• H はHelly 特性を持ち、Hの交差グラフ(頂点がEであり、 Eの 2 つの要素が交差する場合に限りリンクされる単純なグラフ) は完全グラフです。
• Hのすべての部分ハイパーグラフ(つまり、いくつかのハイパーエッジを削除することによってHから派生したハイパーグラフ) には、Konig プロパティ、つまり、最大マッチングサイズが最小横断サイズに等しいというプロパティがあります。
• Hのすべての部分ハイパーグラフには、その最大次数がその最小の辺色数に等しいという性質があります。