ガーランドのトークングラフの方法

グラフ G=(V,E) の k 番目のトークングラフは、頂点が V の k 部分集合であり、辺が A と B のすべての k 部分集合の対で、A と B の対称差が G の辺を形成するグラフ Fk(G) です。L(G) を G のラプラシアン行列、Lk(G) を Fk(G) のラプラシアン行列とします。Dalfó、Duque、Fabila-Monroy、Fiol、Huemer、Trujillo-Negrete、および Zaragoza Martínez によって、n 頂点を持つ任意のグラフ G と任意の 0≤ℓ≤k≤⌊n/2⌋ に対して、Lℓ(G) のスペクトルが Lk(G) のそれに含まれることが示されました。ここでは、Lk(G) のスペクトルと Lk−1(G) のそれとの関係を引き続き研究します。特に、1≤k≤⌊n/2⌋ の場合において、Lk(G) の任意の固有値 λ が Lk−1(G) のスペクトルに含まれない場合、k(λ2(L(G))−k+1)≤λ≤kλn(L(G)) を満たすことを示します。ここで、λ2(L(G)) は L(G) の第2小さい固有値（G の代数的接続性とも呼ばれる）、λn(L(G)) はその最大固有値です。我々の証明は、高次元ラプラシアンの研究のために元々開発されたガーランドの方法の適応に依存しています。