Combinatorics of CAT(0) cube complexes,   Federico Ardila,   San Francisco State University, California,  Wed, 30 March, 2011,   10:00 a.m. C-236


A "cube complex" X is a space built by gluing cubes together. We say that X is "CAT(0)" if it has global non-positive curvature - roughly speaking, this means that X is shaped like a saddle. CAT(0) cube complexes play an important role in pure mathematics (geometric group theory) and in applications (phylogenetics, robot motion planning). We show that, surprisingly, CAT(0) cube complexes can be described completely combinatorially. This description has several consequences. We give a proof of the conjecture that any d-dimensional CAT(0) cube complex X "fits" in d-dimensional space. Also, for any such space X, we construct a robot whose motion is described by X. Finally, we give an algorithm that finds the shortest path between two points in X (and hence the optimal way to move a robot from one position to another one under this metric). The talk will be self-contained, and will describe joint work with Megan Owen and Seth Sullivan.