局所線形グラフ

グラフ理論において、局所線型グラフは、すべての辺がちょうど 1 つの三角形に属する無向グラフです。同様に、グラフの各頂点について、その隣接頂点はそれぞれ他の 1 つの隣接頂点と隣接しているため、隣接頂点は誘導マッチングでペアにすることができます。^[1]局所線型グラフは、局所的にマッチしたグラフとも呼ばれています。^[2]局所線型グラフの三角形は、三角形のない 3 次元一様線型ハイパーグラフのハイパーエッジと、特定の部分シュタイナー三重システムのブロックを形成し、局所線型グラフは、これらのハイパーグラフまたは部分シュタイナーシステムのGaifman グラフとまったく同じです。

局所線形グラフの構成は数多く知られています。局所線形グラフの例には、三角サボテングラフ、3 正則三角形のないグラフの線グラフ、およびより小さな局所線形グラフの直積などがあります。特定のクネーザーグラフや特定の強正則グラフも局所線形です。

局所線形グラフがいくつの辺を持つことができるかという問題は、ルザ・セメレディ問題の定式化の 1 つです。密なグラフは頂点の数の 2 乗に比例する数の辺を持つことができますが、局所線形グラフの辺の数は少なく、少なくとも小さな非定数倍で 2 乗に届きません。局所線形になり得る最も密な平面グラフも知られています。最も密度の低い局所線形グラフは、三角サボテン グラフです。

友情グラフは、単一の共有頂点で三角形の集合を接着して形成されるグラフであり、局所的に線形です。これは、すべての頂点のペア（隣接しているかどうかに関係なく）が正確に 1 つの共通の隣接点を共有するというより強い特性を持つ唯一の有限グラフです。^[3]より一般的には、追加のサイクルを形成せずに共有頂点で三角形を接着して形成されるグラフであるすべての三角サボテングラフは、局所的に線形です。^[4]

局所線形グラフは、グラフ上のクリーク和演算の一種である次の演算によって、より小さな局所線形グラフから形成される。と を任意の 2 つの局所線形グラフとし、それぞれから三角形を選択し、選択した 2 つの三角形の対応する頂点のペアを結合して 2 つのグラフを接着する。その結果得られるグラフは局所線形のままである。^[5]${\displaystyle G}$${\displaystyle H}$

任意の 2 つの局所線形グラフの直積は、積内の三角形がいずれかの因子の三角形から派生しているため、局所線形のままです。たとえば、9 頂点のペイリー グラフ( 3-3 デュオプリズムのグラフ) は、2 つの三角形の直積です。^[1]ハミング グラフは 三角形の直積であり、これも局所線形です。^[6]${\displaystyle H(d,3)}$${\displaystyle d}$

それ自体が局所的に線形ではないグラフの中には、より大きな局所的に線形なグラフを構築するためのフレームワークとして使用できるものがあります。そのような構築の 1 つに、線グラフがあります。任意のグラフ に対して、線グラフ はのすべての辺に対して頂点を持つグラフです。 の 2 つの頂点が隣接しているとは、それらが で表す 2 つの辺が共通の端点を持つ場合です。 が3-正則三角形のないグラフである場合、その線グラフは 4-正則かつ局所的に線形です。 のすべての頂点に対して三角形があり、三角形の頂点は に接する 3 つの辺に対応します。すべての 4-正則局所的に線形なグラフは、このように構築できます。^[7]たとえば、立方八面体のグラフは立方体の線グラフであるため、局所的に線形です。上で直積として構築された局所的に線形な 9 頂点の Paley グラフは、ユーティリティ グラフの線グラフとは異なる方法で構築することもできます。この構築により、ピーターセン グラフの線グラフも局所的に線形になります。これはケージに類似した性質を持つ。つまり、最大のクリークが3つの頂点を持ち、各頂点がちょうど2つの辺が互いに素なクリークに属し、異なるクリークからの辺を持つ最短のサイクルの長さが5であるような、可能な限り最小のグラフである。^[8]${\displaystyle G}$${\displaystyle L(G)}$${\displaystyle G}$${\displaystyle L(G)}$${\displaystyle G}$${\displaystyle G}$ ${\displaystyle L(G)}$${\displaystyle v}$${\displaystyle G}$${\displaystyle v}$ ${\displaystyle K_{3,3}}$

