A combinatorial shifting method on multicomplexes with applications to simplicial complexes and simple graphs


ARS COMBINATORIA, vol.86, pp.175-191, 2008 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 86
  • Publication Date: 2008
  • Title of Journal : ARS COMBINATORIA
  • Page Numbers: pp.175-191


We introduce a combinatorial shifting operation on multicomplexes that carries similar properties required for the ordinary shifting operation on simplicial complexes. A linearly colored simplicial complex is called shifted if its associated multicomplex is stable under defined operation. We show that the underlying simplicial subcomplex of a linearly shifted simplicial complex is shifted in the ordinary sense, while the ordinary and linear shiftings are not interrelated in general. Separately, we also prove that any linearly shifted complex must be shellable with respect to the order of its facets induced by the linear coloring. As an application, we provide a characterization of simple graphs whose independence complexes are linearly shifted. The class of graphs obtained constitutes a superclass of threshold graphs.