Connectivity and Linkedness of Cubical Polytopes


Bui Thi Hoa


Federation University Australia


Thu, 16/05/2019 - 10:00am


RC-M032, The Red Centre, UNSW


A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. The first part of the talk we will establish that for any $d\ge 4$, the graph of a cubical $d$-polytope with minimum degree $\delta$ is $\min\{\delta, 2d - 2\}$-connected, and every minimum separator of cardinality at most $2d - 3$ in such a graph consists of all the neighbours of some vertex and that removing the vertices of the separator from the graph leaves exactly two components, with one of them being the vertex itself.

The second part of the talk we will discuss about a stronger than connectivity property, so-called linkedness. A graph with at least $2k$ vertices is $k$-linked if for for every set of $2k$ distinct vertices organised in arbitrary $k$ unordered pairs of vertices, there are $k$ vertex-disjoint paths joining the vertices in the pairs. Here we establish that $d$-dimensional cubical polytopes are also $\lfloor(d+1)/2\rfloor$-linked for every $d\neq 3$; this is the maximum possible linkedness for such a class of polytopes.

School Seminar Series: