2018/02/26 by Bui, Hoa Thi, Pineda-Villavicencio, Guillermo, Ugon, Julien
#52B05 (Primary) 52B12 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1802.09230
A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. The paper is concerned with the linkedness of the graphs 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 vertex-disjoint paths joining the vertices in the pairs. Larman and Mani in 1970 proved that simplicial d-polytopes, polytopes with all their facets being combinatorially equivalent to simplices, are \floor(d+1)/2-linked; this is the maximum possible linkedness given the facts that a \floor(d+1)/2-linked graph is at least (2\floor(d+1)/2-1)-connected and that some of these graphs are d-connected but not (d+1)-connected. Here we establish that cubical d-polytopes are also \floor(d+1)/2-linked for every d≠ 3; this is again the maximum possible linkedness for such a class of polytopes.