กราฟพาเลย์
กราฟ Paley อันดับ 13
ตั้งชื่อตาม	เรย์มอนด์ พาเลย์
จุดยอด	q ≡ 1 mod 4, qเป็นกำลังของจำนวนเฉพาะ
ขอบ	q ( ​​q − 1)/4
เส้นผ่านศูนย์กลาง	2
คุณสมบัติ	กราฟการประชุมปกติอย่างมากเสริมกันเอง
สัญกรณ์	QR( q )
ตารางกราฟและพารามิเตอร์

ในทางคณิตศาสตร์กราฟ Paleyคือกราฟแบบไม่มีทิศทางที่สร้างขึ้นจากสมาชิกของฟิลด์จำกัด ที่เหมาะสม โดยการเชื่อมต่อคู่ขององค์ประกอบที่แตกต่างกันด้วยเศษกำลังสองกราฟ Paley ก่อให้เกิดตระกูล อนันต์ของกราฟ การประชุมซึ่งก่อให้เกิดตระกูลอนันต์ของเมทริกซ์การประชุม สมมาตร กราฟ Paley ช่วยให้สามารถ นำเครื่องมือ ทางทฤษฎีกราฟไปประยุกต์ใช้กับทฤษฎีจำนวนของเศษกำลังสองได้ และมีคุณสมบัติที่น่าสนใจซึ่งทำให้มีประโยชน์ในทฤษฎีกราฟโดยทั่วไป

กราฟ Paley ได้รับการตั้งชื่อตามRaymond Paley กราฟ เหล่านี้มีความเกี่ยวข้องอย่างใกล้ชิดกับการสร้าง Paleyสำหรับการสร้างเมทริกซ์ Hadamardจากเศษกำลังสอง^{[ 1 ]} กราฟเหล่านี้ได้รับการแนะนำโดยอิสระโดยSachs (1962)และErdős & Rényi (1963) Sachs สนใจกราฟเหล่านี้เนื่องจากคุณสมบัติการเติมเต็มในตัวเอง^{[ 2 ]}ในขณะที่ErdősและRényiศึกษาสมมาตรของกราฟเหล่านี้^{[ 3 ]}

ไดกราฟ Paleyเป็น อนาล็อกแบบ มีทิศทางของกราฟ Paley ที่ให้เมทริกซ์การประชุม แบบแอนติสมมาตร Graham & Spencer (1971) เป็น ผู้แนะนำ ไดกราฟ Paley (โดยอิสระจาก Sachs, Erdős และ Rényi) เพื่อใช้ในการสร้างทัวร์นาเมนต์ที่มีคุณสมบัติที่ทราบกันดีอยู่แล้วว่ามีเฉพาะในทัวร์นาเมนต์แบบสุ่มเท่านั้น นั่นคือ ในไดกราฟ Paley เซตย่อย เล็กๆ ของจุดยอดทุกเซตจะถูกครอบงำโดยจุดยอดอื่น^{[ 4 ]}

ให้qเป็นกำลังของจำนวนเฉพาะโดยที่นั่นคือqควรจะเป็นกำลังใดๆ ของจำนวนเฉพาะที่สอดคล้องกับ 1 mod 4 ( จำนวนเฉพาะพีทาโกเรียน ) หรือเป็นกำลังคู่ของจำนวนเฉพาะคี่ที่ไม่ใช่พีทาโกเรียน การเลือกq แบบนี้ หมายความว่าในฟิลด์จำกัดF _qที่มีอันดับq เพียงหนึ่งเดียว สมาชิก −1 มีรากที่สอง ${\textstyle q\equiv 1{\pmod {4}}}$

ตอนนี้ให้V = F _qและให้

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

ถ้าคู่ { a , b } อยู่ในEแสดงว่าคู่นั้นอยู่ใน E ไม่ว่าจะเรียงลำดับสมาชิกทั้งสองแบบใดก็ตาม เพราะa  −  b = −( b  −  a ) และ −1 เป็นกำลังสอง ซึ่งสรุปได้ว่าa  −  bเป็นกำลังสองก็ต่อเมื่อb  −  aเป็นกำลังสอง

ตามนิยามG  = ( V ,  E ) คือ กราฟ Paley อันดับ  q

ลำดับการเรียงของกราฟ Paley เริ่มต้นขึ้น

