Cím: Az univerzális gráf
Szerző(k):  Maga Péter ,  Pongrácz András 
Füzet: 2011/május, 258 - 264. oldal  PDF file

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

 
Az univerzális gráf
Bevezető
 

A véletlen gráfok elméleti és gyakorlati jelentősége egyaránt számottevő. Az ismeretségi hálózatok, az internetes weboldalak kapcsolatrendszere mind tekinthetők részben véletlenszerűen kialakuló gráfoknak. Foglalkozzunk csak azzal az esettel, amikor teljesen véletlenszerűen kötjük össze a gráf csúcsait. Legyen adott a véges X halmaz, elemei x1,x2,...,xn. Ha bármely két csúcsot egymástól függetlenül 12 valószínűséggel kötjük össze, akkor egy véletlen gráfot kapunk. Például minden döntésnél feldobunk egy szabályos érmét: ha fej, összekötjük a csúcsokat, ha írás, akkor nem. Számtalan kérdés merül fel a konstrukció kapcsán. Például mekkora valószínűséggel összefüggő egy véletlen gráf? Várhatóan hány szomszédja van egy csúcsnak? Mekkora valószínűséggel kapunk meg egy előre rögzített n-csúcsú gráfot? Utóbbi kérdést tekintve annyi világos, hogy mindegyik gráf pozitív valószínűséggel adódik.
A konstrukció a következő természetes módon általánosítható végtelen alaphalmazra. Adott egy végtelen X halmaz, elemeit az x1,x2,... szimbólumokkal jelöljük. Ez a halmaz egy gráf csúcshalmaza lesz. Minden xixj párhoz tartozik egy szabályos pénzérme. Ezeket a pénzérméket egyszerre feldobjuk úgy, hogy egyik dobás eredménye sem befolyásolja a másikat. Ha az (xi,xj) párhoz tartozó érme dobásának eredménye fej, akkor éllel kötjük össze az xi, xj elemeket, ha pedig írás, akkor nem kötjük őket össze. Ezzel megkapunk egy X gráfot. A fenti kérdések ebben az esetben is értelmesek.
A végtelen véletlen gráfokat sokan vizsgálták, néhány alapvető kérdést tisztáztak is velük kapcsolatban. Az áttörést Erdős Pál és Rényi Alfréd eredménye hozta a témában. Belátták, hogy a fenti konstrukció 1 valószínűséggel egyetlen konkrét gráfot, az univerzális gráfot eredményezi. Ezt a gráfot a szakirodalomban R-rel jelölik, és számtalan néven hivatkoznak rá. Ez nem meglepő: ha egy struktúra valamilyen szempontból ennyire egyedi tulajdonsággal bír, akkor az gyakran a matematika látszólag távoli területein felbukkan. A gráfot modellelméleti kutatások során először Richard Rado fedezte fel, ezért hívják Rado-gráfnak. A valószínűségelméleti konstrukció miatt random gráf vagy véletlen gráf a neve, de szokás Erdős‐Rényi-gráfként is hivatkozni rá.
A továbbiakban az univerzális gráf legfontosabb tulajdonságairól lesz szó. Mindenekelőtt egy világos kombinatorikai leírást adunk róla. Ennek segítségével megkonstruáljuk a gráfot.
Mindvégig arra törekedtünk, hogy a tárgyalás a lehető legkevesebb háttértudással is érthető legyen. Ennek ellenére néhány alapvető gráfelméleti ismeret szükséges, például hogy mi az a gráf, mikor izomorf egymással két gráf, illetve hogy mit értünk feszített részgráf alatt. Az univerzális gráfra adott egyik konstrukciónk felhasznál néhány számelméleti tételt, ezekre pontos hivatkozásokat adunk meg. A közérthetőségre való igyekezetünk szükségszerű következménye, hogy az Erdős‐Rényi-tétel precíz bizonyítását nem mutathatjuk be. Hipotetikusan, gondos valószínűségelméleti megalapozás nélkül (mely messze meghaladná ezen írás terjedelmét) érvelünk, ugyanakkor azt reméljük, az alapgondolatot így is sikerül hiánytalanul közvetítenünk.
 

 
Definíció és néhány egyszerű következmény

Mostantól végtelen alatt mindig megszámlálható végtelent értünk, és nem foglalkozunk a megszámlálható végtelennél nagyobb csúcsszámú gráfokkal.
 

1. definíció. Azt mondjuk, hogy az R gráf univerzális, ha R csúcshalmaza nemüres, és tetszőleges U, V véges csúcshalmazaira, melyekre UV=, létezik olyan xR, melyre x minden U-beli csúcsnak szomszédja (azaz össze van kötve), és minden V-beli csúcsnak nem-szomszédja (a szomszédság és a nem-szomszédság csak kölönböző csúcsokra vannak értelmezve: egy csúcs saját magának sem szomszédja, sem nem-szomszédja).
A definíciónak van néhány egyszerű következménye, ezeket feladatok formájában közöljük.
 

1. feladat. Bizonyítsuk be, hogy nem létezik véges univerzális gráf.
Ennél több is igaz. Nevezetesen:
 

2. feladat. Bizonyítsuk be, hogy egy univerzális gráfban minden csúcs foka végtelen.
A következő állítás már rávilágít az univerzális gráf egy érdekességére.
 

1. állítás. Legyen R egy univerzális gráf. Tegyük fel, hogy a csúcshalmazt felbontjuk R=A1...An páronként diszjunkt részekre. Ekkor van olyan 1in, melyre Ai univerzális.
 

Bizonyítás. Tegyük fel, hogy A1,A2,...,An egyike sem univerzális.
 
Ezt A1-ben tanúsítja az U1,V1 pár, A2-ben az U2,V2 pár stb.
 
Legyen U=i=1nUi, V=i=1nVi. Mivel R univerzális, így az U,V párhoz létezik olyan x csúcs R-ben, ami össze van kötve mnden U-beli elemmel és nincs összekötve egyetlen V-beli csúccsal sem. Az általánosság megszorítása nélkül tegyük fel, hogy xA1. Ekkor x kielégíti az U1,V1 párra előírt összekötöttségi feltételeket, ami ellentmond U1,V1 választásának.  
 

Egy univerzális gráfba minden véges, sőt, minden végtelen gráf is beágyazható, ezt fogalmazza meg a következő állítás.
 

1. tétel. Legyen R univerzális, G pedig tetszőleges véges gráf. Ekkor R-nek van olyan feszített részgráfja, mely G-vel izomorf. Tegyük fel, hogy H végtelen gráf. Ekkor R-nek van olyan feszített részgráfja, mely H-val izomorf.
 

Bizonyítás. Teljes indukcióval bizonyítunk G csúcsszáma szerint. Legyen ez a csúcsszám n. Az állítás n=0,1-re nyilvánvaló. Tegyük fel, hogy az állítás igaz minden legfeljebb (n-1)-csúcsú gráfra, ahol n2. Legyen G tetszőleges n-csúcsú gráf, a csúcsai pedig legyenek v1,...,vn. Jelölje FG a v1,...,vn-1 csúcsok által feszített részgráfot. Az indukciós feltevés szerint vannak R-nek olyan r1,...,rn-1 csúcsai, melyek által feszített részgráf F-fel izomorf. A csúcsok esetleges átszámozásával feltehetjük, hogy ez az izomorfizmus éppen r1=φ(v1),...,rn-1=φ(vn-1). Legyen vn G-beli szomszédainak halmaza U, nem-szomszédainak halmaza pedig V. Ekkor U,VH, valamint UV=. Tehát φ(U) és φ(V) véges, diszjunkt részhalmazai R-nek. Ekkor R univerzalitása miatt van olyan rn csúcs R-ben, mely a φ(U)-belieknek szomszédja, a φ(V)-belieknek nem-szomszédja. Ekkor G izomorf az r1,...,rn csúcsok által feszített részgráffal. Ezzel a véges gráfokra vonatkozó állítást beláttuk.
Legyen most H végtelen gráf, v1,v2,... csúcsokkal. A véges gráfokra alkalmazott indukciót rekurziós eljárássá alakítva kapjuk a bizonyítást. A v1 pont képe legyen tetszőleges r1. Ezután ha a v1,...,vn-1 csúcsok képe rendre r1=φ(v1),...,rn-1=φ(vn-1), akkor legyen U{v1,...,vn-1} a vn szomszédainak halmaza, V{v1,...,vn-1} pedig a vn nem-szomszédainak halmaza. Ekkor φ(U) és φ(V) véges, diszjunkt részei R csúcshalmazának. Tehát R univerzalitása miatt van olyan rn csúcs R-ben, mely a φ(U)-belieknek szomszédja, a φ(V)-belieknek nem-szomszédja. Legyen φ(vn)=rn. Világos, hogy a végtelen rekurzió olyan φ(H)R-t ad, ami izomorf H-val.  
 

 
Az univerzális gráf egyértelműsége

