gráfok
A „Mi is…” rovatban ezúttal a Szemerédi regularitási lemma különböző alakjaival ismerkedhet meg az olvasó. A cikk időzítése nem véletlen: Szemerédi Endre 2012-es Abel-díja után ismét örülhetünk, hiszen 2021 májusában Lovász László vette át ugyanezt a kitüntetést, a „matematikusok Nobel-díját”. A regularitási lemma lehetőséget ad arra, hogy bemutassuk a két világhírű matematikus hatalmas és szerteágazó munkásságának egy-egy kis részletét. Titkos Tamás írása következik…
Lovász László igen gazdag matematikai munkásságának egyik gyöngyszeme a lokális lemma. Jelentőségét felhasználásainak rendkívül nagy száma adja. Magát a lemmát sokan sok irányban általánosították és nagyon sok kombinatorikai (és néhány azon kívüli) probléma megoldásában játszott kulcsszerepet. Tardos Gábor azért választotta cikke témájául a friss Abel-díjas Lovász gyönyörű eredményei közül pont ezt, mert bizonyítása egyszerű és csak elemi módszereket használ. Lássuk a lemma legegyszerűbb formájának teljes bizonyítását a folytatásban…
Erdős Pál egyik kedvenc sejtése volt az Erdős–Faber–Lovász sejtés, és megoldása kétségkívül 2021 egyik fő matematikai szenzációja. Erdősnek szokása volt pénzjutalmat kitűzni sejtései megoldásáért, ezért eredetileg 50 dollárt kínált, majd kisvártatva 500 dollárra emelte az összeget. Ennek ellenére (vagy épp ezért) több mint 40 évet kellett várni a megoldásra. Számos magyar vonatkozása is van a problémának, amelynek közérthető megfogalmazása Gerbner Dániel és Vizer Máté cikkében itt következik.
Bojti Anna társasjáték-tervező és gyerekkönyvíró 2019 óta a Pagony játékkiadójának vezetője. Elsősorban az általános iskolás korosztálynak írja kalandkönyveit. Na de mik is ezek a „lapozgatós” könyvek? És mi közük van a gráfokhoz?
Lovász László 2021-ben megkapott Abel-díja jó alkalmat szolgáltat arra, hogy bemutassuk egyik első világraszóló eredményét: 50 évvel ezelőtt, 1971-ben bizonyította és 1972-ben megjelent cikkében publikálta bizonyítását a perfekt gráf sejtésre. Vizer Máté írásából kiderül, hogy mi motiválta a perfekt gráf fogalmát és magát a sejtést, valamint hogy hogyan kapcsolódik a téma a gráfelmélet korábbi eredményeihez.
Nagy öröm Sós Verát, oly sokunk munkatársát, akadémiai mamáját vagy nagymamáját, a magyar kombinatorikus iskola nagyasszonyát 90. születésnapján köszönteni. De nehéz feladat is, hiszen olyan sok minden tódul az ember fejébe: fontos és gyönyörű matematikai eredményei; elragadó egyetemi és konferencia-előadásai; új tárgyak bevezetése az oktatásba; személyes törődése munkatársaival és tanítványaival; díjai és elismerései; a tudományos közélet odaadó szolgálata itthon és nemzetközi téren. – Lovász László írása.
A perkoláció a statisztikus fizika és a modern valószínűségszámítás egyik legegyszerűbben definiálható, ugyanakkor nagyon mély problémákhoz és általános tanulságokhoz vezető modellje, amiben fázisátmenet történik. A perkolációs modelleknek rendkívül sok változata létezik. Az AMS MathSciNet adatbázisában a „percolation” kifejezés a jelen pillanatban 4273 cikkre illik. Harry Kesten 2006-os Notices of the AMS-beli What is ... percolation? cikke adta a kezdőlökést Mester Péter és Pete Gábor írásának.
Ez a szöveg a ChatGPT 5.5 Thinking modell segítségével készült: ő írta az első verziót, majd visszajelzéseim alapján újra és újra átírta, végül a végső verziót átszerkesztettem és kiegészítettem. Már önmagában ez is jól mutatja, mennyire témába vág, amiről a cikk szól. – Pálvölgyi Dömötör.
Abért Miklós az MTA Rényi Alfréd Matematikai Intézete Algebra osztályának tudományos főmunkatársa, a Csoportok és gráfok kutatócsoport vezetője, a Budapesti Fazekas Mihály Gimnázium egykori diákja. Miért választotta a matematikát és mivel foglalkozik most?
Ez a cikk olyan olvasók számára íródott, akik vagy matematikatanárok, vagy matematikusok, vagy az átlagosnál jobban érdeklődnek a matematika, a matematikusok, és a matematikai élet iránt. A cikkben van egy kis matematika is, de nem sok, és ahol matematikáról írok, ott mindenütt megpróbáltam elkerülni a technikai részleteket. Az első részben a magyar matematikai élet bizonyos vonásairól írok, a másodikban a 2018. július elején rendezett Lovász-konferenciáról. A harmadik részben írok Lovász Lászlónak a matematikai életünkben betöltött szerepéről, és a matematikájáról. (Simonovits Miklós)
2018 áprilisában egy biológus, Aubrey de Grey meglepő című cikket jelentetett meg: „A sík kromatikus száma legalább 5”. Tehát ha ki szeretnénk színezni a sík összes pontját úgy, hogy az egymástól pontosan egységtávolságra lévők különböző színt kapjanak, legalább öt színt kell használnunk. A 60 éve nyitott probléma megfogalmazásának egyszerűsége és szépsége miatt megoldására időről időre megjelennek félkomoly próbálkozások, érthető volt tehát, hogy a gerontológus de Grey cikkét némi szkepticizmussal fogadták, de ez esetben alaptalanul. De Grey talált egy 1581 pontú példát, amelyhez kell legalább 5 szín, és ezt számítógéppel ellenőrizte. (Képünkön Marijin Heule eredménye: 5-kromatikus egységtávolság-gráf 610 csúcson.) Az eredmény komolyabb érdeklődést váltott ki a témával foglalkozók és a laikusok körében is. Az érdekes témakört Frankl Nóra, Hubai Tamás és Pálvölgyi Dömötör mutatja be.
Okostelefonok a ma­te­ma­ti­ka­órán cikksorozatunk 1. részében Koren Balázs ezeket írta: Azzal, hogy beengedjük az okostelefonokat a tanterembe, olyan szellemet szabadítunk el, amit aztán már nehéz, szinte lehetetlen visszatuszkolni a palackba. Az okos­te­le­fo­nok­kal kapcsolatban általános szemlélet, hogy azt a mai Z, illetve alfa generáció képviselői már digitális benn­szü­lött­ként tökéletesen tudják hasz­nál­ni. A közhiedelemmel szemben azonban meg kell jegyeznünk, hogy ez csak részben felel meg a valóságnak. Ebben a részben olyan alkalmazásokat ismerhetünk meg, amelyek segítik mind a tanárok, mind pedig a diákok munkáját a gráfelmélet tanulása, illetve tanítása során.
2017 májusában Budapesten dr. Albert Rékát, a Pennsylvania State University professzorát több alkalommal is felkérték előadónak. Fiatalon, mint általános há­ló­zat­ku­ta­tó, a Barabási–Albert modell megalkotásával hozzájárult a ská­la­füg­get­len hálózatok elemzéséhez. Érdeklődése néhány éve a biológiai hálózatok dinamikája felé irányult, és elsők között alkalmazta rájuk a Boole-logikán alapuló leírást.
Az Európai Kutatási Tanács (ERC) működteti az Európai Unió legnagyobb felfedező kutatásokat támogató pályázati rendszerét. A támogatások odaítélésének egyedüli feltétele a tudományos kiválóság. Olyan vezető kutatók pályázhatnak a kutatók életkorára, nemére és származási or­szá­gá­ra vonatkozó bármely megkötés nélkül, akik Európában tervezik a projektek vég­re­haj­tá­sát. A Rényi Alfréd Matematikai Kutatóintézet ERC Grant támogatását elnyert vezető kutatói közül Szegedy Balázs és Stipsicz András eredményeiről kaphat képet az olvasó. A harmadik interjúban pedig Harangi Viktor Horizont 2020 Kiváló Tudomány – Marie-Skłodowska Curie programját ismerhetjük meg.
Babai László korábban az ELTE algebraprofesszora volt, ma a chicagoi egyetemen tanít számítástudományt és matematikát (ld. a fényképen). 2015 novemberében egy háromrészes chicagoi előadássorozatában jelentette be, hogy kvázipolinomiális algoritmust talált a gráf-izomorfizmus probléma megoldására. Ez egy olyan, egyszerűen megfogalmazható probléma, amit rendkivül nehéz megoldani.
Az expander (kellő erőkifejtéssel) eredeti méreténél sokkal nagyobbra nyújtható. Node: a matematikában az expander nem ez, vagy talán mégis valami hasonló? Peter Sarnak, a Princeton és a New York Egyetem matematika professzora 2004 augusztusában a Notices of the American Mathematical Society folyóiratában írta le az expander alapvető tulajdonságait. Huszár Kristóf fordítása bennünket is megismertet vele. Erőpróbáló!
Mitől találunk szépnek valamit? Az ember ősidők óta keresi a választ erre a kérdésre. Talán mindnyájan érezzük, hogy csakúgy, mint egy andalító dallam élvezetéhez, a szépség megéléséhez is elengedhetetlen a harmónia. A konszonancia és a disszonancia matematikai leírásához Szendi Ágoston matematikus MSc hallgató bevezetett egy mérőszámot és egy távolság fogalmat, amelyet először relatív prím frekvenciák között definiált. Írása egyaránt érdekelheti a zenében jártasakat és járatlanokat is.
A magyarországi matematikának egyik kiemelkedő területe a gráfelmélet. A nemzetközi szak­köny­vek­ben, példatárakban nagyon gyakran talál­koz­ha­tunk hivatkozásokkal magyar ma­te­ma­ti­ku­sok tételeire, hazánkban kitűzött versenyfeladatok bemutatásával. Ezek a példák megmozgatják a fiatalok fantáziáját, hiszen a problémák megoldása szinte minden esetben valamilyen speciális felismerésen, különleges fogalomtársításon alapul, így komoly szellemi kihívást jelent még a matematikailag képzettek számára is. Fonyó Lajos és Fonyóné Németh Ildikó jól hasznosítható, sokszínű anyagot kínál az iskolai szakkörök számára.
A Héttusa 65. feladatának nyomán született írás a geometriáról áttér halmazokra, majd irányított gráfokra, végül Lyndon-szavakra. A Lyndon-szavak felbukkannak az algebra, számelmélet és topológia különféle kérdéseiben, és megjelennek egészen távoli alkalmazási területeken: a számítástudománytól és kriptográfiától kezdve az elméleti fizikán és zenetudományon át egészen a molekuláris biológiáig. Nyitóképünkön Roger Lyndon (a második fotó Halmos Pál felvétele).
A közelmúltban egy több mint fél évszázadon át megoldatlan geometriai sejtést sikerült igazolniuk magyar kutatóknak. A bizonyítás a geometria, a Fourier-analízis, a lineáris programozás, a gráfelmélet és a számítástudomány módszereit ötvözi. Az eredményről 2023 júliusában a tudományos ismeretterjesztés nemzetközi etalonjának számító Quanta Magazine is beszámolt [1]. Ketten az öt szerző közül, Ambrus Gergely és Varga Dániel mutatják be a híres problémát és a bizonyítást.