Tegnap este Berlinben Lovasz Laszlo es Szegedy Balazs kapta az egyik idei Fulkerson-dijat. Ezt a dijat konkret cikkekert adomanyozzak. Lovasz es Szegedy a Limits of dense graph sequences cimu cikkert kapta a dijat. Ezt a cikket tartjak a kombinatorikaban a graflimesz-elmelet alapcikkenek. A Fulkerson-dij erteket mutatja, hogy olyan alapveto sejtesek megoldasaert adtak, mint pl. a negyszin sejtes, Kepler sejtese a ter legsurubb gombpakolasaert illetve az eros perfekt graf sejtes.
OK. Mi is ez az egesz graflimesz elmelet? Megprobalom ezt valamennyire elmagyarazni.
Mit jelent az, hogy ket graf hasonlo? Ebben az esetben ez valami olyasmit jelent, hogy fajlagosan ugyanannyi kisebb reszgrafot tartalmaz a ket graf. Egy grafnak a fajlagos elsurusege az elei szama osztva a csucsai szamanak a negyzetevel. Fajlagos haromszog surusege a haromszogei szama osztva a csucsai szamanak a kobevel. Es altalaban, ha F olyan veges graf, amelynek k darab csucsa van, akkor a fajlagos F-surusege a grafban talalhato F-fel izomorf reszgrafok szama osztva a csucsok szamanak k-adik hatvanyaval.
Grafok sorozata akkor hasonlit egyre jobban egymashoz (konvergal a suru ertelemben), ha minden egyes veges F grafra az F-surusegeik konvergalnak. A "suru" jelzo arra utal, hogy a kerdeses grafok elszama nem lesz nagysagrendileg kisebb, mint a csucsszamuk negyzete (ha megis az lenne, akkor a definicio szerint egyre kozelebbek lesznek az ures grafokhoz).
A legalapvetobb kerdes az, hogyan lehetne valahogy egy limeszt definialni. A Lovasz-Szegedy limeszobjektum egy, az egysegnegyzeten definalt (merheto) W fuggveny, ami szimmetrikus tehat W(x,y)=W(y,x) es az ertekkeszlete 0 es 1 koze esik. Az Olvasot ez valoszinuleg meglepi, hiszen egy ilyen objektum nem tunik igazi grafnak. Ha csak 0 es 1 erteket vehetne fel akkor valamennyivel "grafabbnak" tunne. A trukk az, hogy egy ilyen W fuggvenyrol is megkerdezhetjuk, mi a valoszinusege annak, hogy harom, veletlenul kivalasztott "csucsa" (azaz harom veletlenul kivalasztott pont az egysegintervallumon) haromszoget hatarozzon meg. Egy veletlen mintavetel ugy mukodik, hogy kivalasztjuk az x,y,z pontokat az egysegintervallumon, majd W(x,y),W(x,z) illetve W(y,z) valoszinusegekkel behuzzuk a megfelelo eleket. Ezt a trukkot barmely veges grafban alkalmazhatjuk. Ily modon definialhatjuk egy W fuggveny F-suruseget. Egy grafsorozat pedig akkor konvergal egy W fuggvenyhez, ha az F-surusegeik minden F grafra a W fuggveny F-surusegehez konvergalnak.
Lovasz es Szegedy bebizonyitottak, hogy minden konvergens grafsorozathoz van limeszfuggveny es vice versa minden limeszfuggvenyhez tart konvergens grafsorozat. Az Olvaso megkerdezheti, hogy miert olyan nagy dolog ez az egesz, es erre is szeretnek valamifele valaszt adni. Nehany honapja mi is megirtuk, hogy Szemeredi Endre Abel-dijat kapott. Szemeredi egyik fontos erdemenye az un. regularitasi lemma, ami nagyon nagy vonalakban azt jelenti, hogy minden graf felbonthato nem tul sok reszre ugy, hogy a reszek kozott nagyon pontosan veletlennek tunik a graf. Lovasz es Szegedy elmelete segitsegevel a Szemeredi-fele regularitasi lemma "vizualizalhato". Azt bizonyithatjuk, hogyha ket graf mar nagyon kozel van egymashoz, akkor a Szemeredi-felbontasuk nagyon hasonlo. Sot. Es ez talan meg fontosabb. Ha egy graf mar eleg kozel van egy W fuggvenyhez, akkor a W fuggveny jo lepcsos fuggveny kozelitesei megvalosithatok, mint Szemeredi felbontasok. A graflimesz elmelet tehat a Szemeredi-fele elmelet tovabbfejlesztesenek es melyebb megertesenek tekintheto.
Elnezest az ekezetek hianyaert, de egy folyoson ulok egy konferencian, es az elet kisse komplikalt.
