Printable PDF
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

****************************