Jarlen af Paley

Jarlen af Paley
Earl of Paley 13. orden
Toppe	q ≡ 1 mod 4, q er en primærpotens
ribben	q ( q − 1)/4
Ejendomme	Stærkt regelmæssig selvkomplementær konferencegraf
Betegnelse	QR( q )
Mediefiler på Wikimedia Commons

I grafteori er Paley-grafer (opkaldt efter Raymond Paley ) tætte urettede grafer bygget ud fra vilkårene for et passende endeligt felt ved at forbinde par af elementer, der adskiller sig med en kvadratisk rest . Paley-grafer danner en uendelig familie af konferencegrafer , fordi de er tæt forbundet med den uendelige familie af symmetriske konferencematricer . Paley-grafer giver mulighed for at anvende grafteoriens teoretiske værktøjer i teorien om kvadratiske rester og har interessante egenskaber, der gør dem anvendelige til grafteori generelt.

Paley-grafer er tæt forbundet med Paleys konstruktion til at konstruere Hadamard-matricer ud fra kvadratiske rester (Paley, 1933) [1] . De blev introduceret som grever uafhængigt af Sachs (Sachs, 1962) og Erdős sammen med Rényi (Erdős, Rényi, 1963) [2] . Horst Sachs var interesseret i dem på grund af deres selvkomplementære ejendom, mens Erdős og Rényi studerede deres symmetrier.

Paley-digrafer er den direkte analog af Paley-grafer og svarer til antisymmetriske konferencematricer . De blev introduceret af Graham og Spencer [3] (og uafhængigt af Sachs, Erdős og Renyi) som en måde at konstruere turneringer med egenskaber, der tidligere kun var kendt for tilfældige turneringer: i Paley-digrafer domineres enhver delmængde af toppunkter af et eller andet toppunkt.

Definition

Lad q være en potens af et primtal , således at q = 1 (mod 4). Bemærk, at dette indebærer eksistensen af en kvadratrod af −1 i det eneste endelige felt F q af orden q .

Lad også V = F q og

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

Dette sæt er veldefineret, fordi a − b = −( b − a ), og −1 er et kvadrat af et tal, hvilket betyder, at a − b er et kvadrat , hvis og kun hvis b − a er et kvadrat.

Per definition er G = ( V , E ) en Paley-graf af orden q .

Eksempel

For q = 13 er feltet F q dannet af tallene modulo 13. Tal, der har kvadratrødder modulo 13:

±1 (kvadratrødder ±1 for +1, ±5 for -1)
±3 (kvadratrødder ±4 for +3, ±6 for -3)
±4 (kvadratrødder ±2 for +4, ±3 for -4).

Paley-grafen er således dannet af toppunkter svarende til tal i intervallet [0,12], og hvert toppunkt x er forbundet med seks naboer: x ± 1 (mod 13), x ± 3 (mod 13) og x ± 4 (mod 13).

Egenskaber

Paley-grafer er selvkomplementære – komplementet af enhver Paley-graf er isomorfisk til selve grafen. [fire]
Disse grafer er meget regelmæssige med parametre

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

Derudover danner Paley-graferne faktisk en uendelig familie af konferencegrafer .

Egenværdierne for Paley-graferne er tallene (med multiplicitet 1) og (begge med multiplicitet ) og kan beregnes ved hjælp af kvadratiske Gauss-summer . ${\tfrac {1}{2}}(q-1)$ ${\tfrac {1}{2}}(-1\pm {\sqrt {q}})$ ${\tfrac {1}{2}}(q-1)$

Hvis q er primtal, er grænserne for det isoperimetriske tal i ( G ):

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

Det følger, at i(G)~O(q), og Paley-grafen er en ekspander .

Hvis q er primtal, er dens Paley-graf den Hamiltonske cyklus af en cirkulerende graf .

Paley-grafer er kvasi-tilfældige (Chang et al., 1989) [5] - antallet af tilfælde, hvor en graf af konstant orden viser sig at være en undergraf af en Paley-graf, er (i grænsen for store q ) det samme som for tilfældige grafer, og for store sæt af hjørner har den omtrent det samme antal kanter som tilfældige grafer.

Ansøgninger

Paley-grafen af 17. orden er den eneste største graf G , således at hverken den eller dens komplement indeholder en komplet 4-vertex subgraf (Evans et al. 1981). [6] Det følger af dette, at Ramsey-tallet R (4, 4) = 18.

Ordren 101 Paley grafen er indtil videre den eneste kendte maksimale graf G , således at hverken G eller dens komplement indeholder en komplet 6-vertex subgraf.

Sasakura [7] brugte Paley-grafer til at generalisere konstruktionen af Horrocks-Mumford-skjoldet .

Paley digraphs

Lad q være en potens af et primtal , således at q = 3 (mod 4). Så har det endelige felt F q af orden q ikke en kvadratrod på −1. Derfor er enten a − b eller b − a , men ikke begge, kvadrater for ethvert par ( a , b ) af distinkte elementer af F q . En Paley-digraf er en rettet graf med et sæt toppunkter V = F q og et sæt buer

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

Paley-digrafen er en turnering , fordi hvert par af distinkte hjørner er forbundet med en bue i én og kun én retning.

Paley-digrafen fører til konstruktionen af nogle antisymmetriske konferencematricer og to-plans geometri .

Grevens slægt

De seks naboer til hvert toppunkt i en Paley-graf af 13. orden er forbundet i en cyklus, så grafen er lokalt cyklisk . Denne graf kan således indlejres i en Whitney-triangulering af en torus , hvor hver flade er en trekant, og hver trekant er en flade. Mere generelt, hvis en Paley-graf af orden q kan indlejres, således at alle dens flader er trekanter, kan vi beregne slægten af den resulterende overflade ved hjælp af Euler-karakteristikken . Bojan Mohar (2005) formodede, at minimumsslægten af en overflade, hvori en Paley-graf kan indlejres, er et sted omkring denne værdi, når q er et kvadrat, og stillede spørgsmålet om, hvorvidt sådanne grænser kan generaliseres. Især formodede Mohar, at Paley-grafer af kvadratisk orden kunne indlejres i overflader af slægten ${\tfrac {1}{24}}(q^{2}-13q+24)$

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

hvor udtrykket o(1) kan være en hvilken som helst funktion af q , der har en tendens til nul, da q har en tendens til det uendelige.

White (2001) [8] fandt en indlejring af Paley-grafer af orden q ≡ 1 (mod 8) ved at generalisere den naturlige indlejring af en 9. ordens Paley-graf som et kvadratisk gitter på en torus. Imidlertid er slægten af Whitney-indlejringen omkring tre gange højere end den grænse, som Mohar angav i sin formodning.

Eksterne links

Brouwer, Andries E. Paley graps (utilgængeligt link - historie ) . (ubestemt) (utilgængeligt link)
Mohar, Bojan. PaleyGenus.html Slægt af Paley-druer (2005). (ubestemt) (utilgængeligt link)

Jarlen af ​​Paley