より複雑な拡張プロセスが平面グラフに適用されます。を、立方体のグラフのようなすべての面が四辺形であるような方法で平面に埋め込まれた平面グラフとします。の各面に正方形の反角柱を接着し、 の元の辺を削除すると、新しい局所的に線形な平面グラフが生成されます。 結果の辺と頂点の数は、オイラーの多面体公式から計算できます。 に頂点がある場合、 はちょうど 面を持ち、 の面を反角柱に置き換えた結果、頂点と辺を持ちます。^[5]たとえば、この方法で、4 閉路の 2 つの面 (内部と外部) から、立方八面体を再び作成できます。 この構成の削除された 4 閉路は、多面体を二等分する、正方形の面の 4 つの対角線の閉路として、立方八面体上で確認できます。 ${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle n}$${\displaystyle n-2}$${\displaystyle G}$${\displaystyle 5(n-2)+2}$${\displaystyle 12(n-2)}$

ある種のクネザーグラフ、つまり等しいサイズの集合の交差パターンから構築されたグラフは、局所的に線形である。クネザーグラフは、それが表す集合のサイズと、これらの集合が抽出される宇宙のサイズという 2 つのパラメータによって記述される。クネザーグラフには、要素集合の要素部分集合を表す頂点 (二項係数の標準表記)がある。このグラフでは、対応する部分集合が共通の要素を持たない互いに素な集合である場合、2 つの頂点は隣接している。 の特殊なケースでは、結果として得られるグラフは局所的に線形である。なぜなら、互いに素な要素部分集合と のそれぞれに対して、その両方から素な 要素部分集合が 1 つだけ存在し、その要素はすべて にも にも含まれないからである。結果として得られる局所的に線形なグラフには、頂点と辺がある。たとえば、 の場合、クネザーグラフは15 個の頂点と 45 個の辺を持つ局所的に線形である。^[2]${\displaystyle KG_{a,b}}$${\displaystyle {\tbinom {a}{b}}}$${\displaystyle b}$${\displaystyle a}$${\displaystyle a=3b}$${\displaystyle b}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle b}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle {\tbinom {3b}{b}}}$${\displaystyle {\tfrac {1}{2}}{\tbinom {3b}{b}}{\tbinom {2b}{b}}}$${\displaystyle b=2}$${\displaystyle KG_{6,2}}$

局所的に線形なグラフは、数列のない集合から構築することもできます。を素数とし、 を を法とする数のサブセットとし、 のどの 3 つの要素もを法とする等差数列を形成しないものとします。(つまり、 は を法とするセーラム・スペンサー集合です。) この集合を使用して、局所的に線形である頂点と辺を持つ 3部グラフを構築できます。このグラフを構築するには、から までの番号が付けられた 3 つの頂点セットを作成します。から までの範囲の各数と の各要素について、最初の頂点セットの番号の頂点、2 番目の頂点セットの 番号の頂点、 3 番目の頂点セットの番号の頂点を結ぶ三角形を構築します。これらの三角形すべての和集合としてグラフを形成します。これは三角形の和集合であるため、結果として得られるグラフのすべての辺は三角形に属します。ただし、この方法で形成された三角形以外の三角形は存在できません。他の三角形では、頂点、 、 がすべて に属する番号が付けられるため、には等差数列が存在しないという仮定に反します。^[9]たとえば、 と の場合、この構成の結果は9頂点のペイリーグラフになります。 ${\displaystyle p}$${\displaystyle A}$${\displaystyle p}$${\displaystyle A}$${\displaystyle p}$${\displaystyle A}$${\displaystyle p}$${\displaystyle 3p}$${\displaystyle 3p\cdot |A|}$${\displaystyle 0}$${\displaystyle p-1}$${\displaystyle x}$${\displaystyle 0}$${\displaystyle p-1}$${\displaystyle a}$${\displaystyle A}$${\displaystyle x}$${\displaystyle x+a}$${\displaystyle x+2a}$${\displaystyle (x,x+a,x+a+b)}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c=(a+b)/2}$${\displaystyle A}$${\displaystyle (a,c,b)}$${\displaystyle A}$${\displaystyle p=3}$${\displaystyle A=\{\pm 1\}}$

