Számítástudományi és Információelméleti Tanszék

Ritka kombinatorikai struktúrák vizsgálatának algoritmikus kérdései

Az elmúlt évtizedekben a nagy hálózatok (például az internet vagy mobilhálózatok) széleskörű megjelenésének következtében mind nagyobb igény mutatkozott olyan matematikai modellek és fogalmak kidolgozására, amelyekkel nagy hálózatok tulajdonságait le lehet írni. (A Szemerédi-féle regularitási lemma, a Lovász által kezdeményezett gráflimesz elmélet vagy Razborov flag algebra módszere mind hatékony eszközök, melyek segítségével nagy és sűrű kombinatorikai objektumok strukturális és extremális tulajdonságai leírhatóak.)

Ugyanakkor a sűrű rendszerek mellett a ritka kombinatorikai objektumok vizsgálata is egyre fontosabbá vált az utóbbi időben, ugyanis azok a matematikai objektumok (gráfok, hipergráfok, halmazrendszerek), amelyek a való életbeli helyzetek modellezésekor felmerülnek, leginkább ritkák (korlátos fokúak, d-leépíthetőek stb.). Ám ritka kombinatorikai objektumok tulajdonságai vizsgálatára (egyelőre) nincsenek annyira hatékony módszereink, mint a sűrű esetben.

Az egyik ilyen módszer, amellyel ritka kombinatorikai objektumokat vizsgálunk, részstruktúráinak leszámlálása és a köztük lévő kapcsolatok vizsgálata. Ezekhez kapcsolódó algoritmikus kérdések irodalmának összegyűjtése és a felmerülő kérdések vizsgálata lenne a projekt célja.

Ajánlott irodalom:

[1] L. Gishboliner, A. Shapira. A generalized Turán problem and its applications. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (pp. 760-772). ACM.

[2] N. Alon, C. Shikhelman. Additive Approximation of Generalized Turán Questions. arXiv preprint arXiv:1811.08750.

Szükséges nyelvtudás: angol.

Vizer Máté
Rényi A. Matematikai Kutatóintézet
vizermate@gmail.com