An algorithmist's journey through topology

An important part of algorithmics is devoted to studying the problem of satisfying systems of constraints – or, equivalently – finding homomorphisms between finite structures such as graphs. I will present several new applications of algebraic topology to purely combinatorial and algorithmic questions on graph homomorphisms. All rely on the so-called box complex of a graph and the continuous Z2-equivariant map induced by a graph homomorphism. The topology we used so far is elementary, but I will focus on a few questions that arose in this work and remain, to us combinatorialists, open. One example: are there two spaces X, Y with Z2 actions such that neither admits a Z2-equivariant map to the 2-sphere, but the product X x Y (with Z2 acting simultaneously on both components) does? Another example: how can we classify maps [T^n, RP^2], and more generally, how can we understand relations between [T^n, RP^d] and [T^k, RP^d] induced by functions from (finite sets) n to k?