Csak semmi politika avagy gráfposzt

Eredeti szerző: jotunder

 

       Lovász Lászlót a Magyar Tudományos Akadémia elnökét külső tagjának választotta a Svéd Királyi Tudományos Akadémia. Tegnap tartotta meg a székfoglaló előadását „Nagyon nagy hálózatok matematikája” címmel.

        Matematikus olvasóink most hagyják abba az olvasást, ez nem nekik szól. Megpróbálom nem-matematikusok számára leírni, hogy miről is van szó. Annyi mindenről beszélnek manapság az Akadémiával kapcsolatban, ez itt valami nagyon más lesz. Nem lesz szó Gundel étteremről, emlékműről, O-val kezdődő nevű miniszterelnökökről. Itt most gráfokról lesz szó. Ugyanis Lovász azért mégis csak a gráfokról szól, sőt, és ez még nagyobb dolog, a gráfok kicsit a Lovászról szólnak. 

       Amit itt leírok, az Lovász László és társszerzői elméletének egy egészen kicsiny töredéke, de azt gondolom, hogy egy igen fontos töredéke. Lovásznak nemrég jelent meg egy majd ötszáz oldalas könyve az Amerikai Matematikai Társaság kiadásában Large Networks and Graph Limits címmel, a scholar.google  háromszáz idézetet lát csak a Limits of Dense Graph Sequences című cikkükre, ez egy nagyon nagy téma, amelyről már konferenciákat is rendeztek. Tavaly egy Arbeitgemeinschaft volt a nagy gráfokról Oberwolfachban, ami azt mutatja, hogy nagyon sok tehetséges fiatal is érdeklődik a téma iránt a világban.

       Na, akkor in medias res….

     1.    A nagy gráfok, amelyekről beszélünk végesek ugyan, de óriásiak. Van mondjuk tíz a századikon darab csúcsuk. Az jóval nagyobb, mint a világegyetemben lévő atomok száma. Esélyünk nincs arra, hogy egy ilyen gráfot valaha megértsünk. Az a kérdés, hogyan mondhatunk mégis valamit ezekről az irdatlanul nagy gráfokról és hogyan kell elképzelni őket, amikor már felfoghatatlanul nagyok.

    2.    A legegyszerűbb kérdés, amit a gráfokról feltehetünk az az, hogy hány élük van. Ezt a következő módon is megkérdezhetjük. Ha véletlenül kiválasztjuk egy gráf két csúcsát, akkor mi az esélye annak, hogy össze lesznek kötve. Ha a gráfban nincsenek élek, akkor ez a valószínűség nulla. Ha a gráfban bármely két csúcs össze van kötve, akkor 1. Mi van akkor, ha a gráf úgy néz ki, hogy a baloldalán van százbillió csúcs, a jobboldalán is van, és a két különböző oldalon levő csúcsok össze vannak kötve, az azonos oldalon levők meg nem. Akkor ez a valószínűség lényegében 1/2.

  3.   Ennél bonyolultabb kérdéseket is fel lehet tenni. Mi történik, ha három különböző pontot választunk ki véletlenül? Akkor több eset lehetséges. (A) mindenki mindenkivel össze van kötve.  (B) senki nincs összekötve senkivel. (C) egy élet látunk. (D) két élet látunk. Mi a valószínűsége az (A),(B),(C),(D) eseteknek?  Ezek a valószínűségek valamit elmondanak a gráfról. Valamit már láthatunk belőlük. 

 4.  Ha egy n csúcsú gráfnak sokkal kevesebb (mondjuk egymilliárdszor kevesebb) éle van, mint a teljes gráfnak, akkor ha kiválasztunk három csúcsot, tipikusan egyetlen élet sem fogunk látni. Lovászék elmélete azokról a gráfokról mond el érdekes dolgokat, amelyeknek aránylag sok éle van. Ezeket a gráfokat hívják sűrű gráfoknak. 

5.  Az általános kérdés a következő:  Mi van, ha k (ahol a k lehet 10, 100, 1000 vagy akár százbillió) csúcsot választunk ki véletlenül a gráfból? Mit fogunk látni?  Száz csúcsra nagyon sok különböző gráf rajzolható. Minden egyes ilyen lehetséges G gráfnak van valamilyen csekély valószínűsége egy adott hatalmas gráf esetén, amelyből a száz pontot kiválasztottuk. Ha az irdatlanul nagy gráf neve H, akkor jelöljük ezt a valószínűséget p(k,G,H)-nak. 

6. Lovászék azt akarták megérteni, hogy két ilyen borzasztóan nagy gráf, H1 és H2, mikor „hasonlít” egymásra. Azt a definíciót adták erre, hogy akkor hasonlítanak, ha már elég nagy k értékekre, minden legfeljebb k csúcsú mintagráfra a p(k,G,H1) és a p(k,G,H2) számok már nagyon közel vannak egymáshoz.

7. Gráfok egy H1, H2, H3,…. sorozatát akkor nevezik konvergensnek, ha minden lehetséges k értékre és G gráfra a p(k,G,H1), p(k,G,H2),p(k,G,H3)… sorozat konvergens. Az a kérdés, hová „tartanak” ezek az egyre hatalmasabb gráfok?

