Paleyův graf - Paley graph - Wikipedia

Paleyův graf
Paleyův graf řádu 13
Pojmenoval podle	Raymond Paley
Vrcholy	q ≡ 1 mod 4, q hlavní síla
Hrany	q(q − 1)/4
Průměr	2
Vlastnosti	Silně pravidelné Konferenční graf Samoobslužné
Zápis	QR (q)
Tabulka grafů a parametrů

v matematika, Paleyovy grafy jsou hustý neorientované grafy postavené z členů vhodného konečné pole spojením dvojic prvků, které se liší o kvadratický zbytek. Paleyovy grafy tvoří nekonečnou rodinu konferenční grafy, které poskytují nekonečnou rodinu symetrických konferenční matice. Paleyovy grafy umožňují graf-teoretický nástroje, které mají být použity na teorie čísel kvadratických zbytků a mají zajímavé vlastnosti, díky nimž jsou obecně užitečnější v teorii grafů.

Paleyovy grafy jsou pojmenovány po Raymond Paley. Jsou úzce spjaty s Paleyova konstrukce pro konstrukci Hadamardovy matice z kvadratických zbytků (Paley 1933 Byly zavedeny jako grafy nezávisle na Sachs (1962) a Erdős & Rényi (1963). Sachs zajímal se o ně kvůli jejich vlastnostem komplementarity Erdős a Rényi studoval jejich symetrie.

Paley digraphs jsou režie analogy Paleyových grafů, které poskytují antisymetrické konferenční matice. Byli představeni Graham & Spencer (1971) (nezávisle na Sachsovi, Erdősovi a Rényim) jako způsob konstrukce turnaje s majetkem, o kterém bylo dříve známo, že je držen pouze náhodnými turnaji: v Paleyově digrafu každý malý podmnožina vrcholů dominuje nějaký jiný vrchol.

Definice

Nechat q být hlavní síla takhle q = 1 (mod 4). To znamená q by měla být buď libovolná síla a Pytagorejský prime (prvočíslo shodné s 1 modem 4) nebo sudá síla lichého nepytagorejského prvočísla. Tato volba q to znamená v jedinečném konečném poli F_q řádu q, prvek −1 má druhou odmocninu.

Teď nech PROTI = F_q a nechte

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

Pokud párA,b} je součástí E, je zahrnut v obou pořadích jeho dvou prvků. Pro, A − b = −(b − A), a -1 je čtverec, ze kterého to vyplývá A − b je čtverec kdyby a jen kdyby b − A je čtverec.

Podle definice G = (PROTI, E) je Paleyův graf řáduq.

Příklad

Pro q = 13, pole F_q je jen celé číslo aritmetické modulo 13. Čísla s druhou odmocninou mod 13 jsou:

• ± 1 (druhé odmocniny ± 1 pro +1, ± 5 pro -1)
• ± 3 (druhé odmocniny ± 4 pro +3, ± 6 pro -3)
• ± 4 (druhé odmocniny ± 2 pro +4, ± 3 pro −4).

V grafu Paley tedy vytvoříme vrchol pro každé z celých čísel v rozsahu [0,12] a spojíme každé takové celé číslo X šesti sousedům: X ± 1 (mod 13), X ± 3 (mod 13) a X ± 4 (mod 13).

Vlastnosti

• Paleyovy grafy jsou samo-doplňkové: doplněk libovolného Paleyova grafu je pro něj isomorfní, např. prostřednictvím mapování, které trvá vrchol X na xk (modq), kde k je jakýkoli neresiduální modq (Sachs 1962 ).
• Tyto grafy jsou silně pravidelné grafy s parametry

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

Kromě toho Paleyovy grafy tvoří nekonečnou rodinu konferenční grafy.

• Vlastní čísla Paleyových grafů jsou ${ displaystyle { tfrac {1} {2}} (q-1)}$ (s multiplicitou 1) a ${ displaystyle { tfrac {1} {2}} (- 13 pm { sqrt {q}})}$ (oba s multiplicitou ${ displaystyle { tfrac {1} {2}} (q-1)}$) a lze jej vypočítat pomocí kvadratická Gaussova suma nebo pomocí teorie silně pravidelných grafů.
• Pokud je q prvočíslo, pak hranice na izoperimetrické číslo i(G) jsou:

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

• Když q je prime, jeho Paleyův graf je a Hamiltonian oběhový graf.
• Paleyovy grafy jsou kvazi náhodný (Chung et al. 1989): počet případů, kdy se každý možný graf konstantního řádu vyskytuje, protože podgraf Paleyova grafu je (v limitu pro velké q) stejné jako u náhodných grafů a velké sady vrcholů mají přibližně stejný počet hran jako v náhodných grafech.

Aplikace

• Paleyův graf řádu 9 je a lokálně lineární graf, a věžní graf a graf 3-3 duoprism.
• Paleyův graf řádu 13 má tloušťka knihy 4 a číslo fronty 3 (Wolz 2018 ).
• Paleyův graf řádu 17 je jedinečný největší graf G takové, že ani jedno G ani jeho doplněk neobsahuje úplný 4-vrcholový podgraf (Evans et al. 1981). Z toho vyplývá, že Ramseyovo číslo R(4, 4) = 18.
• Paleyův graf řádu 101 je v současnosti největším známým grafem G takové, že ani jedno G ani jeho doplněk neobsahuje úplný 6-vrcholový podgraf.
• Sasukara a kol. (1993) používají Paleyovy grafy ke zobecnění konstrukce Balíček Horrocks – Mumford.

