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

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 $x_1\mathrm{,}{x}_2\mathrm{,}\text{...}\mathrm{,}{x}_n$. Ha bármely két csúcsot egymástól függetlenül $\frac{1}{2}$ 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 $x_1\mathrm{,}{x}_2\mathrm{,}\text{...}$ szimbólumokkal jelöljük. Ez a halmaz egy gráf csúcshalmaza lesz. Minden $x_i\ne x_j$ 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 $\left(x_i\mathrm{,}{x}_j\right)$ párhoz tartozó érme dobásának eredménye fej, akkor éllel kötjük össze az $x_i$, $x_j$ 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 $U\cap V=\varnothing$, létezik olyan $x\in R$, 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=A_1\cup \text{...}\cup A_n$ páronként diszjunkt részekre. Ekkor van olyan $1\le i\le n$, melyre $A_i$ univerzális.   Bizonyítás. Tegyük fel, hogy $A_1\mathrm{,}{A}_2\mathrm{,}\text{...}\mathrm{,}{A}_n$ egyike sem univerzális.   Ezt $A_1$-ben tanúsítja az $U_1\mathrm{,}{V}_1$ pár, $A_2$-ben az $U_2\mathrm{,}{V}_2$ pár stb.   Legyen $U=\bigcup _{i=1}^n{U}_i$, $V=\bigcup _{i=1}^n{V}_i$. Mivel $R$ univerzális, így az $U\mathrm{,}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 $x\in A_1$. Ekkor $x$ kielégíti az $U_1\mathrm{,}{V}_1$ párra előírt összekötöttségi feltételeket, ami ellentmond $U_1\mathrm{,}{V}_1$ választásának.  $\square$   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=\mathrm{0,1}$-re nyilvánvaló. Tegyük fel, hogy az állítás igaz minden legfeljebb $\left(n-1\right)$-csúcsú gráfra, ahol $n\ge 2$. Legyen $G$ tetszőleges $n$-csúcsú gráf, a csúcsai pedig legyenek $v_1\mathrm{,}\text{...}\mathrm{,}{v}_n$. Jelölje $F\subset G$ a $v_1\mathrm{,}\text{...}\mathrm{,}{v}_{n-1}$ csúcsok által feszített részgráfot. Az indukciós feltevés szerint vannak $R$-nek olyan $r_1\mathrm{,}\text{...}\mathrm{,}{r}_{n-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 $r_1=\phi \left(v_1\right)\mathrm{,}\text{...}\mathrm{,}{r}_{n-1}=\phi \left(v_{n-1}\right)$. Legyen $v_n$ $G$-beli szomszédainak halmaza $U$, nem-szomszédainak halmaza pedig $V$. Ekkor $U\mathrm{,}V\subseteq H$, valamint $U\cap V=\varnothing$. Tehát $\phi \left(U\right)$ és $\phi \left(V\right)$ véges, diszjunkt részhalmazai $R$-nek. Ekkor $R$ univerzalitása miatt van olyan $r_n$ csúcs $R$-ben, mely a $\phi \left(U\right)$-belieknek szomszédja, a $\phi \left(V\right)$-belieknek nem-szomszédja. Ekkor $G$ izomorf az $r_1\mathrm{,}\text{...}\mathrm{,}{r}_n$ 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, $v_1\mathrm{,}{v}_2\mathrm{,}\text{...}$ csúcsokkal. A véges gráfokra alkalmazott indukciót rekurziós eljárássá alakítva kapjuk a bizonyítást. A $v_1$ pont képe legyen tetszőleges $r_1$. Ezután ha a $v_1\mathrm{,}\text{...}\mathrm{,}{v}_{n-1}$ csúcsok képe rendre $r_1=\phi \left(v_1\right)\mathrm{,}\text{...}\mathrm{,}{r}_{n-1}=\phi \left(v_{n-1}\right)$, akkor legyen $U\subseteq \left\{v_1\mathrm{,}\text{...}\mathrm{,}{v}_{n-1}\right\}$ a $v_n$ szomszédainak halmaza, $V\subseteq \left\{v_1\mathrm{,}\text{...}\mathrm{,}{v}_{n-1}\right\}$ pedig a $v_n$ nem-szomszédainak halmaza. Ekkor $\phi \left(U\right)$ és $\phi \left(V\right)$ véges, diszjunkt részei $R$ csúcshalmazának. Tehát $R$ univerzalitása miatt van olyan $r_n$ csúcs $R$-ben, mely a $\phi \left(U\right)$-belieknek szomszédja, a $\phi \left(V\right)$-belieknek nem-szomszédja. Legyen $\phi \left(v_n\right)=r_n$. Világos, hogy a végtelen rekurzió olyan $\phi \left(H\right)\subseteq R$-t ad, ami izomorf $H$-val.  $\square$     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\text{'}$ univerzális gráfok. Ekkor $R$ és $R\text{'}$ izomorfak egymással.   Bizonyítás. A bizonyítás az 1. tétel mintájára történik. Legyenek $R$ csúcsai $r_1\mathrm{,}{r}_2\mathrm{,}\text{...}$, $R\text{'}$ csúcsai $r_1\text{'}\mathrm{,}{r}_2\text{'}\mathrm{,}\text{...}\mathrm{.}$ Célunk ismét az, hogy rekurzívan megadjunk egy $\phi :R\to R\text{'}$ izomorfizmust. Ha azonban pontosan ugyanúgy járnánk el, mint az 1. tétel bizonyításában, akkor $R$-et csak $R\text{'}$ egy feszített részgráfjával tennénk izomorffá, nem magával $R\text{'}$-vel. Ezt a problémát orvosolja a következő technika. Az izomorfizmust ,,oda-vissza'' építjük fel. Vagyis a $\left(2n-1\right)$-edik lépésben $R$ soron következő csúcsának keresünk képet, míg a $2n$-edik lépésben $R\text{'}$ 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 $\phi \left(r_1\right)=r_1\text{'}$. Most vegyük $r_2\text{'}$-t, és keressünk egy $s_2$ csúcsot $R$-ben, ami ugyanúgy kapcsolódik $r_1$-hez, mint $r_2\text{'}$ az $r_1\text{'}$-höz. Legyen $\phi \left(s_2\right)=r_2\text{'}$. Vegyük most $R$ legkisebb indexű csúcsát, aminek még nem találtunk képet. Ha például $r_2=s_2$, akkor ez az $r_3$ csúcs (minden más esetben az $r_2$ a soron következő csúcs.) Általában, tegyük fel, hogy már $2n-2$ darab $R$-beli csúcsnak megtaláltuk a $\phi$-képét, legyen ezek halmaza $S$, $\phi \left(S\right)=S\text{'}$. Vegyük $R\setminus S$-ben a legkisebb indexű csúcsot, jelöljük ezt $s_{2n-1}$-gyel. Legyen $U\subseteq S$ az $s_{2n-1}$ szomszédainak, $V\subseteq S$ pedig $s_{2n-1}$ nem-szomszédainak halmaza. Ekkor $\phi \left(U\right)$ és $\phi \left(V\right)$ diszjunkt, véges részei $R\text{'}$-nek, így $R\text{'}$ univerzalitása miatt van olyan $s_{2n-1}\text{'}\in R\text{'}\setminus S\text{'}$, ami a $\phi \left(U\right)$-belieknek szomszédja, a $\phi \left(V\right)$-belieknek nem-szomszédja. Legyen $\phi \left(s_{2n-1}\right)=s_{2n-1}\text{'}$. Hasonlóan járunk el, ha már $2n-1$ darab $R$-beli csúcsnak megtaláltuk a $\phi$-képét. Akkor $R\text{'}\setminus S\text{'}$-ben vegyük a legkisebb indexű csúcsot, jelöljük ezt $s_{2n}\text{'}$-vel. Legyen $U\text{'}\subseteq S\text{'}$ az $s_{2n}\text{'}$ szomszédainak, $V\text{'}\subseteq S\text{'}$ pedig $s_{2n}\text{'}$ nem-szomszédainak halmaza. Ekkor ${\phi }^{-1}\left(U\right)$ és ${\phi }^{-1}\left(V\right)$ diszjunkt, véges részei $R$-nek, így $R$ univerzalitása miatt van olyan $s_{2n}\in R\setminus S$, ami a ${\phi }^{-1}\left(U\right)$-belieknek szomszédja, a ${\phi }^{-1}\left(V\right)$-belieknek nem-szomszédja. Legyen $\phi \left(s_{2n}\right)=s_{2n}\text{'}$. Világos, hogy a végtelen rekurzió egy izomorfizmust épít fel $R$ és $R\text{'}$ között.  $\square$   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 $R_0\mathrm{,}{R}_1\mathrm{,}\text{...}$ véges gráfokat. Álljon $R_0$ egyetlen csúcsból. Általában, tegyük fel, hogy már megkonstruáltuk az $R_{n-1}$ gráfot, most megkonstruáljuk $R_n$-et. Legyen minden $R_{n-1}$-beli csúcs $R_n$-ben is csúcs, közöttük fussanak az $R_{n-1}$-ből örökölt élek. Továbbá minden $U\subseteq R_{n-1}$ részhalmazra vegyünk fel egy-egy új $v_U$ csúcsot az $R_{n-1}$-beli csúcsokon kívül, aminek $R_{n-1}$ csúcsai közül pontosan az $U$-beliek a szomszédai, az $U$-n kívüliek nem-szomszédai.   A $v_U$ alakú csúcsok között tetszőlegesen vehetjük fel az éleket (például legyen mind összekötve). Így kapjuk az $R_n$ gráfot. Legyen $R=\bigcup _{n=1}^{\infty }{R}_n$. Ennek van értelme: egy csúcs akkor csúcs $R$-ben, ha valamelyik $R_n$-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 $R_n$-ben fut köztük él (ekkor onnantól kezdve mindben fut). Állítjuk, hogy $R$ univerzális. Vegyük ugyanis tetszőleges $U\mathrm{,}V$ véges, diszjunkt részhalmazát a csúcsainak. Ekkor $U\cup V$ benne van valamelyik $R_n$-ben, hiszen véges sok lépés után $U\cup V$ minden csúcsa bekerült a konstrukcióba. Ekkor $R_{n+1}$-nek a $v_U$ csúcsa megfelelő: az $U$-beli csúcsok szomszédai, a $V$-beliek nem-szomszédai.  $\square$   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 $2^{y-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=\left\{y_1\mathrm{,}\text{...}\mathrm{,}{y}_k\right\}$, $V=\left\{z_1\mathrm{,}\text{...}\mathrm{,}{z}_m\right\}$ 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 $y_i$-edik jegye $1$-es ($1\le i\le k$), a hátulról vett $z_j$-edik jegye pedig $0$ ($1\le j\le m$), továbbá minden $y_i$-nél és $z_j$-nél nagyobb. Ilyen szám nyilván létezik. A teljesség kedvéért megjegyezzük, hogy az $\begin{array}{c}{\displaystyle x=\sum _{i=1}^k{2}^{y_i-1}+2^{1+\sum _{i=1}^k{y}_i+\sum _{j=1}^m{z}_j}}\end{array}$ egy megfelelő szám.  $\square$   2. konstrukció. Legyenek a gráf csúcsai a $4k+1$ alakú prímszámok. Két ilyen csúcs, $p\ne q$ 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=\left\{p_1\mathrm{,}\text{...}\mathrm{,}{p}_m\right\}$, $V=\left\{q_1\mathrm{,}\text{...}\mathrm{,}{q}_n\right\}$ a $4k+1$ alakú prímek két diszjunkt halmaza. Olyan $P$ prímet keresünk, ami modulo $p_1\mathrm{,}\text{...}\mathrm{,}{p}_m$ kvadratikus maradék, modulo $q_1\mathrm{,}\text{...}\mathrm{,}{q}_n$ kvadratikus nem-maradék. Ebből a célból minden $p_i$-hez ($1\le i\le m$) kiválasztunk egy $a_i$ kvadratikus maradékot modulo $p_i$, illetve minden $q_j$-hez ($1\le j\le n$) kiválasztunk egy $b_j$ kvadratikus nem-maradékot modulo $q_j$. Legyen $\begin{array}{c}{\displaystyle N=4\left(\prod _{i=1}^m{p}_i\right)\left(\prod _{j=1}^n{q}_j\right)\mathrm{.}}\end{array}$ A kínai maradéktétel [3, 2.6.2. Tétel] alapján van olyan $t$ maradék modulo $N$, amire $t\equiv 1$ modulo $4$, $t\equiv a_i$ modulo $p_i$ és $t\equiv b_j$ modulo $q_j$. 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 $P\equiv t$ modulo $N$. Ekkor $P$ kvadratikus maradék modulo $p_i$, valamint kvadratikus nem-maradék modulo $q_j$.  $\square$   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\mathrm{,}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\mathrm{,}V$ két véges, diszjunkt részhalmaza $X$-nek úgy, hogy $|U\cup V|=n$. Ekkor $\frac{1}{2^n}$ annak a valószínűsége, hogy egy rögzített $X\setminus \left(U\cup V\right)$-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-\frac{1}{2^n}$.   Ezek az események az $X\setminus \left(U\cup V\right)$-beli csúcsokra függetlenek. Tehát $(1-\frac{1}{2^n}{)}^k$ annak a valószínűsége, hogy $k$ darab $X\setminus \left(U\cup V\right)$-beli csúcs mindegyike rossz. Így az egy $0$ valószínűségű esemény, hogy minden $X\setminus \left(U\cup V\right)$-beli csúcs rossz, hiszen $\begin{array}{c}{\displaystyle \underset{k\to \infty }{\overset{}{\text{lim}}}{\left(1-\frac{1}{2^n}\right)}^k=0.}\end{array}$ Tehát 1 annak a valószínűsége, hogy van jó csúcs. Mivel a választható $U\mathrm{,}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\mathrm{,}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.  $\square$   Ú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 $R\to R$ 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 $R\to R$ 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).   ${\displaystyle \begin{array}{c}\hfill {\displaystyle \text{<span style="font-weight: bold;">Maga Péter, </span><br><span style="font-weight: bold;">Pongrácz András </span>}}\hfill \end{array}}$