Paley grófja

Paley grófja
Earl of Paley 13. rend
Csúcsok	q ≡ 1 mod 4, q egy prímhatvány
borda	q ( q − 1)/4
Tulajdonságok	Erősen rendszeres önkiegészítő konferenciagrafikon
Kijelölés	QR( q )
Médiafájlok a Wikimedia Commons oldalon

A gráfelméletben a Paley-gráfok ( Raymond Paley -ről ) sűrű irányítatlan gráfok, amelyeket egy megfelelő véges mező feltételeiből építenek fel olyan elempárok összekapcsolásával, amelyek másodfokú maradékban különböznek egymástól . A Paley-gráfok a konferencia gráfok végtelen családját alkotják, mivel szorosan kapcsolódnak a szimmetrikus konferenciamátrixok végtelen családjához . A Paley-gráfok lehetőséget adnak a gráfelmélet elméleti eszközeinek alkalmazására a másodfokú maradékok elméletében, és olyan érdekes tulajdonságokkal rendelkeznek, amelyek általánosságban is hasznosak a gráfelméletben.

A Paley gráfok szorosan kapcsolódnak Paley konstrukciójához Hadamard-mátrixok másodfokú maradékokból való felépítésére (Paley, 1933) [1] . Grófként egymástól függetlenül Sachs (Sachs, 1962) és Erdős vezette be őket, Rényivel együtt (Erdős, Rényi, 1963) [2] . Horst Sachs önkiegészítő tulajdonságuk miatt érdeklődött irántuk, Erdős és Rényi pedig szimmetriáikat tanulmányozták.

A Paley-digráfok a Paley-gráfok közvetlen analógjai, és antiszimmetrikus konferenciamátrixoknak felelnek meg . Graham és Spencer [3] (és egymástól függetlenül Sachs, Erdős és Renyi) vezette be őket, hogy olyan versenyeket hozzanak létre , amelyek tulajdonságai korábban csak a véletlenszerű versenyekről ismertek: a Paley-digráfokban a csúcsok bármely részhalmazát valamilyen csúcs uralja.

Definíció

Legyen q egy prím hatványa , amelyre q = 1 (mod 4). Vegyük észre, hogy ez azt jelenti, hogy létezik -1 négyzetgyöke az egyetlen q rendű véges F q mezőben .

Legyen V = F q és

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

Ez a halmaz jól definiált, mert a − b = −( b − a ), és −1 valamilyen szám négyzete, amiből következik, hogy a − b akkor és csak akkor négyzet , ha b − a négyzet.

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

Példa

q = 13 esetén az F q mezőt modulo 13 számok alkotják. Modulo 13 négyzetgyökű számok:

±1 (négyzetgyök +1 esetén ±1, -1 esetén ±5)
±3 (négyzetgyök +3 esetén ±4, -3 esetén ±6)
±4 (négyzetgyök +4 esetén ±2, −4 esetén ±3).

Így a Paley-gráfot a [0,12] intervallum számainak megfelelő csúcsok alkotják, és minden x csúcs hat szomszédhoz kapcsolódik: x ± 1 (mod 13), x ± 3 (mod 13) és x ± 4 (13. mód).

Tulajdonságok

A Paley gráfok önkomplementerek – bármely Paley gráf komplementere izomorf magával a gráftal . [négy]
Ezek a grafikonok erősen szabályosak a paraméterekkel

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

Ezenkívül a Paley-gráfok a konferencia-gráfok végtelen családját alkotják .

A Paley-gráfok sajátértékei a számok (1-es multiplicitással) és (mindkettő multiplicitással ), és kiszámíthatók másodfokú Gauss-összegekkel . ${\tfrac {1}{2}}(q-1)$ ${\tfrac {1}{2}}(-1\pm {\sqrt {q}})$ ${\tfrac {1}{2}}(q-1)$

Ha q prím, akkor az i ( G ) izoperimetrikus szám határai :

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

Ebből következik, hogy i(G)~O(q), és a Paley gráf egy bővítő .

Ha q prím, akkor a Paley-gráfja egy cirkulációs gráf Hamilton-ciklusa .

A Paley-gráfok kvázi véletlenszerűek (Chang et al., 1989) [5] – azon esetek száma, amikor egy állandó sorrendű gráf egy Paley-gráf részgráfjának bizonyul (a nagy q határértékében ) megegyezik véletlen gráfokhoz és nagy csúcshalmazokhoz körülbelül ugyanannyi éle van, mint a véletlen gráfoknak.

Alkalmazások

A 17. rendű Paley-gráf az egyetlen olyan legnagyobb G gráf , amelyben sem ez, sem a komplementere nem tartalmaz teljes 4 csúcsú részgráfot (Evans et al. 1981). [6] Ebből az következik, hogy a Ramsey-szám R (4, 4) = 18.

