Logic Seminar

Abstract: The fractional chromatic number (FCN) of a graph is the solution to the linear relaxation of an integer program that computes the chromatic number (CN). Hence a descriptive set theorist may consider the Borel FCN, a quantity as yet unstudied, by restricting to only Borel colourings. We show that for an acyclic graph with Borel CN 3, the Borel FCN may (like the CN) drop to 2. We also show that the CN, FCN, and Borel FCN of a Borel graph may be made almost any values desired that follow the obvious inequalities.