Distinguishing Numbers of Graphs and Groups

By Yitzchak Solomon

February 5, 2014


A blind janitor has a large ring of keys. When the janitor's eyesight was better, he was able to read the labels on each of the keys. However, because he can no longer do so, he often sorts through half of the keys on the loop, trying each one until he eventually stumbles on the right key. Recognizing the plight of the janitor, the school administrators are willing to pay for keys of different shapes, so that the janitor can feel the difference between the keys. However, the budget is tight, and the school cannot afford to print as many new shapes as there are keys. What is the minimal number of shapes needed so that the janitor never has to use trial and error to find the right key?

This artificial example is designed to motivate the following setup. Every graph G has an associated group of symmetries Aut(G). We can add structure to our graph by coloring our vertices, and then consider the subgroup of Aut(G) that preserves that coloring. This talk will be concerned with the task of making that subgroup trivial with as few colors as possible; that is, breaking all of the symmetries in the graph with the least amount of additional structure. We will use algebraic and combinatorial arguments to show that this number is very small for a large family of interesting graphs.