ペイリーグラフ

数学において、ペイリーグラフとは、適切な有限体の要素から、 2次剰余数だけ異なる要素のペアを結び付けて構築される無向グラフである。ペイリーグラフは無限族の会議グラフを形成し、それによって無限族の対称会議行列が得られる。ペイリーグラフを用いることで、グラフ理論的手法を2次剰余数の数論に適用することが可能となり、また、グラフ理論全般において有用な興味深い性質を持つ。

ペイリーグラフはレイモンド・ペイリーにちなんで名付けられました。これらは、二次剰余からアダマール行列を構成するペイリー構成と密接に関連しています。 ^{[ 1 ]}これらは、ザックス（1962年）とエルデシュとレニ（1963年） によって独立にグラフとして導入されました。ザックスは自己相補性特性に興味を持ち、^{[ 2 ]}エルデシュとレニは対称性を研究しました。^{[ 3 ]}

ペイリー有向グラフは、反対称会議行列を生成するペイリーグラフの有向類似物です。これらは、グラハムとスペンサー（1971） （サックス、エルデシュ、レーニとは独立に）によって、以前はランダムトーナメントのみが持つことが知られていた特性を持つトーナメントを構築する方法として導入されました。ペイリー有向グラフでは、頂点の小さな部分集合はすべて、他の何らかの頂点によって支配されます。^{[ 4 ]}

q を素数のべき乗とし、${\textstyle q\equiv 1{\pmod {4}}}$つまり、q は 4 を法として 1 に合同な素数 (ピタゴラス素数)の任意のべき乗、または奇数の非ピタゴラス素数の偶数べき乗のいずれかでなければならない。このqの選択は、位数qの唯一の有限体F _qにおいて、要素−1 が平方根を持つことを意味する。 

ここで、V = F _qとし、

${\displaystyle E=\left\{\{a,b\}\$ :\ ab\in (\mathbf {F} _{q}^{\times })^{2}\right\}} .

ペア { a , b } がEに含まれる場合、その 2 つの要素の順序付けのどちらでも含まれます。なぜなら、a  − b = −( b − a ) であり、−1 は平方数であるため、a − bが平方数であるのは、 b − aが平方数である場合のみであることがわかります。         

定義により、 G  =  ( V , E ) は次数qのペイリーグラフである。  

ペイリーグラフの次数列は

1、5、9、13、17、25、29、37、41、49、53、61、73、... （ OEISの配列A085759）

q = 13の場合、体F _qは 13 を法とする整数演算のみを表します。13 を法とする平方根を持つ数は次のとおりです。

• ±1（+1の場合は平方根±1、-1の場合は平方根± 5）
• ±3（+3の場合は平方根±4、-3の場合は平方根± 6）
• ±4（+4の場合は平方根±2、-4の場合は±3 ）。

したがって、ペイリーグラフでは、[0,12] の範囲の各整数に対して頂点を形成し、そのような各整数x を、 x  ±  1  (mod  13)、x  ±  3  (mod  13)、およびx  ±  4  (mod 13)の 6 つの隣接点に接続します 。

ペイリーグラフは自己相補的である。つまり、任意のペイリーグラフの補グラフはそれと同型である。同型性の1つは、頂点xをxk (mod q )に写像することによって実現される。ここで、kはmod q の任意の二次非剰余である。^{[ 2 ]}

ペイリーグラフは、パラメータを持つ強正則グラフです。

${\displaystyle srg\left(q,{\tfrac {1}{2}}(q-1),{\tfrac {1}{4}}(q-5),{\tfrac {1}{4}}(q-1)\right).}$

これは実際、グラフが弧推移的かつ自己相補的であるという事実から導かれる。この形式のパラメータを持つ強正則グラフ（任意のqに対して）は会議グラフと呼ばれ、したがってペイリーグラフは会議グラフの無限族を形成する。ペイリーグラフなどの会議グラフの隣接行列は会議行列を構築するために使用でき、その逆も可能である。これらは係数が± 1で対角線上にゼロを持ち、転置行列を乗算すると単位行列のスカラー倍となる行列である。^{[ 5 ]}

ペイリーグラフの固有値は${\displaystyle {\tfrac {1}{2}}(q-1)}$（多重度1）および$\displaystyle {\tfrac {1}{2}}(-1\pm {\sqrt {q}})}$（どちらも多重度あり）${\displaystyle {\tfrac {1}{2}}(q-1)}$これらは、二次ガウス和を用いるか、強正則グラフの理論を用いて計算することができる。 ^{[ 6 ]}

