Gyorshir: Fulkerson-dij 2012
Eredeti szerző: jotunder
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.
<div class='sharedaddy sd-block sd-like jetpack-likes-widget-wrapper jetpack-likes-widget-unloaded' id='like-post-wrapper-192691293-16520942-6ae51f6746cd1' data-src='https://widgets.wp.com/likes/?ver=14.1#blog_id=192691293&post_id=16520942&origin=www.orulunkvincent.hu&obj_id=192691293-16520942-6ae51f6746cd1&n=1' data-name='like-post-frame-192691293-16520942-6ae51f6746cd1' 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>
Csodalatos!!! 🙂
Úgy tűnik, folyosón az ékezetek előfordulása nullához konvergál.
…vagy ilyesmi.
Bocs, de ez nem világos:
„a grafban talalhato F-fel izomorf reszgrafok szama osztva a csucsok szamanak k-adik hatvanyaval” — föntebb a részgráfok számát nevezted k-nak; ez így k a k-adikon lenne. A példából viszont k az F-ediken gyanítható — vagy én értem félre az egészet, de nagyon.
@Pásztörperc: A k _nem_ a(z F-fel izomorf) részgráfok _száma_, hanem az F részgráf _pontszáma_. Tehát a háromszögsűrűség esetén a k=3, ezért kell köbre emelni az egész gráf pontszámát. Élsűrűség esetén négyzetre.
Gondolom megkapják a 35 millát, mint amennyi egy lólengés, vagy kalapácsvetés olimpiai aranyért jár.
Vagy tévednék?
Hirkereso idezi:
http://www.hirkereso.hu/blog/friss/
@biohouse: …Szemerédi meg ma vette át a Köztársaság Nagykeresztjét. Ja nem, az Pataki volt…(Nem a fejszámoló, hanem az ufós!)
Komoly poszt alatt miért kérdezel hülyeséget? 🙁
@acs63: A magyar akademia matematikai osztalya tavasszal Szemeredit Szechenyi-nagydijra ajanlotta, de a biralo bizottsag csak egyszeru Szechenyi dijat adott neki, a nagydijat egy Szemeredinel erdemesebbnek adta.
Már megen egy Vincent-irály, aminek a magyarázatából ekkurva szót sem értek…:-)))
@dvhr: Nem is értem, hogy a másik posztban miért panaszkodnak a felsőoktatás színvonaláról, amikor egy (kvázi) Nobel-díjasunk csak a második vonalba fér be (akadémiai szinten), állami szinten meg sem említik. Van itt tudás, tele vagyunk „Magyarországon világhírű” személyekkel…
@acs63:
Ki vette át a Köztársaság Horogkeresztjét? (Kissé tájékozatlan vagyok.)
@misimisi:
Nem Vincent! Jótündér. Szakmai egótúltengéssel. De nem csak ezért szeressük.
(Btw. én sem értek emmukkotsem. Irigylem is Pásztörperc-et. Arra azért befizetnék, hogy maroz vagy Kettes matematikai sejtésekkel dobálja jótündért.)
@nudniq: Hohó, nagy kösz. Éreztem én, hogy vmi nem stimmol, de hogy mi???
@HaKohen: Nyugi, az utolsó harmadából én se értettem semmit, és mint igazolt, a korábbiakat is főleg félre. Én, kérem, csak 1 1*ű mérnökember vagyok…
@HaKohen: A „Nemzeti Együttműködés Konzervatív Csalogánya”, Pataki Attila, az EDDA-s.
Nem is merek arra gondolni, hogy a Békamenettel érdemelte ki, gondolom az ufókkal való kapcsolattartás nagyköveteként folytatott intergalaktikus kommunikációja lehetett az apropó…
Én csak azért nem értettem, mert hiányoztak az ékezetek… :-)))
Mellesleg én már azzal is megelégednék, ha a felnőtt lakosság 90%-a vágná a négy alapműveletet. Azzal elég jól el lehet boldogulni már. 🙂
@dvhr: reszegbroker.tumblr.com/post/29850857766/a-magyar-akademia-matematikai-osztalya-tavasszal
a visszacsatolás:))
@tyder: mármint nem az én tumblr-em,.
@HaKohen: Vizi E. Szilveszter kapta a Széchenyi-nagydíjat:
index.hu/tudomany/2012/03/14/szechenyi_dij/
A közlemény szerint „a központi és perifériás idegrendszer ingerületátvitele, a kémiai ingerületátvitel farmakológiája terén elért, világszerte elismert kutatási eredményeiért, iskolateremtő tudományos tevékenységéért, széleskörű tudományszervezői és tudománydiplomáciai munkásságáért, példaértékű életpályája elismeréseként”.
@Pásztörperc: A „Jótündér”-szintű matekban az a roppant lehangoló, hogy gyakorlatba átültetett hasznosításával sűrűn találkozik az ember (legyen szó gráfokról, kriptográfiáról, vagy csupán relációs adatbáziskezelésről). Aztán megnézve a szóban forgó téma magos matematikai alapjait, az esetek túlnyomó részében rá kell döbbennem, hogy piszkosul kevés vagyok hozzá :-(.
@Pásztörperc: @HaKohen a lovagkeresztet kérdezte. (Szerintem.)
Ami engem felbosszant, hogy a _valóban_világhírű koponyáink _helyett_kevésbé sikeres embereket tüntetnek ki, kisstílű személyeket emelünk piedesztálra. (Vizi szakmai értékelésére nem vállalkoznék, nem vagyok farmakológus.) Hasonlóan ahhoz, amikor középszerű írókat „írófejedelem”-ként aposztrofálnak politikai érzelmek miatt.
Valahogy’ elcsúsztak az értékrendek…
@acs63: Azt megkapják évente úgy kétszázan:
hu.wikipedia.org/wiki/A_Magyar_K%C3%B6zt%C3%A1rsas%C3%A1gi_%C3%89rdemrend_lovagkeresztje#2011
(Köztük az idén Pataki Attila is.)
@ijontichy: +1. Matiematikuskent, 5 eve alkalmazott matemakiai melot vegezve, kis kutatasi hatterrel meg mindig ledobbent h milyen sok osszefuggest nem latok, es nem is fogok latni soha. Egyenkent reszeredmenyeket meg csak-csak, bar nyilvan megerteni sokkal konnyebb, mint belatni. Viszont ATLATNI, tenyleg latni az eredmenyt, na azt nagyon ritkan es nagyon szuk teruleten 🙁
Jo hir viszont, bar nagyon off, h mar nem (ujdonsag h mar Magyarorszag szerint sem) vagyok magyar allampolgar igy aztan az ekezetek miatt nem erdemes panaszkodni 😉
@Pásztörperc: F az egy graf, nem egy szam. a k az az F csucsainak szama.
@Pásztörperc: Esetleg jotunder indíthatna egy Népszerű gráfelmélet-kurzust.
Matolcsy is kaphatna egy ilyen FÜlkerson-díjat az unorthodox matematika alapjainak letevéséért.
@jotunder: Kösz; harmadik olvasatban megértettem…
Hatodik olvasatra (azt hiszem) megértettem mit mond ki az utolsó bekezdés. Köszönöm az ismertetést!
http://www.youtube.com/watch?v=Yq5NOahNc9g
a dijatadas videoja.
az a furcsa, hogy ez egyaltalan nem hir magyarorszagon. jelentos (es mondhatjuk legendas) tudomanyos dijat kapnak magyarok, es sehol semmi.
@jotunder: Nem tudom értesültek-e egyáltalán róla, bekerül-e ez annak a látókörébe aki nem matematikus. Engem pl laikusként érdekel a téma függetlenül attól hogy ki kapta, de ha nem írsz róla akkor nem tudtam volna róla, azt hiszem ezt csak szakmabeliek figyelik igazán és nekik kell továbbítani – esetleg keress meg újságokat egy rövid összefoglalóval.
@tollaszerge: Pont ezt pedzegettem feljebb. JT matematikus, figyeli a szakmáját és jelzi a blogon, ha említésre méltó történik. De ez nem az Ő feladata!
A hivatalból ezzel foglalkozóknak (MTA matematikai osztály) egy ilyen esemény bekövetkeztekor azonnal verni kellene az asztalt az MTI-nél. (Őket meg ezért tartjuk.) Hasonlóan egy sportsikerhez, az ilyen híreknek is prioritást kell(ene) biztosítani!
Tehát vagy nem követik az eseményeket, vagy nem látják szükségét a publicitásnak, vagy nem érdekli őket az esemény, vagy az MTI-nél a takarítónak is nagyobb súlya van, mint nekik.
@acs63: Az MTAnak külön matematikai kutatóintézete van, de mielőtt számonkéred rajtuk érdemes várni egy kicsit. Nem tartom kizártnak hogy ha eddig nem léptek a sajtó felé akkor már dolgoznak rajta, de egynapos átfutás még simán OK – még az ő honlapjukon sincs kint semmi. Tudománynak publicitást adni nem triviális, ha túl akarsz menni azon hogy vki vmilyen díjat kapott akkor érdemes közérthetően összefoglalni hogy miért, na ez a nehéz része, minél absztraktabb annál nehezebb. Amúgy meg augusztus 21-e van, sok minden félgőzzel megy.
@acs63: biztos vagyok benne, hogy az MTA sajtoosztalya ezt meg fogja tenni, de most szabadsagon van mindenki. az a fura, hogy az MTI nem kapta meg. ne gondold, hogy en valami hihetetlenul szemfules vagyok, ez az egyik kedves temam, nyilvan nem arrol van szo, hogy valami tortenik a matematikaban es en naprakeszen mondom rola tutit.
@jotunder: Bezzeg anno a Durer-sejtes „bizonyitasa” vegigszantotta a magyar sajtot.
@acs63: Nehany eve az Elet es Irodalom paratlan oldalan valaki megirta, hogy a magyar sajto mindig huen beszamol arrol, hogy ha az USA-ba leigazolt magyar kosarlabdas ujabb meccset nezett vegig a kispadrol, de arrol szot sem ejt, ha Lovasz ujabb nagy eredmenyt er el.
acs63 2012.08.21. 01:14:30
Teljesen egyetertek.
@tollaszerge: @jotunder: Ez a része rendben lenne, de én az egyszerűen tálalt gyorshírt hiányolom. Azt a részét, amitől dagad a honfi-kebel, nem kell feltétlenül érteniük. (Az a második hullám lehet, a valódi érdeklődőknek.) A Thomas-orsót sem elemzik, sokaknak az is elég, hogy Berki aranyat szerzett. (Láttál szakelemzést a nyertes gyakorlatról valamelyik orgánumban?)
Ezek azok az apróságok, amiatt az átlagembernek fogalma sincs a _valódi_eredményekről, neki Bogár „elemzése” a csúcs. Az eredményeknek a politikusok orra alá dörgöléséhez a nagyközönségre is szükség van.
acs63 2012.08.20. 20:33:11
[A Kossuth es Szechenyi-dij Bizottsagban]
„A jelenlegi testületben pedig „a tudományos, a műszaki, a gazdasági, a művészeti és a kulturális élet” Orbán által kiválasztott „mértékadó képviselői” között három agykutató, két irodalmár, továbbá egy-egy történész, színész, prímás, vegyészmérnök és jogász szerepel. Gyönyörű életkép lehet, ahogy egy agykutató, egy jogász és Semjén Zsolt azon vitatkozik, adjanak-e Kossuth-díjat az aranytorkú Demjén Ferencnek, Széchenyi-díjat Kulcsár Szabó Ernő irodalomtörténésznek vagy Iván László pszichiáternek. Érdekes kérdés, hogy vajon ki konyít akár csak egy kicsit is ebben a csapatban – ötletszerűen kiemelve – a festészethez, az informatikához vagy az építészethez? Az is borzongató persze, hogy a színház- és filmművészethez leginkább Eperjes Károly ért. Természetesen minden bizottsági tag vállaltan jobboldali elkötelezettségű, a tizenöt szavazóból öten a kormány tagjai, Hámori és Pálinkás Józsefek pedig az előző Fidesz-kormányban voltak miniszterek.” (Magyar Narancs)
@Pásztörperc: én meg még egyszerűbb építész, de a matematikai könyveket, cikkeket, írásokat, ha rám jön, úgy olvasom. mint a legnagyobb költők verseit (ha belegondolunk sem azokból, sem pedig ezekből nem érthet meg mindent egy egyszerű halandó). Jó matematikusainkról és matematikusainktól olvasni. Szemerédiről, Lovászról, Szemeréditől. Lovásztól. És ami még jobb, hogy a matemetika talán az egyetlen dolog az emberi szellemtörténetben, amely nemzedéksorok sejtéseinek, bizonyításainak egymásra rakásából épül, egyre épül, tégla a téglára, amint a példa mutatja: Szemerédi sejtését Lovász megfoghatóbbá tesz, mi meg később, gyakorlati emberek, használnii fogjuk, legfeljebb az nyugtalanít bennünket időnként, amit @moses_prophet mond, hogy milyen kevesek is vagyunk a megértésükhöz, bár ettől a felismeréstől azt hiszem a valódi megértésig már csak egy ici-pici többlet energia kellene részünkről.
„Meglehet a prímszámok közötti kapcsolat” (index.hu/tudomany/2012/09/12/meglehet_a_primszamok_kozotti_kapcsolat/).
Örülünk, Vincent?
Érthető ez laikusnak valamilyen módon? Vagy azzá tehető?
@ámbátor: mathoverflow.net/questions/106560/philosophy-behind-mochizukis-work-on-the-abc-conjecture
itt páran elmagyarázzák mit is csinál mochizuki.
az ABC sejtés egy technikai jellegűnek tűnő kérdés, de rengeteg dolog, amit tudnak és borzalmasan nehéz, meg rengeteg dolog amit nem tudnak kijön belőle. en.wikipedia.org/wiki/Abc_conjecture
mochizukit nagyon komoly matematikusnak tartják, ez az egész lehet, hogy valóban jó.
cms.math.ca/MediaReleases/2013/cj-prize
:)))
@jotunder: Gratulalunk Blazsnak a megerdemelt dijhoz, amit nyilvan tovabbiak is fognak meg kovetni.
@dvhr: Bocsanat, Balazs.
Szegedy Surányi tanítvány:
444.hu/2013/05/30/suranyi-laszlo-fazekas/