An algorithmist's journey through topology

Speaker(s)

Marcin Wrochna

Affiliation

Oxford

Date

Dec. 1, 2020, 4:30 p.m.

Information about the event

Zoom: 811 1192 8889, pass: proszę wpisać liczbę równą rk(H^2((S^1)^{200};Z))

Seminar

Seminar Algebraic 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?

---