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'$.

$\endgroup$
  • $\begingroup$ If such a facet $F$ exists, then is it true that $F$ contains a shedding vertex? $\endgroup$ – T. Amdeberhan Dec 21 '16 at 21:23
  • 1
    $\begingroup$ Does Example 1.17 work from math.cornell.edu/~eranevo/homepage/FaceRingNotes.pdf $\endgroup$ – T. Amdeberhan Dec 21 '16 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 Dec 22 '16 at 3:25
5
$\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.

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.