Title: Chromatic number of generalized Borsuk Graphs
Speaker: Francisco Martinez Figueroa (Ohio State University)
Abstract: The Borsuk graph is the graph with vertex set the sphere S^d, and edges {x,y} whenever x and y are epsilon-almost antipodal. It is well known that when epsilon is small, its chromatic number is d+2, which follows from the topology of S^2 via Borsuk-Ulam’s Theorem. Given a finite group G acting freely over a compact space X via isometries, we define the G-Borsuk graph to be the graph with vertex set X and edges {x,y} whenever there exists a non-identity g in G such that d(x,gy)<epsilon. The chromatic number of such graph is determined by the topology of X. In this talk we’ll show some upper bounds for this chromatic number depending only on |G| and dim(X). Our bounds are tight when dim(X)=1, and we exhibit some tight results in dimensions 2 and 3 when G=Z_m, for small values of m. We will also discuss random G-Borsuk graphs, which are finite induced subgraphs by choosing n i.i.d. uniform vertices on X. For these, we exhibit a tight threshold for epsilon (up to a constant) such that a.a.s. the chromatic number of the random subgraph coincides with that of the whole G-Borsuk graph. This is joint work in progress with Matthew Kahle.