A 101-es sorrendű Paley-gráf az egyetlen ismert maximális G gráf , amelyben sem G , sem komplementere nem tartalmaz teljes 6 csúcsú részgráfot.

Sasakura [7] Paley-gráfokat használt a Horrocks-Mumford köteg felépítésének általánosítására .

Paley digráfusok

Legyen q egy prím hatványa , amelyre q = 3 (mod 4). Ekkor a q rendű F q véges mezőnek nincs -1 négyzetgyöke. Ezért az F q különböző elemeinek bármely ( a , b ) párja esetén vagy a − b vagy b − a , de nem mindkettő, négyzet. A Paley-digráf egy irányított gráf , amelynek csúcsai V = F q és ívek halmaza

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

A Paley-digráf egy verseny , mert minden egyes csúcspárt egy ív köt össze egy és csak egy irányban.

A Paley-digráf néhány antiszimmetrikus konferencia mátrix és kétsík geometria felépítéséhez vezet .

A gróf nemzetsége

A 13. rendű Paley-gráf minden csúcsának hat szomszédja egy ciklusban van összekapcsolva, így a gráf lokálisan ciklikus . Így ez a gráf beágyazható egy tórusz Whitney-féle háromszögletébe , amelyben minden lap háromszög, és minden háromszög lap. Általánosabban fogalmazva, ha bármely q rendű Paley-gráf beágyazható úgy, hogy minden lapja háromszög legyen, akkor az Euler-karakterisztikával kiszámíthatjuk az eredményül kapott felület nemzetségét . Bojan Mohar (2005) úgy sejtette, hogy egy felület minimális nemzetsége, amelybe egy Paley-gráf beágyazható, valahol ennek az értéknek a környékén van, amikor q négyzet, és feltette a kérdést, hogy általánosíthatók-e ezek a határok. Mohar különösen azt sejtette, hogy a négyzetes sorrendű Paley-gráfok beágyazhatók a nemzetség felületeibe. ${\tfrac {1}{24}}(q^{2}-13q+24)$

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

ahol az o(1) tag lehet q tetszőleges függvénye, amely nullára hajlik, míg q a végtelenbe hajlik.

White (2001) [8] a q ≡ 1 rendű Paley-gráfok beágyazását találta (8. mod) úgy, hogy egy 9. rendű Paley-gráf természetes beágyazását négyzetrácsként egy tóruszba általánosította. A Whitney-beágyazás nemzetsége azonban körülbelül háromszorosa annak a határnak, amelyet Mohar a sejtésében megállapított.

Linkek

↑ REAC Paley. Ortogonális mátrixokon // J. Math. Phys. . - T. 12 . – S. 311–320 .
↑ Aszimmetrikus gráfok // Acta Mathematica Academiae Scientiarum Hungaricae. - 1963. - T. 14 , sz. 3–4 . – S. 295–315 . - doi : 10.1007/BF01895716 .
↑ R. L. Graham, J. H. Spencer. Konstruktív megoldás egy versenyfeladatra // Canadian Mathematical Bulletin . - 1971. - T. 14 . — 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,. Kvázi véletlenszerű graps // Combinatorica . - 1989. - T. 9 , sz. 4 . – S. 345–362 . - doi : 10.1007/BF02125347 .
↑ Evans, RJ; Pulham, JR; Sheehan, J. Az egyes gráfokban található teljes részgráfok számáról // Journal of Combinatorial Theory, B sorozat . - 1981. - T. 30 , sz. 3 . – S. 364–371 . - doi : 10.1016/0095-8956(81)90054-X .
↑ Sasakura, Nobuo; Enta, Yoichi; Kagesawa, Masataka. A Horrocks–Mumford köteghez hasonló tulajdonságokkal rendelkező, második rangú reflexív tárcsa építése // Proc. Japán Akad., Ser. A. - 1993. - T. 69 , sz. 5 . – S. 144–148 . doi : 10.2183 /pjab.69.144 .
↑ White, A. T. Csoportok grafikonjai felületeken // Interakciók és modellek. - Amszterdam: North-Holland Mathematics Studies 188, 2001.

Baker, R. D.; Ebert, G. L.; Hemmeter, J.; Woldar, AJ Maximális klikkek a négyzetes sorrendű Paley-gráfokban // J. Statist. Terv. következtetés. - 1996. - T. 56 . – 33–38 . - doi : 10.1016/S0378-3758(96)00006-7 .
Broere, I.; Doman, D.; Ridley, JN Egyes Paley-gráfok klikkszámai és kromatikus számai // Quaestiones Mathematicae. - 1988. - T. 11 . – S. 91–93 . doi : 10.1080 / 16073606.1988.9631945 .

Külső linkek

Brouwer, Andries E. Paley graps (elérhetetlen link - történelem ) . (határozatlan) (nem elérhető link)
Mohar, Bojan. PaleyGenus.html Genus of Paley graps (2005). (határozatlan) (nem elérhető link)