Paley digraphs

Nechat q být hlavní síla takhle q = 3 (mod 4). Tedy konečné pole řádu q, F_q, nemá druhou odmocninu z -1. V důsledku toho pro každý pár (A,b) různých prvků F_q, buď A − b nebo b − A, ale ne obojí, je čtverec. The Paley digraph je řízený graf se sadou vrcholů PROTI = F_q a oblouková sada

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

Paley digraph je a turnaj protože každá dvojice odlišných vrcholů je spojena obloukem v jednom a jediném směru.

Paleyův digraf vede ke konstrukci nějaké antisymetrie konferenční matice a dvojplošníkové geometrie.

Rod

Šest sousedů každého vrcholu v Paleyově grafu řádu 13 je spojeno v cyklu; to znamená, že graf je lokálně cyklický. Proto lze tento graf vložit jako a Whitneyho triangulace a torus, ve kterém každý obličej je trojúhelník a každý trojúhelník je obličej. Obecněji, pokud existuje Paleyův graf objednávky q lze vložit tak, aby všechny jeho tváře byly trojúhelníky, mohli bychom vypočítat rod výsledného povrchu pomocí Eulerova charakteristika tak jako ${ displaystyle { tfrac {1} {24}} (q ^ {2} -13q + 24)}$. Mohar  (2005 ) domněnky, že minimální rod povrchu, do kterého lze vložit Paleyův graf, je blízko této hranice v případě, že q je čtverec a otázky, zda by taková vazba mohla platit obecněji. Mohar konkrétně předpokládá, že Paleyovy grafy čtvercového řádu lze vložit do ploch s rodem

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

kde o (1) člen může být jakákoli funkce q to jde na nulu v limitu jako q jde do nekonečna.

White (2001) najde vložení Paleyových grafů řádu q ≡ 1 (mod 8), které jsou vysoce symetrické a sebe-duální, zobecňující přirozené vložení Paleyova grafu řádu 9 jako čtvercovou mřížku 3 × 3 na torusu. Rod Whiteových embeddings je však vyšší přibližně o faktor tři než Moharova domnělá vazba.

Reference

• Baker, R. D .; Ebert, G. L .; Hemmeter, J .; Woldar, A. J. (1996). "Maximální kliky v Paleyově grafu čtvercového řádu". J. Statist. Plán. Odvození. 56: 33–38. doi:10.1016 / S0378-3758 (96) 00006-7.CS1 maint: ref = harv (odkaz)
• Broere, I .; Döman, D .; Ridley, J. N. (1988). Msgstr "Čísla klik a chromatická čísla určitých Paleyových grafů". Quaestiones Mathematicae. 11: 91–93. doi:10.1080/16073606.1988.9631945.CS1 maint: ref = harv (odkaz)
• Chung, Fan R. K.; Graham, Ronald L.; Wilson, R. M. (1989). "Kvazi-náhodné grafy". Combinatorica. 9 (4): 345–362. doi:10.1007 / BF02125347.CS1 maint: ref = harv (odkaz)
• Erdős, P.; Rényi, A. (1963). Msgstr "Asymetrické grafy". Acta Mathematica Academiae Scientiarum Hungaricae. 14 (3–4): 295–315. doi:10.1007 / BF01895716. PAN  0156334.CS1 maint: ref = harv (odkaz)
• Evans, R. J .; Pulham, J. R .; Sheehan, J. (1981). "K počtu úplných podgrafů obsažených v určitých grafech". Journal of Combinatorial Theory. Řada B. 30 (3): 364–371. doi:10.1016 / 0095-8956 (81) 90054-X.CS1 maint: ref = harv (odkaz)
• Graham, R. L.; Spencer, J. H. (1971). "Konstruktivní řešení problému turnaje". Kanadský matematický bulletin. 14: 45–48. doi:10.4153 / CMB-1971-007-1. PAN  0292715.CS1 maint: ref = harv (odkaz)
• Mohar, Bojan (2005). „Triangulace a domněnka Hajóse“. Electronic Journal of Combinatorics. 12: N15. PAN  2176532.CS1 maint: ref = harv (odkaz)
• Paley, R.E.A.C. (1933). "Na ortogonálních maticích". J. Math. Phys. 12 (1–4): 311–320. doi:10,1002 / sapm1933121311.CS1 maint: ref = harv (odkaz)
• Sachs, Horst (1962). „Über selbstkomplementäre Graphen“. Publicationes Mathematicae Debrecen. 9: 270–288. PAN  0151953.CS1 maint: ref = harv (odkaz)
• Sasakura, Nobuo; Enta, Yoichi; Kagesawa, Masataka (1993). „Konstrukce reflexních kladek druhé úrovně s podobnými vlastnostmi jako svazek Horrocks – Mumford“. Proc. Japan Acad., Ser. A. 69 (5): 144–148. doi:10,3792 / pjaa.69.144.CS1 maint: ref = harv (odkaz)
• White, A. T. (2001). Msgstr "Grafy skupin na plochách". Interakce a modely. Amsterdam: North-Holland Mathematics Studies 188.CS1 maint: ref = harv (odkaz)
• Wolz, Jessica (2018). Inženýrské lineární rozložení se SAT. Diplomová práce. University of Tübingen.CS1 maint: ref = harv (odkaz)

externí odkazy

• Brouwer, Andries E. „Paley graphs“.
• Mohar, Bojan (2005). „Grafy rodu Paleyů“.