8. A naív, de azért matematikailag már elég ügyes megközelítés a következő. Az egyre nagyobb gráfok csúcsai összeállnak egy folytonos szakasszá. Mit jelent az, hogy „él” ?  Miért, mit jelent egy véges gráf? A gráf csúcsainak önmagával vett szorzatának egy részhalmazát jelenti. Akkor pedig ezeknek a folytonos gráfoknak is ilyeneknek kellene lenniük. A szakasz önmagával vett szorzata a négyzet. És akkor ennek a négyzetnek valamilyen részhalmazát nevezzük élhalmaznak.

9. A matematikusok, mint tudjuk, igen te is, nem olvassák a posztot, tehát nem vághatnak közbe, hogy mérhető részhalmazról van szó. Ez a mérhetőség egy kellemetlenség, amivel most nem fogunk foglalkozni, elég az, amivel eddig megterheltük az Olvasót.

10. Amit viszont joggal vethetne közbe a matematikus, de nem veti közbe, mert meg van neki tiltva, az az, hogy amennyiben egy (x,y) pont benne van az „élhalmazban”, akkor legyen benne az (y,x) pont is. A gráfok ilyenek. Ha x össze van kötve y-nal, akkor y is össze van kötve x-szel.

11. Mit jelent egy ilyen folytonos monstrumra az, hogy kiválasztok k csúcsot? Az pont azt jelenti, hogy egyenletesen lerakok k pontot a szakaszra. Bármely két kiválasztott (x,y) párra megnézhetem, hogy az (x,y) pont benne van-e a furcsa folytonos élhalmazomban és így az ilyen folytonos Q gráfokra is definiálható a p(k,G,Q) szám. 

12. Azt mondjuk, hogy a Q folytonos gráf limesze a H1,H2,H3,… sorozatnak, ha minden egyes k-ra és G gráfra igaz az, hogy ( lim_{itoinfty} p(k,G,Hi)=p(k,G,Q) ) .

13. Az igaz, hogy minden Q folytonos gráfhoz található egy igazi gráfokból álló sorozat, amelyik hozzá tart. A Lovász-féle varázslat ott kezdődik, hogy nem minden konvergens gráfsorozathoz tartozik ilyen folytonos gráf Q.

14. Amit Lovászék kitaláltak az eggyel bonyolultabb, mint a folytonos gráf. (pontosan tudom, hogy már az is elég bonyolult)

15. Vegyük egy W függvényt a négyzeten (matematikailag precízebben: egy integrálható ( W:[0,1]times [0,1]to [0,1] ) függvényt, amire W(x,y)=W(y,x).  )

16. Ez mi ez? – kérdi most az Olvasó. Ez nem is gráf. Mit jelent az, hogy W(x,y)=1/2? Ez valami Schrődinger macskája? Hogy egy ketted eséllyel ott van az a nyomorult él, egy ketted eséllyel meg nincs? 

17. Pontosan erről van szó!

18. A Schrődinger macska típusú gráfok (portugálul: graphon) az igazi limeszek. Ha van egy ilyen W macskánk, akkor simán kiszámíthatjuk a p(k,G,W) valószínűséget. Megint kiválasztjuk véletlenül a k pontot a [0,1] szakaszon, de most megállunk egy kicsit macskázni. A kiválasztott x és y pont között nem fogjuk rögtön tudni, hogy van-e él. Fel kell dobnunk egy furcsa érmét, amelyik W(x,y) valószínűséggel az” ÉL”, 1-W(x,y) valószínűséggel a „NEM ÉL” oldalát fogja megmutatni nekünk. Így kétszer is használva a véletlent, kapunk egy gráfot k csúcson. 

19. A fentiek szerint a p(k,G,W) valószínűség  definiálható. Tehát egy Schrődinger macska gráf, akkor limesze egy H1,H2,H3,… sorozatnak, ha ( lim_{itoinfty} p(k,G,Hi)=p(k,G,W) ) .  

20. És ez már a jó fogalom. Minden konvergens sorozathoz van ilyen macska, és minden macskához van hozzá konvergáló sorozata igazi gráfoknak. Itt a vége, fuss el véle. 

<div class='sharedaddy sd-block sd-like jetpack-likes-widget-wrapper jetpack-likes-widget-unloaded' id='like-post-wrapper-192691293-16519559-6ae7a3c0431a5' data-src='https://widgets.wp.com/likes/?ver=14.1#blog_id=192691293&post_id=16519559&origin=www.orulunkvincent.hu&obj_id=192691293-16519559-6ae7a3c0431a5&n=1' data-name='like-post-frame-192691293-16519559-6ae7a3c0431a5' data-title='Like or Reblog'><h3 class="sd-title">Like this:</h3><div class='likes-widget-placeholder post-likes-widget-placeholder' style='height: 55px;'><span class='button'><span>Like</span></span> <span class="loading">Loading...</span></div><span class='sd-text-color'></span><a class='sd-link-color'></a></div>