Kutatás
Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar
Discrete mathematics
Activity of the research group:
Fundamental research in graph theory, hypergraphs, combinatorics, combinatorial optimization, combinatorial number theory, game theory, database theory, rigidity of graphs and structures, additive combinatorics, combinatorial geometry, search theory, extremal set systems, relation between databases and code theory, graph coloring, behaviour of graph parameters in product graphs
Recent results:
Péter Pach Pál developed a new version of the polynomial method in 2016 together with Croot and Lev. This new method has led to the solution of famous problems such as the cap set problem or the Erdős-Szemerédi sunflower conjeture. Since then, the method has had many applications, such as exact bound for Green’s lemma of “arithmetical triangle removal” (Fox-Lovász), Sárközy’s theorem for polynomials over finite bodies (Green), and many others. The article was published in the most prestigious mathematical journal, Annals of Mathematics, and Fields Medal-winning mathematicians Gowers, Tao, and other leading mathematicians such as Cameron and Kalai have also analyzed it on their blogs.
Géza Tóth, together with János Pach and Gábor Tardos, proved far-reaching generalizations of the Crossing Lemma to multigraphs under various natural conditions.
Gábor Wiener, together with Peter Dameschke and Azam Sheikh Muhammad, laid the combinatorial foundations of a new, practical and well-used strict group testing model, which was published in the Journal of Combinatorial Theory A, one of the leading combinatorial journals.
Gábor Simonyi, together with Gábor Tardos, gave a partial (complete in the 4-chromatic case) characterisation of the colour-critical edges of Schrijver graphs.
Gyula Katona and László Papp, in a joint work with Ervin Győri, gave lower and upper bounds on the optimal pebbling number of large grids.
Gyula Katona, with Kitti Varga, achieved several significant results in the study of minimally tough graphs.
Recent projects:
MTA Lendület • OTKA
International relations:
Ibaraki University, Japan • Lancaster University, UK • University of Haifa, Israel • University of Warwick, UK • Ghent University • Yokohama National University • University of British Columbia, Canada • Sapienza – Universitá di Roma
Industrial partners:
Morgan Stanley • Lynx Analytics
Algorithm theory
Activity of the research group:
Kombinatorikus algoritmusok. Klasszikus és kvantumalgoritmusok, bonyolultságelméleti és paraméteres bonyolultságos megközelítések. Ezen belül pl. társadalmi választások, fair hozzárendelések, stabil és népszerű párosítások, hálózatok megbízhatóságának vizsgálata kombinatorikus és játékelméleti módszerekkel. Különböző kvantumos megközelítések (algoritmus, QUBO, kvantumbolyongás) vizsgálata. Logikai és deklaratív programozás.
Recent results:
Számos eredményünk született a fair hozzárendelés területén: többek között bizonyítottuk, hogy 3 ágens esetén az irigység-mentes allokáció keresése NP-teljes feladat (ezzel egy 5 évig nyitott kérdést megválaszolva), ugyanakkor arányos allokáció keresése polinom idejű algoritmussal megoldható; ez utóbbi kérdést általános számú ágens esetén is körbejártuk, feltérképeztük annak paraméteres bonyolultságát és approximálhatóságát. Vizsgáltuk a stabil párosítás probléma sok-paraméteres bonyolultságát abban az esetben, ahol bizonyos ágensek fedését írhatjuk elő: öt vizsgált paraméter minden kombinációjára sikerült a probléma bonyolultságát meghatározni. Foglalkoztunk még a népszerű fenyvesek problémájával is, hatékony egzakt és közelítő algoritmusok megadása mellett számos nehézségi eredményt is bizonyítottunk.
Bizonyítottunk egy olyan új eredményt, aminek segítségével a hálózatok megbízhatóságának játékelméleti eszközökkel való mérésére vonatkozó korábban ismert, matroidelméleti módszereket sikerült a greedoidoknak egy, a matroidoknál bővebb osztályára kiterjeszteni.
Kvantumalgoritmusok körében vizsgáltuk a Fourier-transzformáció alkalmazásanak határait bizonyos algebrai feladatokra. Foglalkoztunk a kvantumalgoritmusok egy fajta használatával a gépi tanulásban, megmutatva, hogy egy mások által javasolt módszer nem sok előnyt ad a klasszikus eljárásokhoz képest. Vizsgáljuk, hogyan lehet klasszikus problémákat a D-Wave (korábbi) kvantumszámítógépébe beágyazni, az ott használt QUBO (quantum unconstrained binary optimization) feladatra átfordítani.
Recent projects:
OTKA
International relations:
Hamburg University of Technology • University of Tübingen • Université Paris Diderot – Paris, Centre for Quantum Technologies • University of Singapore
Diszkrét matematika
A kutatócsoport tevékenysége:
Alapkutatások a gráfelmélet, hipergráfok, kombinatorika, kombinatorikus optimalizálás, kombinatorikus számelmélet, játékelmélet, adatbázisok elmélete, gráfok és szerkezetek merevsége, additív kombinatorika, kombinatorikus geometria, kereséselmélet, extremális halmazrendszerek, adatbázisok és kódelmélet kapcsolata, gráfszínezések, gráfparaméterek viselkedése szorzatgráfokban témakörökben
Eredmények:
Pach Péter Pál 2016-ban Croottal és Levvel közösen kidolgozta a polinom módszer egy új változatát. Ez az új módszer olyan híres problémák megoldásához vezetett, mint például a cap set probléma vagy az Erdős-Szemerédi-féle napraforgósejtés. Azóta a módszernek számos alkalmazása született, mint például pontos becslés Green “arithmetical triangle removal” lemmájára (Fox-Lovász), Sárközy tétele véges test feletti polinomokra (Green), és még számos egyéb. A cikk a legrangosabb matematikai folyóiratban, az Annals of Mathematics-ban jelent meg, Fields medállal kitüntetett matematikusok: Gowers, Tao, és más vezető matematikusok, például Cameron és Kalai is elemezték blogjukon.
Tóth Géza Pach Jánossal és Tardos Gáborral a Metszési Lemma messzemenő általánosításait bizonyította be multigráfokra, különböző természetes feltételek mellett.
Wiener Gábor Peter Dameschkevel és Azam Sheikh Muhammaddal közösen egy újfajta, a gyakorlatban is jól használható csoporttesztelési modell (a strict group testing) kombinatorikai alapjait rakta le, a cikk a vezető kombinatorikai folyóiratok egyikében, a Journal of Combinatorial Theory A-ben jelent meg.
Simonyi Gábor Tardos Gáborral részleges (a 4-kromatikus esetben teljes) jellemzését adta Schrijver gráfok színkritikus éleinek.
Katona Gyula és Papp László egy Győri Ervinnel közös munkában alsó és felső korlátokat adott nagy rácsok optimális kövezési számára.
Katona Gyula Varga Kittivel a minimálisan szívós gráfok vizsgálatában ért el számos jelentős eredményt.
A közelmúlt projektjei:
MTA Lendület • OTKA
Nemzetközi kapcsolatok:
Ibaraki University, Japán • Lancaster University, Egyesült Királyság • University of Haifa, Izrael • University of Warwick, UK • Ghent University • Yokohama National University • University of British Columbia, Canada • Sapienza – Universitá di Roma
Vállalati partnerek:
Morgan Stanley • Lynx Analytics
Algoritmuselmélet
A kutatócsoport tevékenysége:
Kombinatorikus algoritmusok. Klasszikus és kvantumalgoritmusok, bonyolultságelméleti és paraméteres bonyolultságos megközelítések. Ezen belül pl. társadalmi választások, fair hozzárendelések, stabil és népszerű párosítások, hálózatok megbízhatóságának vizsgálata kombinatorikus és játékelméleti módszerekkel. Különböző kvantumos megközelítések (algoritmus, QUBO, kvantumbolyongás) vizsgálata. Logikai és deklaratív programozás.
Eredmények:
Számos eredményünk született a fair hozzárendelés területén: többek között bizonyítottuk, hogy 3 ágens esetén az irigység-mentes allokáció keresése NP-teljes feladat (ezzel egy 5 évig nyitott kérdést megválaszolva), ugyanakkor arányos allokáció keresése polinom idejű algoritmussal megoldható; ez utóbbi kérdést általános számú ágens esetén is körbejártuk, feltérképeztük annak paraméteres bonyolultságát és approximálhatóságát. Vizsgáltuk a stabil párosítás probléma sok-paraméteres bonyolultságát abban az esetben, ahol bizonyos ágensek fedését írhatjuk elő: öt vizsgált paraméter minden kombinációjára sikerült a probléma bonyolultságát meghatározni. Foglalkoztunk még a népszerű fenyvesek problémájával is, hatékony egzakt és közelítő algoritmusok megadása mellett számos nehézségi eredményt is bizonyítottunk.
Bizonyítottunk egy olyan új eredményt, aminek segítségével a hálózatok megbízhatóságának játékelméleti eszközökkel való mérésére vonatkozó korábban ismert, matroidelméleti módszereket sikerült a greedoidoknak egy, a matroidoknál bővebb osztályára kiterjeszteni.
Kvantumalgoritmusok körében vizsgáltuk a Fourier-transzformáció alkalmazásanak határait bizonyos algebrai feladatokra. Foglalkoztunk a kvantumalgoritmusok egy fajta használatával a gépi tanulásban, megmutatva, hogy egy mások által javasolt módszer nem sok előnyt ad a klasszikus eljárásokhoz képest. Vizsgáljuk, hogyan lehet klasszikus problémákat a D-Wave (korábbi) kvantumszámítógépébe beágyazni, az ott használt QUBO (quantum unconstrained binary optimization) feladatra átfordítani.
A közelmúlt projektjei:
OTKA
Nemzetközi kapcsolatok:
Hamburg University of Technology • University of Tübingen • Université Paris Diderot – Paris, Centre for Quantum Technologies • University of Singapore