Connectivity and Linkedness of Cubical Polytopes

Speaker: 

Bui Thi Hoa

Affiliation: 

Federation University Australia

Date: 

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

Venue: 

RC-M032, The Red Centre, UNSW

Abstract: 

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: