Department of Mathematics,
University of California San Diego
****************************
Math 295 - Mathematics Colloquium
Penny Haxell
University of Waterloo
Topological connectedness in combinatorics
Abstract:
An abstract simplicial complex $\Sigma$ is said to be $k$-connected if for each $−1 \leq d \leq k$ and each continuous map $f$ from the sphere $S$ to $\|\Sigma\|$ (the polyhedron of the geometric realization of $\Sigma$), the map $f$ can be extended to a continuous map from the ball $B_{d+1}$ to $\|\Sigma\|$. The topological connectedness of $\Sigma$ is the largest $k$ for which it is $k$-connected. In 2000 a link was discovered between the topological connectedness of the independence complex of a graph and various other important graph parameters to do with colouring and partitioning. When the graph represents some other combinatorial structure, for example when it is the line graph of a hypergraph $H$, this link can be exploited to obtain information such as lower bounds on the matching number of $H$. Since its discovery there have been various other applications of this phenomenon to other combinatorial problems, including several different types of colouring (list colouring, strong colouring, delay edge colouring, circular colouring), hypergraph packing and covering, toughness and Hamiltonicity, and job scheduling and other resource allocation problems. In this talk we give an overview of this technique, and describe some of its applications.
Host: Jacques Verstraete
March 29, 2018
4:00 PM
AP&M 2402
****************************