1, 5, 9, 13, 17, 25, 29, 37, 41, 49, 53, 61, 73, ... (ลำดับA085759ในOEIS )

สำหรับq = 13 ฟิลด์F _qคือผลรวมเลขคณิตจำนวนเต็มมอดูล 13 ตัวเลขที่มีรากที่สองมอดูล 13 ได้แก่:

• ±1 (รากที่สอง ±1 สำหรับ +1, ±5 สำหรับ −1)
• ±3 (รากที่สอง ±4 สำหรับ +3, ±6 สำหรับ −3)
• ±4 (รากที่สอง ±2 สำหรับ +4, ±3 สำหรับ −4)

ดังนั้น ในกราฟ Paley เราจะสร้างจุดยอดสำหรับจำนวนเต็มแต่ละจำนวนในช่วง [0,12] และเชื่อมต่อจำนวนเต็มx แต่ละจำนวนดังกล่าว กับจุดยอดข้างเคียงหกจุด ได้แก่x  ± 1 (mod 13), x  ± 3 (mod 13) และx  ± 4 (mod 13)

กราฟ Paley เป็นส่วนเติมเต็มในตัวเอง : ส่วนเติมเต็มของกราฟ Paley ใดๆ จะเป็นไอโซมอร์ฟิกกับกราฟนั้น ไอโซมอร์ฟิกหนึ่งคือผ่านการแมปที่นำจุดยอดxไปยังxk (mod q )โดยที่k เป็น ค่าที่ไม่ใช่เศษกำลังสองใดๆmod q ^{[ 2 ]}

กราฟ Paley เป็นกราฟปกติอย่างเข้มข้นโดยมีพารามิเตอร์

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

อันที่จริงแล้ว สิ่งนี้เป็นผลมาจากข้อเท็จจริงที่ว่ากราฟเป็นแบบอาร์คทรานซิทีฟและแบบสมบูรณ์ในตัวเอง กราฟปกติอย่างเข้มข้นที่มีพารามิเตอร์ในรูปแบบนี้ (สำหรับq ใดๆ ) เรียกว่ากราฟการประชุมดังนั้นกราฟ Paley จึงประกอบเป็นตระกูลอนันต์ของกราฟการประชุมเมทริกซ์ประชิดของกราฟการประชุม เช่น กราฟ Paley สามารถใช้สร้างเมทริกซ์การประชุมได้ และในทางกลับกัน เมทริกซ์เหล่านี้มีสัมประสิทธิ์เป็น±1โดยมีศูนย์บนแนวทแยงมุม ซึ่งให้ผลคูณเชิงสเกลาร์ของเมทริกซ์เอกลักษณ์เมื่อคูณด้วยทรานสโพส^{[ 5 ]}

ค่าลักษณะเฉพาะของกราฟ Paley คือ(โดยมีความซ้ำซ้อน 1) และ(โดยมีความซ้ำซ้อน) สามารถคำนวณได้โดยใช้ผลรวม Gauss กำลังสองหรือโดยใช้ทฤษฎีกราฟปกติอย่างเข้มงวด^{[ 6 ]}${\displaystyle {\tfrac {1}{2}}(q-1)}$${\displaystyle {\tfrac {1}{2}}(-1\pm {\sqrt {q}})}$${\displaystyle {\tfrac {1}{2}}(q-1)}$

ถ้าqเป็นจำนวนเฉพาะจำนวนไอโซเพอริเมตริกi ( G )ของกราฟ Paley จะเป็นไปตามขอบเขตต่อไปนี้:

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

เมื่อqเป็นจำนวนเฉพาะ กราฟ Paley ที่เกี่ยวข้องจะเป็นกราฟ Hamiltonian circulant

กราฟ Paley เป็นแบบกึ่งสุ่ม : จำนวนครั้งที่กราฟลำดับคงที่ที่เป็นไปได้แต่ละกราฟปรากฏเป็นกราฟย่อยของกราฟ Paley นั้น (ในขีดจำกัดสำหรับq ขนาดใหญ่ ) จะเท่ากับกราฟสุ่ม และเซตของจุดยอดขนาดใหญ่จะมีจำนวนขอบโดยประมาณเท่ากับที่จะมีในกราฟสุ่ม^{[ 8 ]}

