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


ARS COMBINATORIA, cilt.86, ss.175-191, 2008 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 86
  • Basım Tarihi: 2008
  • Sayfa Sayıları: ss.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.