Paley-gráf

Innen: testwiki
Ugrás a navigációhoz Ugrás a kereséshez

Sablon:Gráf infobox 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 Sablon:Harv. A Paley-gráfokat egymástól függetlenül Sablon:Harvtxt és Sablon:Harvtxt 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 Sablon:Harvtxt 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, Fq-ban a  −1 elemnek létezik négyzetgyöke.

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

E={{a,b} : a−b∈(𝐅q×)2}.

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 Fq 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

srg(q,12(q−1),14(q−5),14(q−1)).
Ezen túl a Paley-gráfok a konferenciagráfok végtelen családját alkotják.
q−q4≤i(G)≤(q+q)(q−q2).
  • 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.[1]
  • 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, Fq-ban, −1-nek nincsen négyzetgyöke. Ebből következően az Fq 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 = Fq, irányított élhalmaza pedig

A={(a,b)∈𝐅q×𝐅q : b−a∈(𝐅q×)2}.

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ó: 124(q2−13q+24). Sablon:Harvs 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

(q2−13q+24)(124+o(1))

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.

Sablon:Harvtxt 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

Jegyzetek

Jegyzetek

Sablon:Jegyzetek

További információk

  1. ↑ Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
A lap eredeti címe: „https://hu.wiki.beta.math.wmflabs.org/w/index.php?title=Paley-gráf&oldid=3873”