qが素数の場合、ペイリーグラフの等周数i ( G )は次の境界を満たす。

$\displaystyle \displaystyle {\frac {q-{\sqrt {q}}}{4}}\leq i(G)\leq {\frac {q-1}{4}}.}$^{[ 7 ]}

qが素数の場合、関連するペイリーグラフはハミルトン巡回グラフである。

ペイリーグラフは準ランダムである。ペイリーグラフのサブグラフとして出現する定数次数グラフの数は、（qが大きい極限では）ランダムグラフの場合と同じであり、大きな頂点の集合はランダムグラフの場合とほぼ同じ数のエッジを持つ。^{[ 8 ]}

• 次数9のペイリーグラフは、局所的に線形なグラフであり、ルークのグラフであり、 3-3デュオプリズムのグラフである。
• 次数13のペイリーグラフは、ブックの厚さが4、キューの数が3である。 ^{[ 9 ]}
• 次数17のペイリーグラフは、Gとその補グラフのどちらにも完全な4頂点部分グラフが含まれない唯一の最大のグラフGである。 ^{[ 10 ]} したがって、ラムゼイ数R (4,4 ) = 18となる。   
• 次数101のペイリーグラフは、現在知られているグラフGの中で、 Gとその補グラフのどちらにも完全な6頂点部分グラフが含まれない最大のグラフである。
• Sasukara et al. (1993) は、Paley グラフを使用してHorrocks–Mumford バンドルの構成を一般化しています。^{[ 11 ]}

q を素数のべき乗とし、 q = 3 (mod 4)とする。したがって、位数qの有限体F _qは− 1の平方根を持たない。結果として、 F _qの異なる要素のペア ( a , b ) に対して、a − bまたはb − aのいずれか一方のみが平方数となる。ペイリー有向グラフは、頂点集合V = F _qと弧集合を持つ有向グラフである。

${\displaystyle A=\left\{(a,b)\in \mathbf {F} _{q}\times \mathbf {F} _{q}\$ :\ ba\in (\mathbf {F} _{q}^{\times })^{2}\right\}.}

ペイリー有向グラフはトーナメントグラフである。なぜなら、異なる頂点のペアは、ただ一方向の弧によって結ばれているからである。

ペイリー有向グラフは、いくつかの反対称会議行列と二平面幾何学の構築につながる。

次数13のペイリーグラフの各頂点の6つの隣接頂点はサイクルで接続されています。つまり、このグラフは局所的に巡回グラフです。したがって、このグラフは、すべての面が三角形であり、すべての三角形が面であるトーラスのホイットニー三角形分割として埋め込むことができます。より一般的に、次数qの任意のペイリーグラフを、すべての面が三角形になるように埋め込むことができれば、結果として得られる曲面の種数をオイラー標数を用いて次のように計算できます。${\displaystyle {\tfrac {1}{24}}(q^{2}-13q+24)}$ボヤン・モハールは、qが正方形の場合、ペイリーグラフを埋め込むことができる曲面の最小種数はこの境界に近いと推測し、そのような境界がより一般的に成り立つかどうか疑問を呈している。具体的には、モハールは、正方形の位数のペイリーグラフは種数を持つ曲面に埋め込むことができると推測している。

${\displaystyle (q^{2}-13q+24)\left({\tfrac {1}{24}}+o(1)\right),}$

ここで、o(1)項は、 qが無限大に近づく極限でゼロになるqの任意の関数である。 ^{[ 12 ]}

White (2001) は、次数q  ≡  1  (mod 8)の Paley グラフの埋め込みが 高度に対称で自己双対であることを発見し、次数 9 の Paley グラフの自然な埋め込みをトーラス上の 3×3 の正方形グリッドとして一般化しました。しかし、White の埋め込みの種数は、Mohar の予想上限よりも約 3 倍高くなっています。^{[ 13 ]}

• Baker, RD; Ebert, GL; Hemmeter, J.; Woldar, AJ (1996). "平方位数のペイリーグラフにおける最大クリーク". J. Statist. Plann. Inference . 56 : 33– 38. doi : 10.1016/S0378-3758(96)00006-7 .
• Broere, I.; Döman, D.; Ridley, JN (1988). 「特定のペイリーグラフのクリーク数と彩色数」. Quaestiones Mathematicae . 11 : 91–93 . doi : 10.1080/16073606.1988.9631945 .

• ブロワー、アンドリーズ E. 「ペイリーグラフ」。
• モハール、ボージャン(2005)。「ペイリーグラフの属」。