A következő tétel azt mondja ki, hogy izomorfizmus erejéig legfeljebb egyetlen univerzális gráf lehet.
 

2. tétel. Tegyük fel, hogy R és R' univerzális gráfok. Ekkor R és R' izomorfak egymással.
 

Bizonyítás. A bizonyítás az 1. tétel mintájára történik. Legyenek R csúcsai r1,r2,..., R' csúcsai r1',r2',.... Célunk ismét az, hogy rekurzívan megadjunk egy φ:RR' izomorfizmust. Ha azonban pontosan ugyanúgy járnánk el, mint az 1. tétel bizonyításában, akkor R-et csak R' egy feszített részgráfjával tennénk izomorffá, nem magával R'-vel. Ezt a problémát orvosolja a következő technika. Az izomorfizmust ,,oda-vissza'' építjük fel. Vagyis a (2n-1)-edik lépésben R soron következő csúcsának keresünk képet, míg a 2n-edik lépésben R' soron következő csúcsának keresünk ősképet. Ezzel garantáljuk, hogy a konstruált leképezés bijektív.
Legyen tehát φ(r1)=r1'. Most vegyük r2'-t, és keressünk egy s2 csúcsot R-ben, ami ugyanúgy kapcsolódik r1-hez, mint r2' az r1'-höz. Legyen φ(s2)=r2'. Vegyük most R legkisebb indexű csúcsát, aminek még nem találtunk képet. Ha például r2=s2, akkor ez az r3 csúcs (minden más esetben az r2 a soron következő csúcs.)
Általában, tegyük fel, hogy már 2n-2 darab R-beli csúcsnak megtaláltuk a φ-képét, legyen ezek halmaza S, φ(S)=S'. Vegyük RS-ben a legkisebb indexű csúcsot, jelöljük ezt s2n-1-gyel. Legyen US az s2n-1 szomszédainak, VS pedig s2n-1 nem-szomszédainak halmaza. Ekkor φ(U) és φ(V) diszjunkt, véges részei R'-nek, így R' univerzalitása miatt van olyan s2n-1'R'S', ami a φ(U)-belieknek szomszédja, a φ(V)-belieknek nem-szomszédja. Legyen φ(s2n-1)=s2n-1'. Hasonlóan járunk el, ha már 2n-1 darab R-beli csúcsnak megtaláltuk a φ-képét. Akkor R'S'-ben vegyük a legkisebb indexű csúcsot, jelöljük ezt s2n'-vel. Legyen U'S' az s2n' szomszédainak, V'S' pedig s2n' nem-szomszédainak halmaza. Ekkor φ-1(U) és φ-1(V) diszjunkt, véges részei R-nek, így R univerzalitása miatt van olyan s2nRS, ami a φ-1(U)-belieknek szomszédja, a φ-1(V)-belieknek nem-szomszédja. Legyen φ(s2n)=s2n'. Világos, hogy a végtelen rekurzió egy izomorfizmust épít fel R és R' között.  
 

Tehát míg eddig úgy beszéltünk univerzális gráfokról, hogy egy univerzális gráf, mostantól úgy fogalmazunk majd, hogy az univerzális gráf. Felmerül azonban a kérdés, hogy nem beszélünk-e véletlenül a semmiről, azaz létezik-e egyáltalán univerzális gráf. A következő pontban erre a kérdésre adunk igenlő választ.
 

 
Az univerzális gráf létezése

 

3. tétel. Létezik olyan R gráf, ami univerzális.
 

Bizonyítás. Rekurzívan megkonstruáljuk az R0,R1,... véges gráfokat. Álljon R0 egyetlen csúcsból. Általában, tegyük fel, hogy már megkonstruáltuk az Rn-1 gráfot, most megkonstruáljuk Rn-et. Legyen minden Rn-1-beli csúcs Rn-ben is csúcs, közöttük fussanak az Rn-1-ből örökölt élek. Továbbá minden URn-1 részhalmazra vegyünk fel egy-egy új vU csúcsot az Rn-1-beli csúcsokon kívül, aminek Rn-1 csúcsai közül pontosan az U-beliek a szomszédai, az U-n kívüliek nem-szomszédai.
 