局所線型グラフの三角形は、3-ユニフォームハイパーグラフ を形成するものと同義に考えることができます。このようなハイパーグラフは線型でなければなりません。つまり、そのハイパーエッジ (三角形) の 2 つが 1 つ以上の頂点を共有することはできません。局所線型グラフ自体は、ハイパーグラフのGaifman グラフ、つまり共通のハイパーエッジに属する頂点のペアのグラフです。この観点から、ハイパーグラフの内周について話すことは理にかなっています。グラフの用語では、これはグラフの三角形の 1 つではない最短のサイクルの長さです。このコンテキストでは、極性グラフ (ブラウン グラフとも呼ばれる) に基づく代数構成を使用して、4-サイクルを持たない稠密な局所線型グラフが見つかりました。そのハイパーグラフの内周は 5 です。極性グラフは、有限射影平面と、その点とその線の間の接続を維持する一対一である極性から定義されます。極性グラフの頂点は点であり、辺は 2 つの点を、一方の点がもう一方の点を含む直線に対して極性を持つ場合に結び付ける。より代数的に、同じグラフの頂点は同次座標で表すことができる。これらは有限体の値の 3 つ組であり、すべて 0 ではない。3 つ組は、互いのスカラー倍数である場合に、平面内で同じ点を定義する。このように 3 つ組で表された 2 つの点は、内積が 0 のときに隣接している。奇数次の有限体の極性グラフには、自己隣接し、どの三角形にも属さない頂点がある。これらを削除すると、結果は、頂点、辺、ハイパーグラフの内周が 5 の局所線形グラフとなり、この内周の局所線形グラフで可能な最大辺数が低次の項までとなる。^[10]${\displaystyle (x,y,z)}$${\displaystyle q}$${\displaystyle q^{2}+q+1}$${\displaystyle q+1}$${\displaystyle q^{2}}$${\displaystyle {\bigl (}{\tfrac {1}{2}}+o(1){\bigr )}q^{3}}$

グラフが正則なのは、その頂点のすべてが同じ次数、つまり接続する辺の数を持っている場合です。すべての局所線型グラフは、各頂点の辺を三角形に組み合わせることができるため、各頂点の次数は偶数でなければなりません。2 つの局所線型正則グラフの直積も、次数が因子の次数の合計に等しくなる局所線型かつ正則です。したがって、次数 2 の局所線型グラフ (三角形) の直積を取ると、すべての偶数次数の正則な局所線型グラフを作成できます。^[1]

正則局所線型グラフは少なくとも頂点を持たなければならない。なぜなら、任意の三角形とその隣接頂点だけでもこれだけの頂点があるからである。(三角形のどの2つの頂点も、局所線型性に違反することなく隣接頂点を共有できない。) ちょうどこれだけの頂点数を持つ正則グラフは、が1、2、3、または5の場合にのみ可能であり、これら4つのケースのそれぞれに対して一意に定義される。頂点数のこの制限を満たす4つの正則グラフは、3頂点2正則三角形、9頂点4正則ペイリーグラフ、15頂点6正則クネザーグラフ、およびシュレーフリグラフの27頂点10正則補グラフである。最後の27頂点10正則グラフは、立方体表面上の27本の直線の交差グラフも表す。^[2]${\displaystyle 2r}$${\displaystyle 6r-3}$${\displaystyle r}$${\displaystyle K_{3}}$${\displaystyle KG_{6,2}}$

強正則グラフは、4つのパラメータで特徴付けられる。ここで、は頂点の数、は頂点あたりの接続辺の数、は隣接する頂点のペアごとに共有される隣接点の数、は隣接しない頂点のペアごとに共有される隣接点の数である。グラフが局所線形の場合。すでに上で述べた強正則グラフである局所線形グラフとそのパラメータは^{[11]である。}${\displaystyle (n,k,\lambda ,\mu )}$${\displaystyle n}$${\displaystyle k}$${\displaystyle \lambda }$${\displaystyle \mu }$${\displaystyle \lambda =1}$

