Connectivity of graphs of polytopes
Seminar/Forum
In this talk we explore two questions on the connectivity of graphs of cubical polytopes. A cubical \(d\)polytope is a polytope with all its facets being combinatorially equivalent to \((d1)\)cubes.
Firstly, we establish the following.
(1) For any integer \(d\) at least 3 and any nonnegative integer \(\alpha\) at most \ (d3\), the graph of a cubical \(d\)polytope with minimum degree at least \(d+\alpha\) is \((d+\alpha)\)connected; and
(2) for any integer \(d\) at least 4 and any nonnegative integer \(\alpha\) at most \(d3\), every separator of cardinality \(d+\alpha\) in such a graph consists of all the neighbours of some vertex and breaks the polytope into exactly two components.
The second question is about the linkedness of cubical polytopes. A graph with at least \(2k\) vertices is \(k\)linked if, for every set of \(2k\) distinct vertices organised in arbitrary \(k\) pairs of vertices, there are \(k\) vertexdisjoint paths joining the vertices in the pairs. In this direction, the following is our main contribution.
(3) Cubical \(d\)polytopes are \(\lfloor{(d+1)/2}\rfloor\)linked for every \(d\) at least 3; this is the maximum possible linkedness for such a class of polytopes.
Other information: This talk will be broadcast online using Zoom conferencing system. Join from PC, Mac, iOS or Android: https://unimelb.zoom.us/j/931478513
Presenter

Dr Guillermo PinedaVillavicencio, Federation University