Leírás
Az előadáson Mirzakhani és Vondrák "Hypergraph labeling problems and fair division" című cikkét ismertetem. Jelölje $V_{k,q}$ azon $k$-dimenziós nemnegatív egész vektorok halmazát, amiknek koordináta-összege q. Sperner-színezésnek nevezzük $V_{k,q}$ egy olyan színezését k színnel, ahol $x_i=0$ esetén $x$ színe nem $i$. $V_{k,q-1}$ minden $z$ pontjához hozzárendelhetjük a $z+e_1,z+e_2,\dots,z+e_k$ szimplexet $V_{k,q}$-ban; jelölje ezen szimplexek halmazát $E_{k,q}$. A cikk pontos alsó korlátot ad a többszínű $E_{k,q}$-beli szimplexek számára egy Sperner-színezésben. Ennek segítségével belátja, hogy a Unique Games sejtést feltéve nincs $(k-1)$-nél jobb közelítés a következő feladatra: adott $H=(V,E)$ $k$-uniform hipergráfra és $L(v) \subseteq [k]$ ($v \in V$) színlistákra találjunk olyan listaszínezést, ami minimalizálja a többszínű hiperélek számát.