Paley-gráf

Paley-gráf
A 13 rendű Paley-gráf
Névadó	Raymond Paley
Csúcsok száma	q ≡ 1 mod 4, q prímhatvány
Élek száma	q(q − 1)/4
Egyéb	Erősen reguláris Konferenciagráf Önkomplementer
Jelölés	QR(q)

A matematika, azon belül a gráfelmélet területén a Paley-gráfok olyan sűrű, irányítatlan gráfok, melyek egy megfelelő véges test azon elempárjainak összekötésével keletkeznek, melyek egy kvadratikus maradékban (nem nulla négyzetelemben) különböznek. A Paley-gráfok konferenciagráfok végtelen családját alkotják, melyek szimmetrikus konferenciamátrixok végtelen családjához vezetnek. A Paley-gráfok lehetővé teszik a gráfelméleti eszközök alkalmazását a számelmélethez tartozó kvadratikus maradékokon, egyéb érdekes tulajdonságaik miatt pedig a gráfelméletben szélesebb körben is alkalmazzák őket.

A Paley-gráfok Raymond Paley-ről kapták nevüket. Szorosan kapcsolódnak a kvadratikus maradékokból Hadamard-mátrixokat előállító Paley-féle konstrukcióhoz (Paley 1933). A Paley-gráfokat egymástól függetlenül (Sachs 1962) és (Erdős & Rényi 1963) is bevezette. Sachst az önkomplementer tulajdonságuk érdekelte, míg Erdős és Rényi a szimmetriáikat tanulmányozták.

Az irányított Paley-gráfok (Paley-digráfok) a Paley-gráfok irányított analógiái, melyek antiszimmetrikus konferenciamátrixokhoz vezetnek. Ezeket (Graham & Spencer 1971) vezette be (függetlenül Sachs, Erdős és Rényi munkáitól) olyan tournamentek konstrukciós módszereként, melyek egy korábban csak véletlen tournamenteknek tulajdonított jellemzővel rendelkeznek: egy irányított Paley-gráfban a csúcsok minden kis részhalmazát valamely más csúcs dominálja.

Definíció

Legyen q olyan prímhatvány, melyre q ≡ 1 (mod 4). Tehát q vagy egy pitagoraszi prím (prím, ami kongruens 1 mod 4) vagy egy páratlan, nem pitagoraszi prím páros hatványa. A q kiválasztási módjából következik, hogy a q rendű véges testben, F_q-ban a  −1 elemnek létezik négyzetgyöke.

Ekkor legyen a gráf csúcshalmaza, V = F_q, az élhalmaz pedig:

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

Ha az E tartalmaz egy {a,b} párat, az a két elem bármely sorrendjében szerepelhet. Mivel a − b = −(b − a), és  −1 egy négyzet, a − b pontosan akkor lehet négyzet, ha b − a is négyzet.

Definíció szerint a G = (V, E) a q rendű Paley-gráf.

Példa

Ha q = 13, az F_q test egyszerűen a moduláris aritmetika modulo 13-mal. A következő számok rendelkeznek négyzetgyökkel mod 13:

• ±1 (±1 négyzetgyökei az +1-nek, ±5 a −1-nek)
• ±3 (±4 négyzetgyökei a +3-nak, ±6 a −3-nak)
• ±4 (±2 négyzetgyökei a +4-nek, ±3 a −4-nek).

Tehát a Paley-gráfban a [0,12] egész számoknak megfeleltetünk egy-egy csúcsot, és minden ilyen csúcsot a hozzá tartozó x egész szám hat szomszédjával kötjük össze: x ± 1 (mod 13), x ± 3 (mod 13) és x ± 4 (mod 13).

Tulajdonságok

• A Paley-gráfok önkomplementer tulajdonsággal rendelkeznek: bármely Paley-gráf komplementere izomorf az eredeti gráffal, például azon leképezés útján, ami az x csúcsot xk (mod q)-ba viszi, ahol k bármely nemmaradék mod q (Sachs 1962).
• Ezek a gráfok erősen regulárisak, a következő paraméterekkel:

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

Ezen túl a Paley-gráfok a konferenciagráfok végtelen családját alkotják.

• A Paley-gráfok sajátértékei ${\tfrac {1}{2}}(q-1)$ (1 multiplicitással) és ${\tfrac {1}{2}}(-1\pm {\sqrt {q}})$ (mindkettő ${\tfrac {1}{2}}(q-1)$ multiplicitással), és a kvadratikus Gauss-összeggel számíthatók ki.
• Ha q prím, az i(G) izoperimetrikus számra a következő korlátok ismertek:

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

• Ha q prímszám, a hozzá tartozó Paley-gráf egy Hamilton-körrel rendelkező cirkuláns gráf.
• A Paley-gráfok kvázi-véletlenszerűek (Chung et al. 1989): az a szám, ahányszor az összes lehetséges konstans rendű gráf megjelenik egy Paley-gráf részgráfjaként (nagy q értékek felé tartva) megegyezik a véletlen gráfokéval, és a nagy csúcshalmazok éleinek átlagos száma is megegyezik a véletlen gráfokban mért értékkel.

Alkalmazások

