Adattudomány, hálózatok és modellezés szeminárium

A matematika egyik (tudománytörténeti) vívmánya, hogy a világ bonyolult dolgait tudja a saját eszközeivel hatékonyan modellezni. Előadásunk egy ilyen modellt próbál bemutatni, nevezetesen a gráfokkal való modellezést. Bemutatunk és részletezünk néhány problémát, amely hatékonyan megfogalmazható mint gráfprobléma, és ahol a megoldást a gráf egy maximális vagy k-klikkje szolgáltatja.

A bevezető példák után bemutatunk több átfogalmazást, ahol a gráfok színezése vezethető vissza klikk keresésre. Ezen példákhoz hasonlóan bemutatjuk, ahogy a hipergráfok esetén is alkalmazhatóak ezek a
technikák, és összevetjük a lehetséges megoldásokat. Bemutatjuk, hogy az elemzett technikák segítségével hogy lehet megoldani bonyolult, nyitott kérdéseket.

Annak céljából, hogy bemutassuk a gráf-átfogalmazások valóban sokrétű erősségét meg egy speciális esetet mutatunk be. A gráfszínezések LP átfogalmazásánál ismert módszer van arra, hogy bizonyos
szimmetriatöréseket is meg lehessen az LP egyenlőtlenségekben fogalmazni. Megmutatjuk, hogy ezen szimmetriatörések a gráfátfogalmazásokban is lehetségesek. Az így kapott gráfok meglepő
tulajdonsággal bírnak: bár nagyobb gráfokról van szó, mégis könnyebb a bennük a k-klikk feladat megoldása.