Abstract: 

We study chromatic number in classes of finite graphs contained in an infinite graph definable in a pure set. In particular, we will see that shift graphs and cliques are in some sense the only obstructions to bounded chromatic number. This is entirely finite combinatorics, but tropical linear programming and its connection to mean-payoff games make a surprise appearance. Joint work with Sarosh Adenwalla, Tomáš Hons, John Sylvester, and Viktor Zamaraev.

Zoom: 717 463 6082