佩利圖

在數學中，佩利圖（Paley graphs）是從合適的有限體的成員中建構出的無向圖，其連接方式為：若一對元素的差為二次剩餘，則將它們相連。佩利圖構成了一個無限的會議圖族，從而產生了一個無限的對稱會議矩陣族。佩利圖允許將圖論工具應用於二次剩餘的數論研究，並且其有趣的性質使其在更廣泛的圖論領域中也相當實用。

佩利圖以雷蒙德·佩利（Raymond Paley）的名字命名。它們與利用二次剩餘建構阿達馬矩陣的佩利建構法密切相關。 它們由 與 獨立地作為圖引進。Sachs 對其自補性質感興趣，而 Erdős 和 Rényi 則研究了它們的對稱性。

佩利有向圖（Paley digraphs）是佩利圖的有向類比，可產生反對稱會議矩陣。它們由 （獨立於 Sachs、Erdős 和 Rényi）引進，作為一種建構競賽圖的方法。這些競賽圖具有一種以往認為只有隨機競賽圖才擁有的性質：在佩利有向圖中，每個小的頂點子集都會被某個其他頂點所支配。

定義

設 q 為一個質數冪，使得 q ≡ 1 (mod 4)。也就是說，q 要麼是畢氏質數（一個模 4 同餘 1 的質數）的任意次方，要麼是奇數非畢氏質數的偶數次方。如此選擇 q 意味著在階為 q 的唯一有限體 Fq 中，元素 −1 存在平方根。

現在，令 V = Fq，並令

E= \left \{\{a,b\} \ : \ a-b\in (\mathbf{F}_q^{\times})^2 \right \}。

如果一對 {a,b} 被包含在 E 中，則無論其兩個元素的順序如何，該配對都會被包含。這是因為 a − b = −(b − a)，且 −1 是一個平方數，由此可知，a − b 是平方數若且唯若 b − a 是平方數。

根據定義，G = (V, E) 即為階為 q 的佩利圖。

範例

當 q = 13 時，有限體 Fq 即為模 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)。

性質

佩利圖是自補圖：任何佩利圖的補圖都與其同構。其中一種同構是透過一個映射實現，該映射將頂點 x 映至 ax，其中 a 是任意一個非二次剩餘。

佩利圖是強正則圖，其參數為

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

這實際上源於佩利圖是弧傳遞且自補的。具有此種形式參數（對於任意的 q）的強正則圖被稱為會議圖，因此佩利圖構成了一個無限的會議圖族。會議圖（例如佩利圖）的鄰接矩陣可用於建構會議矩陣，反之亦然。會議矩陣是一種其係數為 0 或 ±1 且對角線為零的矩陣，其與自身的轉置相乘會得到單位矩陣的純量倍。

佩利圖的特徵值為 \tfrac{1}{2}(q-1)（重數為 1）以及 \tfrac{1}{2} (-1 \pm \sqrt{q})（兩者的重數均為 \tfrac{1}{2}(q-1)）。這些特徵值可以使用二次高斯和或強正則圖的理論計算得出。

如果 q 是質數，則佩利圖的等周數 i(G) 滿足以下邊界：

當 q 為質數時，相關的佩利圖是一個漢米爾頓循環圖。

佩利圖是擬隨機的：在佩利圖中，每個可能的定階圖作為子圖出現的次數，與其在隨機圖中出現的次數相同（在 q 趨近於無窮大的極限下）；並且，大的頂點集合所擁有的邊數，也約略等於它們在隨機圖中會有的邊數。

• 階數為 9 的佩利圖是局部線性圖、車形圖，也是 3-3 雙稜柱的圖形。
• 階數為 13 的佩利圖，其書厚度為 4，隊列數為 3。
• 階數為 17 的佩利圖是唯一的最大圖 G，使得 G 與其補圖皆不包含 4-頂點完全子圖。由此可知拉姆齊數 R(4, 4) = 18。
• 階數為 101 的佩利圖是目前已知的最大圖 G，使得 G 與其補圖皆不包含 6-頂點完全子圖。
• Sasukara 等人 (1993) 使用佩利圖來推廣霍羅克斯-芒福德叢的建構。

佩利有向圖

設 q 為一個質數冪，使得 q ≡ 3 (mod 4)。因此，階為 q 的有限體 Fq 中，−1 沒有平方根。所以，對於 Fq 中每一對相異元素 (a,b)，a − b 或 b − a 中恰好有一個是平方數。佩利有向圖是一個有向圖，其頂點集為 V = Fq，弧集為

A = \left \{(a,b)\in \mathbf{F}_q\times\mathbf{F}_q \ : \ b-a\in (\mathbf{F}_q^{\times})^2 \right \}.

佩利有向圖是一種競賽圖，因為每對相異頂點都由一條單向的弧所連接。

佩利有向圖可用於建構某些反對稱會議矩陣和雙平面幾何。

虧格

階數為 13 的佩利圖中，每個頂點的六個鄰居連接成一個循環；也就是說，該圖是局部循環的。因此，這個圖可以嵌入為環面的一個惠特尼三角剖分，其中每個面都是三角形，且每個三角形都是一個面。更一般地，如果任何階數為 q 的佩利圖都能夠被嵌入，使其所有的面都是三角形，那麼我們就可以透過歐拉示性數計算出所得曲面的虧格為 \tfrac{1}{24}(q^2 - 13q + 24)。Bojan Mohar 推測，在 q 為平方數的情況下，可嵌入佩利圖的曲面之最小虧格接近此邊界，並質疑此邊界是否可能更廣泛地成立。具體來說，Mohar 推測階數為平方數的佩利圖可以嵌入到虧格為

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

的曲面中，其中 o(1) 項可以是任何在 q 趨近於無窮大時極限為零的 q 的函數。

發現了階數為 q ≡ 1 (mod 8) 的佩利圖的高度對稱且自對偶的嵌入，此嵌入推廣了階數為 9 的佩利圖在環面上作為 3×3 方格網的自然嵌入。然而 White 的嵌入所產生的虧格比 Mohar 推測的邊界高出約三倍。

外部連結

Category:數論 Category:參數化圖族 Category:正則圖 Category:強正則圖