• 三角形 (3,2,1,0)、
• 9頂点ペイリーグラフ（9,4,1,2）
• クネザーグラフ（15,6,1,3）と${\displaystyle KG_{6,2}}$
• シュレーフリグラフ(27,10,1,5)の補グラフ。

その他の局所線型強正則グラフには、

• Brouwer -Haemers グラフ(81,20,1,6)、^[12]
• ベルレカンプ– ファン リント – ザイデル グラフ(243,22,1,2)、^[13]
• コシデンテ・ペンティラグラフ（378,52,1,8）^[14]および
• ゲームグラフ（729,112,1,20）。^[15]

潜在的に有効な他の組み合わせには(99,14,1,2)と(115,18,1,3)が含まれますが、これらのパラメータを持つ強正則グラフが存在するかどうかは不明です。^[11]パラメータ(99,14,1,2)を持つ強正則グラフの存在に関する問題は、コンウェイの99グラフ問題として知られており、ジョン・ホートン・コンウェイは、その解決に1000ドルの賞金を出しました。^[16]${\displaystyle \lambda =1}$

局所的に線形である次数4または6の距離正則グラフは有限個存在する。同じ次数の強正則グラフ以外にも、ピーターセングラフの線グラフ、ハミンググラフ、半分にされたフォスターグラフなどが含まれる。^[17]${\displaystyle H(3,3)}$

Ruzsa–Szemerédi 問題の定式化の 1 つは、- 頂点の局所線型グラフの最大辺数を求めるものです。Imre Z. RuzsaとEndre Szemerédi が証明したように、この最大数は ですが、任意の に対してとなります。進行フリー集合から局所線型グラフを構築すると、辺を持つ最も密な既知の局所線型グラフが得られます。(これらの式で、、、はそれぞれ、小さな o 表記、大きなオメガ表記、大きな O 表記の例です。) ^[9]${\displaystyle n}$${\displaystyle o(n^{2})}$${\displaystyle \Omega (n^{2-\varepsilon })}$${\displaystyle \varepsilon >0}$${\displaystyle n^{2}/\exp O({\sqrt {\log n}})}$${\displaystyle o}$${\displaystyle \Omega }$${\displaystyle O}$

平面グラフのうち、頂点を持つ局所線型グラフの最大辺数はである。立方八面体のグラフは、 の四辺形面を反角柱に拡張することで構築される、頂点と辺を持つ多面体グラフの無限列の最初のものである。 これらの例は、上限が達成できることを示している。^[5]${\displaystyle n}$${\displaystyle {\tfrac {12}{5}}(n-2)}$${\displaystyle n=5k+2}$${\displaystyle {\tfrac {12}{5}}(n-2)=12k}$${\displaystyle k=2,3,\dots }$${\displaystyle K_{2,k}}$${\displaystyle {\tfrac {12}{5}}(n-2)}$

すべての局所線形グラフは、グラフ内のどのパスでも、一致するエッジをその三角形の他の 2 つのエッジに置き換えることができるため、マッチングが削除された後も接続されたままになるという特性があります。この特性を持つグラフの中で最も密度が低いのは三角形のサボテン グラフであり、これは最も密度の低い局所線形グラフでもあります。^[4]

局所線形グラフの応用例の1つは、量子論理で特定のヒルベルト空間方程式が互いに推論できるかどうかを判断するのに役立つグリーキー図の定式化です。この応用では、局所線形グラフの三角形がブロックサイズ3のグリーキー図のブロックを形成します。格子に対応するグリーキー図は、ハイパーグラフの内周が5以上の局所線形グラフから得られます^[18]。これは、たとえば極性グラフから構築されます^{[10] 。}

ランダムサンプリングとグラフ除去補題の組み合わせは、任意の3-均一線形ハイパーグラフまたは部分シュタイナー三重システム内の大きな高内周3-均一ハイパーグラフを見つけるために使用できます。この方法は、 3-均一線形ハイパーグラフと部分シュタイナー三重システムの独立数の漸近的に厳しい下限を証明するために使用できます。^[19]