Effective symmetry breaking
Rebecca M. Steiner
Vanderbilt University
Symmetry breaking involves the coloring of elements of a structure so that the only automorphism of the structure which respects the coloring is the trivial one. We investigate how much information we would need to be able to compute a 2-coloring of a computable finite-branching tree under the predecessor function which eliminates all automorphisms except the trivial one; we also generalize to n-colorings for fixed n and for variable n. Then, we suppose the tree is no longer finite branching, and we observe what happens to the difficulty of computing a 2-coloring.
Rebecca Steiner is a CUNY Graduate Center product, having received her Ph.D. here in 2012 as a student of Russell Miller. She then assumed a postdoctoral position at Vanderbilt University, studying computability and computable model theory, with a focus on algebraic structures. In the fall of 2015 she will join the mathematics department of Virginia Commonwealth University.