Contele de Paley

Contele de Paley
Contele de Paley al 13-lea Ordin
Vârfurile	q ≡ 1 mod 4, q este o putere primă
coaste	q ( q − 1)/4
Proprietăți	Graficul conferinței complementare de sine puternic regulate
Desemnare	QR( q )
Fișiere media la Wikimedia Commons

În teoria grafurilor, grafurile Paley (numite după Raymond Paley ) sunt grafuri dense , nedirecționate, construite din termenii unui câmp finit adecvat prin conectarea perechilor de elemente care diferă printr-un reziduu pătratic . Graficele Paley formează o familie infinită de grafice de conferință deoarece sunt strâns legate de familia infinită de matrici de conferințe simetrice . Graficele Paley oferă o oportunitate de a aplica instrumentele teoretice ale teoriei grafurilor în teoria reziduurilor pătratice și au proprietăți interesante care le fac utile pentru teoria grafurilor în general.

Graficele Paley sunt strâns legate de construcția lui Paley pentru a construi matrici Hadamard din reziduuri pătratice (Paley, 1933) [1] . Au fost introduși ca conți independent de Sachs (Sachs, 1962) și Erdős, împreună cu Rényi (Erdős, Rényi, 1963) [2] . Horst Sachs a fost interesat de ei datorită proprietății lor auto-complementare, în timp ce Erdős și Rényi le-au studiat simetriile.

Digrafele Paley sunt analogul direct al graficelor Paley și corespund matricelor de conferință antisimetrice . Ele au fost introduse de Graham și Spencer [3] (și independent de Sachs, Erdős și Renyi) ca o modalitate de a construi turnee cu proprietăți cunoscute anterior doar pentru turnee aleatorii: în digrafele Paley, orice subset de vârfuri este dominat de un vârf.

Definiție

Fie q o putere a unui prim astfel încât q = 1 (mod 4). Rețineți că aceasta implică existența unei rădăcini pătrate de −1 în singurul câmp finit F q de ordinul q .

Fie și V = F q și

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

Această mulțime este bine definită deoarece a − b = −( b − a ), iar −1 este un pătrat al unui număr, ceea ce implică faptul că a − b este un pătrat dacă și numai dacă b − a este un pătrat.

Prin definiție, G = ( V , E ) este un grafic Paley de ordinul q .

Exemplu

Pentru q = 13, câmpul F q este format din numere modulo 13. Numere care au rădăcini pătrate modulo 13:

±1 (rădăcini pătrate ±1 pentru +1, ±5 pentru -1)
±3 (rădăcini pătrate ±4 pentru +3, ±6 pentru −3)
±4 (rădăcini pătrate ±2 pentru +4, ±3 pentru −4).

Astfel, graficul Paley este format din vârfuri corespunzătoare numerelor din intervalul [0,12], iar fiecare vârf x este conectat la șase vecini: x ± 1 (mod 13), x ± 3 (mod 13) și x ± 4 (modul 13).

Proprietăți

Graficele Paley sunt autocomplementare — complementul oricărui graf Paley este izomorf cu graficul însuși. [patru]
Aceste grafice sunt puternic regulate cu parametrii

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

În plus, graficele Paley, de fapt, formează o familie infinită de grafice de conferință .

Valorile proprii ale graficelor Paley sunt numerele (cu multiplicitate 1) și (ambele cu multiplicitate ) și pot fi calculate folosind sume Gauss pătratice . ${\tfrac {1}{2}}(q-1)$ ${\tfrac {1}{2}}(-1\pm {\sqrt {q}})$ ${\tfrac {1}{2}}(q-1)$

Dacă q este prim, limitele numărului izoperimetric i ( G ) sunt:

{\frac {q-{\sqrt {q}}}{4}}\leq i(G)\leq {\sqrt {\left(q+{\sqrt {q}}\right)\left( {\frac {q-{\sqrt {q}}}{2}}\right)}}

Rezultă că i(G)~O(q), iar graficul Paley este un expandator .

Dacă q este prim, graficul său Paley este ciclul hamiltonian al unui grafic circulant .

Graficele Paley sunt cvasialeatoare (Chang et al., 1989) [5] — numărul de cazuri când un grafic de ordin constant se dovedește a fi un subgraf al unui grafic Paley este (în limita pentru q mare ) același cu pentru graficele aleatoare și pentru seturi mari de vârfuri are aproximativ același număr de muchii ca și graficele aleatoare.

Aplicații

Graficul Paley de ordinul al 17-lea este singurul cel mai mare grafic G astfel încât nici el, nici complementul său nu conține un subgraf complet cu 4 vârfuri (Evans și colab. 1981). [6] De aici rezultă că numărul Ramsey R (4, 4) = 18.

Graficul Paley de ordinul 101 este până acum singurul grafic maxim cunoscut G astfel încât nici G și nici complementul său nu conține un subgraf complet cu 6 vârfuri.