• กราฟ Paley อันดับ 9 เป็นกราฟเชิงเส้นเฉพาะที่กราฟของเรือและกราฟของปริซึมคู่ 3-3
• กราฟ Paley ลำดับที่ 13 มีความหนาของหนังสือ 4 และหมายเลขคิว 3 ^{[ 9 ]}
• กราฟ Paley ลำดับที่ 17 เป็นกราฟที่ใหญ่ที่สุดที่ไม่ซ้ำกันGซึ่งทั้งGและส่วนเติมเต็มของมันไม่ประกอบด้วยกราฟย่อย 4 จุดยอดที่สมบูรณ์^{[ 10 ]} ส่งผลให้จำนวน Ramsey R (4, 4) = 18
• กราฟ Paley อันดับ 101 เป็นกราฟG ที่ใหญ่ที่สุดเท่าที่ทราบในปัจจุบัน ซึ่งทั้งGและกราฟส่วนเติมเต็มของ G ไม่มีกราฟย่อยสมบูรณ์ที่มี 6 จุดยอด
• Sasukara et al. (1993) ใช้กราฟ Paley เพื่อสรุปการสร้าง บันเดิ ลHorrocks–Mumford ^{[ 11 ]}

ให้qเป็นกำลังของจำนวนเฉพาะโดยที่q = 3 (mod 4) ดังนั้น ฟิลด์จำกัดอันดับq , F _q , จะไม่มีรากที่สองของ −1 ด้วยเหตุนี้ สำหรับแต่ละคู่ ( a , b ) ของสมาชิกที่แตกต่างกันในF _q a − bหรือb − aอย่างใดอย่างหนึ่งจะเป็นกำลังสอง แต่ไม่ใช่ทั้งสองอย่างกราฟระบุทิศทางของ Paleyคือกราฟระบุทิศทางที่มีเซตจุดยอด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 เป็นทัวร์นาเมนต์เนื่องจากจุดยอดที่แตกต่างกันแต่ละคู่จะเชื่อมต่อกันด้วยส่วนโค้งในทิศทางเดียวเท่านั้น

กราฟระบุทิศทางของ Paley นำไปสู่การสร้างเมทริกซ์การประชุมแบบปฏิสมมาตรและ เรขาคณิตระนาบคู่ บางประเภท

กราฟ Paley อันดับ 13 เชื่อมต่อจุดข้างเคียงทั้งหกจุดของแต่ละจุดยอดในกราฟ Paley นั้นเข้าด้วยกันเป็นวงจร กล่าวคือ กราฟนี้เป็นกราฟวงจรเฉพาะที่ดังนั้น กราฟนี้จึงสามารถฝังตัวเป็นสามเหลี่ยม Whitneyบนทอรัสได้ โดยที่ทุกหน้าเป็นรูปสามเหลี่ยมและทุกรูปสามเหลี่ยมเป็นหน้า โดยทั่วไปแล้ว หากกราฟ Paley อันดับq ใดๆ สามารถฝังตัวได้โดยที่ทุกหน้าเป็นรูปสามเหลี่ยม เราสามารถคำนวณจีนัสของพื้นผิวที่ได้โดยใช้ลักษณะเฉพาะของออยเลอร์ได้Bojan Moharตั้งข้อสันนิษฐานว่าจีนัสต่ำสุดของพื้นผิวที่สามารถฝังกราฟ Paley ได้นั้นอยู่ใกล้ขอบเขตนี้ในกรณีที่qเป็นกำลังสอง และตั้งคำถามว่าขอบเขตดังกล่าวอาจใช้ได้ทั่วไปหรือไม่ โดยเฉพาะอย่างยิ่ง 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 ]}

White (2001)พบการฝังตัวของกราฟ Paley ที่มีลำดับq  ≡ 1 (mod 8) ซึ่งมีความสมมาตรสูงและเป็นคู่ตัวเอง โดยเป็นการขยายการฝังตัวตามธรรมชาติของกราฟ Paley ที่มีลำดับ 9 ให้เป็นตารางสี่เหลี่ยมจัตุรัสขนาด 3×3 บนทอรัส อย่างไรก็ตาม เจนัสของการฝังตัวของ White นั้นสูงกว่าขอบเขตที่คาดการณ์ไว้ของ Mohar ประมาณสามเท่า^{[ 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) “กราฟสกุล Paley ”