Vidnyánszky Zoltán (Bécs): Borel-kromatikus számok: Bázis és antibázis eredmények

Egy $G=(X,E)$ gráfot Borel-gráfnak nevezünk, ha $X$ Borel-tér, $E$ pedig $X^2$ Borel részhalmaza. Az utóbbi időben sokat vizsgált fogalom a Borel-kromatikus szám  fogalma, mely a szokásos fogalomhoz hasonlóan definiálható, azzal a megkötéssel, hogy a színezés Borel-mérhető leképezés legyen. Az előadásban belátjuk, hogy az, hogy egy gráf Borel-kromatikus száma $>n$, pontosan akkor döntehtő el könnyen, ha $n=1,2$ vagy $\aleph_0$, teljes leírását adva ezzel a Borel-kromatikus számok elméletének. Azt a meglepő állítást is belátjuk, hogy létezik egyetlen Borel gráf, $G_3$, melynek Borel-kromatikus száma 3 (azaz nem Borel-páros), és minden nem Borel-páros gráf tartalmazza $G_3$ egy Borel-homomorf képét.