Department of

August 2016 September 2016 October 2016 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 4 5 6 1 2 3 1 7 8 9 10 11 12 13 4 5 6 7 8 9 10 2 3 4 5 6 7 8 14 15 16 17 18 19 20 11 12 13 14 15 16 17 9 10 11 12 13 14 15 21 22 23 24 25 26 27 18 19 20 21 22 23 24 16 17 18 19 20 21 22 28 29 30 31 25 26 27 28 29 30 23 24 25 26 27 28 29 30 31

Tuesday, September 6, 2016

**Abstract:** A Borel graph is a graph whose vertex set is the elements of a Polish space and whose edge relation is Borel. We investigate combinatorial problems on hyperfinite Borel graphs—the simplest graphs that can display nonclassical behavior in the setting of descriptive graph combinatorics (as made precise by the Glimm–Effros dichotomy). A fundamental theorem of Kechris, Solecki, and Todorcevic states that every Borel graph of degree at most $d$ has Borel $d + 1$ coloring. Answering a question of Conley and Miller, we show that for every $d$ there is an acyclic $d$-regular hyperfinite Borel graph with no Borel $d$-coloring. This Borel result is in contrast to the measure-theoretic context, where hyperfinite graphs are known to be much simpler to measurably color than arbitrary bounded degree Borel graphs.