• A 13 rendű Paley-gráf könyvvastagsága 4 és sorba állítási száma (queue number) 3.
• A 17 rendű Paley-gráf az legnagyobb olyan G gráf (és egyedi a maga nemében), amire igaz, hogy sem G, sem G komplementere nem tartalmazza a 4 csúcsú teljes gráfot részgráfként (Evans et al. 1981). Ebből az következik, hogy a Ramsey-szám, R(4, 4) = 18.
• A 101 rendű Paley-gráf a jelenleg ismert legnagyobb G gráf, amire igaz, hogy sem G, sem G komplementere nem tartalmazza a 6 csúcsú teljes gráfot részgráfként.
• Sasukara et al. (1993) a Paley-gráfok segítségével általánosítja a Horrocks–Mumford-nyalábok konstrukcióját.

Irányított Paley-gráfok

Legyen q olyan prímhatvány, melyre q ≡ 3 (mod 4). Ekkor a q rendű véges testben, F_q-ban, −1-nek nincsen négyzetgyöke. Ebből következően az F_q minden (a,b) párja közül (ahol a és b különböző) vagy a − b, vagy b − a négyzetszám, de sohasem mindkettő. Az irányított Paley-gráf az az irányított gráf, melynek csúcshalmaza V = F_q, irányított élhalmaza pedig

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

A Paley-digráf mindig tournament, hiszen a különböző csúcsok között mindig csak egyetlen irányba húzódik irányított él.

Az irányított Paley-gráf segítségével el lehet jutni néhány antiszimmetrikus konferenciamátrix és bisík megszerkesztéséhez.

Génusz

A 13 rendű Paley-gráfban minden csúcsnak hat szomszédja van, melyek egy kört alkotnak; tehát a gráf lokálisan körgráf. Ezért ez a gráf beágyazható egy tóruszba mint Whitney-háromszögelésként, amikor a beágyazás minden tartománya háromszög és a gráf minden háromszöge egy tartomány. Általánosabban, ha a q rendű Paley-gráf beágyazható úgy, hogy minden tartomány háromszög legyen, az eredményül kapott felület génusza az Euler-karakterisztika alapján kiszámítható: ${\tfrac {1}{24}}(q^{2}-13q+24)$. Mohar (2005) sejtése szerint a minimális génuszú felület, amibe egy Paley-gráf beágyazható akkor van közel ehhez a korláthoz, ha q négyzetszám, és keresi a korlát további általánosítását. Specifikusabban, Mohar sejtése szerint a négyzetszám rendű Paley-gráfok beágyazhatók

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

génuszú felületekbe, ahol az o(1) tag q bármilyen függvénye lehet, ami nullához tart, ha q végtelenbe tart.

(White 2001) a 9 rendű Paley-gráf egy tóruszra 3×3-as négyzetrácsba beágyazását általánosítva, a q ≡ 1 (mod 8) rendű Paley-gráfok olyan beágyazásait találta, melyek erősen szimmetrikusan és önduálisak. White beágyazásainak génusza azonban a Mohar sejtésében szereplő korlátnál körülbelül háromszor magasabbak.

Fordítás

• Ez a szócikk részben vagy egészben a Paley graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• (1996) „Maximal cliques in the Paley graph of square order”. J. Statist. Plann. Inference 56, 33–38. o. DOI:10.1016/S0378-3758(96)00006-7.  
• (1988) „The clique numbers and chromatic numbers of certain Paley graphs”. Quaestiones Mathematicae 11, 91–93. o. DOI:10.1080/16073606.1988.9631945.  
• (1989) „Quasi-random graphs”. Combinatorica 9 (4), 345–362. o. DOI:10.1007/BF02125347.  
• (1963) „Asymmetric graphs”. Acta Mathematica Academiae Scientiarum Hungaricae 14 (3–4), 295–315. o. DOI:10.1007/BF01895716.  
• (1981) „On the number of complete subgraphs contained in certain graphs”. Journal of Combinatorial Theory 30 (3), 364–371. o. DOI:10.1016/0095-8956(81)90054-X.  
• (1971) „A constructive solution to a tournament problem”. Canadian Mathematical Bulletin 14, 45–48. o. DOI:10.4153/CMB-1971-007-1.  
• Mohar, Bojan (2005). „Triangulations and the Hajós conjecture”. Electronic Journal of Combinatorics 12, N15. o.  
• Paley, R.E.A.C. (1933). „On orthogonal matrices”. J. Math. Phys. 12, 311–320. o. DOI:10.1002/sapm1933121311.  
• Sachs, Horst (1962). „Über selbstkomplementäre Graphen”. Publicationes Mathematicae Debrecen 9, 270–288. o.  
• (1993) „Construction of rank two reflexive sheaves with similar properties to the Horrocks–Mumford bundle”. Proc. Japan Acad., Ser. A 69 (5), 144–148. o. DOI:10.3792/pjaa.69.144.  
• White, A. T. (2001). „Graphs of groups on surfaces”. Interactions and models, Amsterdam: North-Holland Mathematics Studies 188. 

További információk

• Brouwer, Andries E.: Paley graphs
• Mohar, Bojan: Genus of Paley graphs, 2005