Sasakura [7] a folosit graficele Paley pentru a generaliza construcția snopului Horrocks-Mumford .

Paley digraphs

Fie q o putere a unui prim astfel încât q = 3 (mod 4). Atunci câmpul finit F q de ordinul q nu are rădăcină pătrată de −1. Prin urmare, pentru orice pereche ( a , b ) de elemente distincte ale lui F q , fie a − b , fie b − a , dar nu ambele, sunt pătrate. Un digraf Paley este un grafic direcționat cu un set de vârfuri V = F q și un set de arce

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

Digraful Paley este un turneu deoarece fiecare pereche de vârfuri distincte este conectată printr-un arc într-o singură direcție.

Digraful Paley conduce la construirea unor matrici de conferință antisimetrice și geometrie în două plane .

Genul contelui

Cei șase vecini ai fiecărui vârf dintr-un graf Paley de ordinul al 13-lea sunt conectați într-un ciclu, astfel încât graficul să fie local ciclic . Astfel, acest grafic poate fi încorporat într-o triangulație Whitney a unui tor , în care fiecare față este un triunghi și fiecare triunghi este o față. Mai general, dacă orice grafic Paley de ordinul q poate fi imbricat astfel încât toate fețele sale să fie triunghiuri, putem calcula genul suprafeței rezultate folosind caracteristica Euler . Bojan Mohar (2005) a presupus că genul minim al unei suprafețe în care poate fi încorporat un graf Paley este undeva în jurul acestei valori atunci când q este un pătrat și a pus întrebarea dacă astfel de limite pot fi generalizate. În special, Mohar a presupus că graficele Paley de ordin pătrat ar putea fi încorporate în suprafețele genului. ${\tfrac {1}{24}}(q^{2}-13q+24)$

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

unde termenul o(1) poate fi orice funcție a lui q care tinde spre zero pe măsură ce q tinde spre infinit.

White (2001) [8] a găsit o încorporare a graficelor Paley de ordinul q ≡ 1 (mod 8) prin generalizarea înglobării naturale a unui graf Paley de ordinul 9 ca o rețea pătrată pe un tor. Cu toate acestea, genul înglobării Whitney este de aproximativ trei ori mai mare decât limita pe care Mohar a declarat-o în conjectura sa.

Link -uri

↑ REAC Paley. Pe matrici ortogonale // J. Math. Fiz. . - T. 12 . — S. 311–320 .
↑ Grafice asimetrice // Acta Mathematica Academiae Scientiarum Hungaricae. - 1963. - T. 14 , nr. 3–4 . — S. 295–315 . - doi : 10.1007/BF01895716 .
↑ R. L. Graham, J. H. Spencer. O soluție constructivă la o problemă de turneu // Canadian Mathematical Bulletin . - 1971. - T. 14 . — p. 45–48 . - doi : 10.4153/CMB-1971-007-1 .
↑ Horst Sachs. Über selbstkomplementäre Graphen // Publicationes Mathematicae Debrecen. - 1962. - T. 9 . — S. 270–288 .
↑ Chung, Fan RK, R. Graham , RM Wilson,. Graps cvasi-aleatoriu // Combinatorica . - 1989. - T. 9 , nr. 4 . — S. 345–362 . - doi : 10.1007/BF02125347 .
↑ Evans, RJ; Pulham, JR; Sheehan, J. Despre numărul de subgrafe complete conținute în anumite grafice // Journal of Combinatorial Theory, Series B . - 1981. - T. 30 , nr. 3 . — S. 364–371 . - doi : 10.1016/0095-8956(81)90054-X .
↑ Sasakura, Nobuo; Enta, Yoichi; Kagesawa, Masataka. Construcția snopilor reflexi de rangul doi cu proprietăți similare pachetului Horrocks–Mumford // Proc. Japonia Acad., Ser. A. - 1993. - T. 69 , nr. 5 . — S. 144–148 . doi : 10.2183 /pjab.69.144 .
↑ White, A. T. Grafice ale grupurilor pe suprafețe // Interacțiuni și modele. - Amsterdam: North-Holland Mathematics Studies 188, 2001.

Baker, R.D.; Ebert, G. L.; Hemmeter, J.; Woldar, AJ Clicuri maxime în graficele Paley de ordin pătrat // J. Statist. Planifică. deducere. - 1996. - T. 56 . — p. 33–38 . - doi : 10.1016/S0378-3758(96)00006-7 .
Broere, I.; Doman, D.; Ridley, JN Numerele clică și numerele cromatice ale anumitor grafice Paley // Quaestiones Mathematicae. - 1988. - T. 11 . — S. 91–93 . doi : 10.1080 / 16073606.1988.9631945 .

Link- uri externe

Brouwer, Andries E. Paley graps (link inaccesibil - istorie ) . (nedefinit) (link indisponibil)
Mohar, Bojan. PaleyGenus.html Genul de graps Paley (2005). (nedefinit) (link indisponibil)