ペイリーグラフ

ペイリーグラフ
13次のペイリーグラフ
名前の由来	レイモンド・ペイリー
頂点	q ≡ 1 mod 4、 q素数乗
エッジ	q ( q − 1)/4
直径	2
プロパティ	強い正則性 会議グラフ 自己補完的
表記	QR( q ) は、
グラフとパラメータの表

数学において、ペイリーグラフは、適切な有限体のメンバーから、平方剰余だけ異なる要素のペアを接続することによって構築される無向グラフです。ペイリーグラフは、無限の会議グラフの族を形成し、対称会議行列の無限の族を生成します。ペイリーグラフを使用すると、グラフ理論のツールを平方剰余の数論に適用でき、グラフ理論でより一般的に役立つ興味深い特性があります。

ペイリーグラフはレイモンド・ペイリーにちなんで名付けられました。これは、2乗剰余からアダマール行列を構成するペイリー構成と密接に関連しています。 ^[1]ペイリー グラフは、Sachs (1962) と Erdős & Rényi (1963) によって独立にグラフとして導入されました。Sachsは、その自己相補性の性質に興味を持ちました。^[2] ErdősとRényi は、その対称性を研究しました。^[3]

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

q をq = 1 (mod 4)となるような素数累乗とします。つまり、q はピタゴラス素数の任意の累乗(1 mod 4 と合同な素数) か、ピタゴラス素数でない奇数の偶数累乗のいずれかになります。この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次数の Paley グラフです 。

q = 13の場合、体F _{q は}13 を法とする整数演算です。13 を法とする平方根を持つ数は次のとおりです。

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

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

ペイリーグラフは自己補集合である。つまり、任意のペイリーグラフの補集合はそれと同型である。同型性の1つは、頂点xをxk (mod q )に写像することである。ここでkは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]

ペイリーグラフの固有値は(重複度1) と(重複度は両方とも) である。これらは、2次ガウス和または強正則グラフの理論を使用して計算できる。 ^[6]${\displaystyle {\tfrac {1}{2}}(q-1)}$${\displaystyle {\tfrac {1}{2}}(-1\pm {\sqrt {q}})}$${\displaystyle {\tfrac {1}{2}}(q-1)}$

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 の Paley グラフは、現在、Gとその補グラフのどちらにも完全な 6 頂点サブグラフが含まれない、最大の既知のグラフGです。
• サスカラら（1993）は、ペイリーグラフを用いてホロックス・マンフォード束の構築を一般化した。^[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\}.}$

Paley 有向グラフは、異なる頂点の各ペアが 1 方向のみの弧でリンクされているため、 トーナメントです。

Paley 有向グラフは、いくつかの反対称会議行列と複平面幾何学の構築につながります。

位数 13 の Paley グラフの各頂点の 6 つの隣接頂点は、循環的に接続されています。つまり、グラフは局所的に循環的です。したがって、このグラフは、すべての面が三角形で、すべての三角形が面であるトーラスのWhitney 三角形分割として埋め込むことができます。より一般的には、位数qの任意の Paley グラフを、そのすべての面が三角形になるように埋め込むことができれば、結果として得られる曲面の種数を、オイラー特性を介してとして計算できます。Bojan Mohar は、 qが正方形の場合、Paley グラフを埋め込むことができる曲面の最小種数はこの境界に近いと予想し、このような境界がより一般的に成り立つかどうかを疑問視しています。具体的には、Mohar は、平方位数の Paley グラフを種数 の曲面に埋め込むことができると予想しています。 ${\displaystyle {\tfrac {1}{24}}(q^{2}-13q+24)}$

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

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

ホワイト（2001）は、高度に対称で自己双対なq≡1 （mod8）の位数のペイリーグラフの埋め込みを発見し 、位数9のペイリーグラフの自然な埋め込みをトーラス上の3×3の正方格子として一般化した。しかし、ホワイトの埋め込みの種数は、モハールの予想された境界よりも約3倍高い。^[13]

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

• Brouwer, Andries E.「Paley グラフ」。
• モハール、ボージャン(2005)。 「ペイリーグラフの属」。