When: Sunday, March 27,
10am
Where: Schreiber 309
Speaker: Shakhar
Smorodinsky, Ben Gurion University
Title:
A Solution to Ringel's Circle Problem
Suppose we are given a finite family $\mathcal{C}$ of circles in the plane. The circles in $\mathcal{C}$ may overlap (i.e., two circles have two points in common) or be tangent (only one point in common) but no three circles may be pairwise tangent at the same point. Consider the tangency graph $G(\mathcal{C})$ on $\mathcal{C}$ where two circles form an edge if and only if they are tangent. In 1959 Gerhard Ringel asked whether the chromatic number of the tangency graph $G(\mathcal{C})$ is bounded? He also showed that it is at least $5$. We construct families of circles in the plane such that their tangency graphs have arbitrarily large girth and chromatic number. This provides a strong negative answer to that problem.
Joint work with James Davis, Chaya Keller, Linda Kleist and Bartosz Walczak