10
$\begingroup$

Does there exist a (pure) shellable simplicial complex $\Delta$ with the following property? There is some facet $F$ of $\Delta$ such that no shelling can begin with $F$.

This condition is easily seen to be equivalent to the existence of a shellable simplicial complex $\Delta'$ with at least two facets, such that for some facet $F'$ every shelling of $\Delta'$ ends with $F'$.

Improve this question
$\endgroup$
3
  • $\begingroup$ If such a facet $F$ exists, then is it true that $F$ contains a shedding vertex? $\endgroup$
    – T. Amdeberhan
    Commented Dec 21, 2016 at 21:23
  • 1
    $\begingroup$ Does Example 1.17 work from math.cornell.edu/~eranevo/homepage/FaceRingNotes.pdf $\endgroup$
    – T. Amdeberhan
    Commented Dec 21, 2016 at 21:29
  • 2
    $\begingroup$ @T.Amdeberhan Example 1.17 does not work. In fact, it is known that the smallest $f$-vector of a shellable simplicial complex for which some partial shelling cannot be extended to a shelling is $(6,14,9)$. $\endgroup$
    – Richard Stanley
    Commented Dec 22, 2016 at 3:25

1 Answer 1

Reset to default
6
$\begingroup$

The answer to your question is "yes". Such complexes were first exhibited by Hachimori in his PhD thesis. See the clear explanation on his webpage:
http://infoshako.sk.tsukuba.ac.jp/~hachi/math/library/nonextend_eng.html
The $f$-vector of this complex is (1,7,19,13). I suspect that 7 vertices is minimal. UPDATE: I later noticed that Simon earlier exhibited an example of similar type in Appendix F of his 1994 paper:
Simon, Robert Samuel, Combinatorial properties of “cleanness”, J. Algebra 167, No. 2, 361-388 (1994). ZBL0855.13013.
Hachimori's webpage also has a fairly nice presentation of Simon's example:
http://infoshako.sk.tsukuba.ac.jp/~hachi/math/library/simon_eng.html

Adiprasito, Benedetti and Lutz have meanwhile (since you first asked the question) extended an idea similar to Hachimori's to arbitrary dimension in their paper:
Adiprasito, Karim A.; Benedetti, Bruno; Lutz, Frank H., Extremal examples of collapsible complexes and random discrete Morse theory, Discrete Comput. Geom. 57, No. 4, 824-853 (2017). ZBL1365.05305.

Complexes having the property of Hachimori's have arisen recently as a tool. They were used as one of the main building blocks to show that the SHELLABILITY problem is NP-complete in this paper of Goaoc, Paták, Patáková, Tancer, and Wagner. (The paper appeared in a conference proceeding, though it doesn't seem to yet be on zbMath.)

I'll mention parenthetically that Goaoc, Paták, Patáková, Tancer, and Wagner require also some other building blocks of the same flavor as Hachimori's complex. Their constructions for these are a bit complicated for my taste, and they don't include all of the details in the above-linked paper. My PhD student Andrés Santamariá Galvis has some simpler constructions that are based on Hachimori's example.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .