When: Monday June 13th, 2022, at 11AM (Israel time)
Where: Sprinzak 202
Link to live session:
https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=cb7c661b-cfae...
Speaker: Chaya Keller (Ariel)
Title: A solution to Ringel’s circle problem
Abstract:
In 1959, Gerhard Ringel posed the following problem: What is the maximal number of colors needed for coloring any collection of circles, no three tangent at a point, such that any two tangent circles get different colors?
The special case where the circles are non-overlapping was shown long ago to be equivalent to the celebrated 4-color theorem. The general case has remained open; it was only known that 4 colors are not sufficient. In this talk we show that no finite number of colors can suffice, by constructing collections of circles whose tangency graphs have an arbitrarily large girth (so in particular, no three are tangent at a point) and an arbitrarily large chromatic number. Our construction, which is one of the first geometric constructions of graphs with a large girth and a large chromatic number, relies on a (multidimensional) version of Gallai’s theorem with polynomial constraints, which we derive from the Hales-Jewett theorem and which may be of independent interest.
Joint work with James Davies, Linda Kleist, Shakhar Smorodinsky, and Bartosz Walczak