vU alakú csúcsok között tetszőlegesen vehetjük fel az éleket (például legyen mind összekötve). Így kapjuk az Rn gráfot. Legyen R=n=1Rn. Ennek van értelme: egy csúcs akkor csúcs R-ben, ha valamelyik Rn-ben csúcs (ekkor onnantól kezdve mindben az), és két csúcs között pontosan akkor fut él R-ben, ha valamelyik Rn-ben fut köztük él (ekkor onnantól kezdve mindben fut).
Állítjuk, hogy R univerzális. Vegyük ugyanis tetszőleges U,V véges, diszjunkt részhalmazát a csúcsainak. Ekkor UV benne van valamelyik Rn-ben, hiszen véges sok lépés után UV minden csúcsa bekerült a konstrukcióba. Ekkor Rn+1-nek a vU csúcsa megfelelő: az U-beli csúcsok szomszédai, a V-beliek nem-szomszédai.  
 

A fejezetet egy feladattal zárjuk.
 

3. feladat. Bizonyítsuk be, hogy az univerzális gráf izomorf a komplementerével.
 
 
,,Konkrét'' konstrukciók

 

A 3. tétel bizonyítása után megmarad az a hiányérzetünk, hogy bár a bizonyítás konstruktív, mégsem tudjuk egyszerre megadni az egész gráfot. Ebben a részben megadunk néhány egészen konkrét gráfot, amelyek univerzálisak (ekkor egymással, illetve a 3. tételben konstruálttal izomorfak a 2. tétel szerint).
 
1. konstrukció. Legyenek a gráf csúcsai a pozitív egész számok. Két csúcs, x>y között pontosan akkor fusson él, ha x-nek a 2-es számrendszerbeli alakjában a 2y-1-nek megfelelő helyiértéken (hátulról számítva az y-adik helyen, utolsó a 0. hely) 1-es áll. Ez volt Rado konstrukciója [4].
 

textbf2. állítás. Az 1. konstrukció során kapott R gráf univerzális.
 

Bizonyítás. Legyenek adottak az U={y1,...,yk}, V={z1,...,zm} diszjunkt, véges részhalmazai a pozitív egészeknek. Írjunk fel egy olyan x számot, melynek a 2-es számrendszerbeli alakjának hátulról vett yi-edik jegye 1-es (1ik), a hátulról vett zj-edik jegye pedig 0 (1jm), továbbá minden yi-nél és zj-nél nagyobb. Ilyen szám nyilván létezik. A teljesség kedvéért megjegyezzük, hogy az
x=i=1k2yi-1+21+i=1kyi+j=1mzj
egy megfelelő szám.  
 

2. konstrukció. Legyenek a gráf csúcsai a 4k+1 alakú prímszámok. Két ilyen csúcs, pq között pontosan akkor fusson él, ha p kvadratikus maradék (egy q-val nem osztható szám négyzete) modulo q. Ez a tulajdonság szimmetrikus, vagyis ha p kvadratikus maradék modulo q, akkor q is kvadratikus maradék modulo p. Ez az állítás a kvadratikus reciprocitási tétel [3, 4.2.3. Tétel] következménye. A reflexivitásra szükségünk van, hiszen p és q között pontosan akkor fut él, ha q és p között fut.
 

3. állítás. A 2. konstrukcióval kapott R gráf univerzális.
 

Bizonyítás. Legyen U={p1,...,pm}, V={q1,...,qn} a 4k+1 alakú prímek két diszjunkt halmaza. Olyan P prímet keresünk, ami modulo p1,...,pm kvadratikus maradék, modulo q1,...,qn kvadratikus nem-maradék. Ebből a célból minden pi-hez (1im) kiválasztunk egy ai kvadratikus maradékot modulo pi, illetve minden qj-hez (1jn) kiválasztunk egy bj kvadratikus nem-maradékot modulo qj. Legyen
N=4(i=1mpi)(j=1nqj).
A kínai maradéktétel [3, 2.6.2. Tétel] alapján van olyan t maradék modulo N, amire t1 modulo 4, tai modulo pi és tbj modulo qj. Ez a t relatív prím maradék N-hez, így a Dirichlet-tétel [5, 4.2. Függelék] alapján van olyan 4k+1 alakú P prím, melyre Pt modulo N. Ekkor P kvadratikus maradék modulo pi, valamint kvadratikus nem-maradék modulo qj.  
 

