Non-constructible Complexes and the Bridge Index

Richard Ehrenborg, Masahiro Hachimori

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


We show that if a three-dimensional polytopal complex has a knot in its 1-skeleton, where the bridge index of the knot is larger than the number of edges of the knot, then the complex is not constructible, and hence, not shellable. As an application we settle a conjecture of Hetyei concerning the shellability of cubical barycentric subdivisions of 3-spheres. We also obtain similar bounds concluding that a 3-sphere or 3-ball is non-shellable or not vertex decomposable. These two last bounds are sharp.

Original languageEnglish
Pages (from-to)475-491
Number of pages17
JournalEuropean Journal of Combinatorics
Issue number4
StatePublished - May 2001

Bibliographical note

Funding Information:
The authors thank Günter Ziegler and the Mathematisches Forschungsinstitut Oberwolfach. The authors also thank Margaret Readdy and the two referees for their comments on an earlier draft of this paper. The first author was supported by National Science Foundation, DMS 97-29992, and NEC Research Institute, Inc. when he was a member at the Institute for Advanced Study, Princeton and by the Swedish Natural Science Research Council DNR 702-238/98 while at the Royal Institute of Technology. The second author was supported by Research Fellowships of the Japan Society for the Promotion of Science for Young Scientists.

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Non-constructible Complexes and the Bridge Index'. Together they form a unique fingerprint.

Cite this