第二の近隣問題

数学において、第二近傍問題は、ポール・シーモアが提起した有向グラフに関する未解決の問題である。直感的には、そのようなグラフで記述されるソーシャルネットワークでは、少なくとも友人の数と同じ数の友人の友人がいることを示唆している。^{[1] [2]}

この問題は第二近傍予想、あるいはシーモアの距離2予想としても知られている。^{[1] [3]}

有向グラフは、単純な無向グラフの各辺に向きを割り当てることによって得られる有限の有向グラフです。同様に、自己ループ、平行辺、2 辺循環を持たない有向グラフです。頂点の最初の近傍 (開近傍とも呼ばれる) は、 から距離1にあるすべての頂点で構成され、 の 2 番目の近傍は、から距離 2 にあるすべての頂点で構成されます。これら 2 つの近傍は互いに素な集合を形成し、どちらにもそれ自体は含まれません。 ${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$

1990年、ポール・シーモアは、あらゆる有向グラフには、第2近傍が第1近傍と少なくとも同じ大きさである頂点が少なくとも1つ必ず存在すると予想した。同様に、グラフの平方では、次数は少なくとも2倍になる。この問題は、 1995年にナサニエル・ディーンおよびブレンダ・J・ラトカによって、トーナメント（完全グラフの方向）という限定された有向グラフのクラスに関する問題を研究した論文で初めて発表された。ディーンはそれ以前に、あらゆるトーナメントが第2近傍予想に従うと予想しており、この特殊なケースはディーンの予想として知られるようになった。^[4]${\displaystyle v}$${\displaystyle v}$

有向グラフの頂点のうち、第2近傍が第1近傍と少なくとも同じ大きさである頂点をシーモア頂点と呼ぶ。^[5]

第二近傍予想では、グラフに 2 辺サイクルがないという条件が必要です。これは、そのようなサイクルを持つグラフ (たとえば、完全有向グラフ) では、すべての第二近傍が空または小さい可能性があるためです。

フィッシャー（1996）は、トーナメントの第2近傍問題の特殊なケースであるディーンの予想を証明した。^[6]

いくつかのグラフでは、最小出次数の頂点はシーモア頂点になります。たとえば、有向グラフにシンク、つまり出次数 0 の頂点がある場合、そのシンクは自動的にシーモア頂点になります。これは、その第 1 および第 2 の近傍のサイズが両方とも 0 だからです。シンクのないグラフでは、出次数 1 の頂点は常にシーモア頂点になります。三角形のないグラフの方向では、最小出次数の任意の頂点は再びシーモア頂点になります。これは、 から別の頂点 への任意の辺について、 のすべての出隣接頂点が の2 番目の近傍に属するためです。^[7]${\displaystyle v}$${\displaystyle v}$${\displaystyle w}$${\displaystyle w}$${\displaystyle v}$

頂点次数が高い任意のグラフでは、最小次数の頂点はシーモア頂点ではないかもしれないが、低次数の頂点が存在することで、近くにシーモア頂点が存在する可能性がある。このような推論を使用すると、第2近傍予想は、出次数≤6の頂点を少なくとも1つ含む任意の有向グラフに対して真であることが証明されている。^[8]

ランダムトーナメントやいくつかのランダム有向グラフは、高い確率で多くのシーモア頂点を持つ。^[5]すべての有向グラフには、第2近傍が第1近傍の 少なくとも倍の大きさである頂点があり、ここで${\displaystyle \gamma}$

${\displaystyle \gamma ={\frac {1}{6}}\left(-1+{\sqrt[{3}]{53-6{\sqrt {78}}}}+{\sqrt[{3}]{53+6{\sqrt {78}}}}\right)\approx 0.657}$

は多項式の実根である。^[9]${\displaystyle 2x^{3}+x^{2}-1}$

• 友情のパラドックス

• シーモアの第 2 近傍予想、グラフ理論と組合せ論における未解決問題、Douglas B. West。