二等辺三角形

離散幾何学において、二等辺集合とは、3 つの点が二等辺三角形を形成するという性質を持つ点の集合です。より正確には、3 つの点それぞれが最大で 2 つの距離を決定する必要があります。これにより、直線上の等間隔の 3 つの点によって形成される 退化した二等辺三角形も可能になります。

与えられた次元のユークリッド空間で最大の二等辺三角形を見つける問題は、1946 年にポール・エルデシュによって提起されました。エルデシュは、この問題の提起において、ユークリッド平面で最大の二等辺三角形には 6 つの点があることを指摘しました。^[1] 1947 年の解決法では、リロイ・ミルトン・ケリーが、唯一の 6 点平面二等辺三角形は正五角形の頂点と中心で構成されていることをより明確に示しました。3 次元では、ケリーは 8 点二等辺三角形を見つけました。そのうち 6 点は同一で、残りの 2 点は五角形の中心を通る垂直線上にあり、中心から五角形の頂点までの距離と同じ距離です。^[2]この 3 次元の例は、後に最適であることが証明され、唯一の最適解であることが証明されました。^{[3] [4]}

ケリーの 8 点 3 次元二等辺集合は、2 つの集合(五角形に垂直な線上の 3 点) と(五角形の 5 つの頂点) に分解でき、 の各点はのすべての点から等距離であるという性質があります。このような分解が可能な場合、任意の次元のユークリッド空間では、と は垂直な部分空間に存在する必要があり、 はその部分空間内の二等辺集合でなければならず、2 つの部分空間の交点の点を追加してから形成される集合も、その部分空間内の二等辺集合でなければなりません。このように、高次元の二等辺集合は、低次元の二等辺集合に分解できる場合があります。一方、二等辺集合にこのような分解がない場合は、二等辺集合であることよりも強い性質、つまり、すべての点のペアの間に 2 つの距離しかないという性質を持っている必要があります。^[5]${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y'}$${\displaystyle Y}$

この分解定理にもかかわらず、同じ次元内の最大二距離集合と最大二等辺集合のサイズが異なる可能性があります。これは、たとえば平面で発生します。最大二距離集合には 5 つの点 (正五角形の頂点) があり、最大二等辺集合には 6 つの点があります。この場合、6 点二等辺集合には分解があり、 は中心点の単一集合 (ゼロ次元の空間内) であり、残りのすべての点で構成されます。^[5]${\displaystyle X}$${\displaystyle Y}$

次元空間 では、二等辺集合は最大で 個の 点を持つことができる。^[5]これはと については厳密であるが、他の次元では必ずしもそうではない。次元二等辺集合における の点の最大数は個であることが知られている^[6]${\displaystyle d}$$${\displaystyle {\binom {d+2}{2}}}$$${\displaystyle d=6}$${\displaystyle d=8}$${\displaystyle d}$${\displaystyle d=1,2,\dots ,8}$

3、6、8、11、17、28、30、45（OEISの配列A175769）

しかし、これらの数値は高次元では知られていない。^[7]

リソネックは、点 を含む二距離集合の次の構成法を提供している 。これは、 点を含む二等辺集合も生成する。次元ユークリッド空間において、(に対して) が、 番目の座標軸に沿って原点から単位距離にあるベクトルを表すものとし、のすべての点からなる集合 を構築する。すると、 は座標和 を持つ点の 次元部分空間に存在し、その凸包は超単体である。 には 2 つの距離しかない。重なり合う単位ベクトルのペアの和から形成される 2 つの点の距離は であるのに対し、互いに素な単位ベクトルのペアから形成される 2 つの点の距離は である。の重心にもう 1 つの点を追加すると、次元二等辺集合が形成される。たとえば、 に対して、この構成は、最適な 8 点集合ではなく、正八面体の頂点と中心の 7 点からなる準最適な二等辺集合を生成する。^[6]$${\displaystyle {\binom {d+1}{2}}}$$$${\displaystyle {\binom {d+1}{2}}+1}$$${\displaystyle d+1}$${\displaystyle e_{i}}$${\displaystyle i=1,\dots ,d+1}$${\displaystyle i}$${\displaystyle S}$${\displaystyle e_{i}+e_{j}}$${\displaystyle i\neq j}$${\displaystyle S}$${\displaystyle d}$${\displaystyle 2}$ ${\displaystyle \Delta _{d+1,2}}$${\displaystyle {\sqrt {2}}}$${\displaystyle 2}$${\displaystyle S}$${\displaystyle d}$${\displaystyle d=3}$

同じ問題は他の距離空間についても考えることができる。例えば、ハミング空間では、同じ次元のユークリッド空間よりもやや小さい上限が知られている。^[7]超距離空間では、空間全体（およびその部分集合）は二等辺集合である。そのため、超距離空間は二等辺空間と呼ばれることもある。しかし、すべての二等辺集合が超距離であるわけではない。例えば、鈍角ユークリッド二等辺三角形は超距離ではない。^[8]