Ezen konkrét konstrukciók tehát oly módon realizálják az univerzális gráfot, hogy két csúcs ismeretében meg tudjuk mondani, hogy van-e közöttük él, illetve diszjunkt, véges U,V csúcshalmazokhoz tudunk találni olyan csúcsot, ami az U-beliekkel össze van kötve, a V-beliekkel nincs.
 
 
A véletlen gráf

 
Most térjünk vissza a bevezetőben leírt szituációhoz. Készítsünk el egy végtelen véletlen gráfot. Vizsgáljuk meg, mi köze van ennek a véletlen gráfnak az univerzális gráfhoz.
Legyen U,V két véges, diszjunkt részhalmaza X-nek úgy, hogy |UV|=n. Ekkor 12n annak a valószínűsége, hogy egy rögzített X(UV)-beli csúcs ,,jó'', vagyis minden U-beli csúcsnak szomszédja, minden V-beli csúcsnak nem-
szomszédja. Vagyis annak valószínűsége, hogy ,,rossz'' (tehát nem jó), 1-12n.
 
Ezek az események az X(UV)-beli csúcsokra függetlenek. Tehát (1-12n)k annak a valószínűsége, hogy k darab X(UV)-beli csúcs mindegyike rossz. Így az egy 0 valószínűségű esemény, hogy minden X(UV)-beli csúcs rossz, hiszen
limk(1-12n)k=0.
Tehát 1 annak a valószínűsége, hogy van jó csúcs. Mivel a választható U,V véges, diszjunkt csúcshalmazok száma csak megszámlálhatóan végtelen, ezért szintén 1 annak a valószínűsége, hogy minden U,V párhoz van megfelelő csúcs. Összességében tehát a véletlen gráf 1 valószínűséggel univerzális. Ezt összevetve a 2. tétellel a következőt kapjuk.
 
4. tétel (Erdős‐Rényi, [2]). Egy végtelen, véletlen gráf 1 valószínűséggel izomorf az univerzális gráffal. Két végtelen, véletlen gráf 1 valószínűséggel izomorf egymással.  
 

Újabb szokatlan jelenséggel találkoztunk: a véges (legalább 2-pontú) gráfok között nincs olyan izomorfia-osztály, ami 1 valószínűséggel előállna véletlenszerű élválasztás esetén.
 
 
Kitekintés

 
Az univerzális gráf néhány további tulajdonságáról ‐ tartalmi és terjedelmi okokból ‐ csak címszavakban beszélhetünk.
Csoportelméleti vonatkozásként megemlítjük, hogy az univerzális gráf szimmetriákban rendkívül gazdag. Például bármelyik éle átvihető bármelyik másikba egy alkalmas RR izomorfizmus segítségével. Valójában ennél sokkal több is igaz: bármely véges része átvihető bármely véges részébe egy RR izomorfizmussal, feltéve hogy ennek nincs nyilvánvaló akadálya (nyilván a két véges résznek izomorfnak kell lennie egymással).
Nagyon érdekes az a modellelméleti tény, hogy ha egy (gráfelméleti) állítás igaz az univerzális gráfban, akkor ,,majdnem minden'' véges gráfban igaz; ha hamis az univerzális gráfban, akkor ,,majdnem minden'' véges gráfban hamis.
Mindezekről (és még rengeteg egyéb különlegességről) Peter J. Cameron [1, 5. fejezet] angol nyelvű könyvében olvashatunk.
 
 
Hivatkozások

[1]Cameron, P., J., Permutation Groups, LMS Student Text 45. Cambridge University Press (Cambridge, 1999).
[2]Erdős, P. and Rényi, A., Asymmetric graphs, Acta Math. Acad. Sci. Hungar., 14 (1963), 295‐315.
[3]Freud, R. ‐ Gyarmati, E., Számelmélet, Nemzeti Tankönyvkiadó (Budapest, 2000).
[4]Rado, R., Universal graphs and universal functions, Acta Arith., 9 (1964), 331‐340.
[5]Szalay, M., Számelmélet, SMT sorozat, Typotex kiadó (Budapest, 1998).


 
Maga Péter, 
Pongrácz András