Skeleton Chordalities
Abstract
We study new higher-dimensional analogs of graph chordality and review the existing ones. Our main results for simplicial complexes are:
(1) $\Delta$ skeleton-E-chordal $\Rightarrow$ $\Delta^\vee$ vertex-decomposable $\Rightarrow$ $\Delta$ skeleton-clique-chordal. Moreover, for subflag complexes, $\Delta$ skeleton-E-chordal $\Longleftrightarrow$ $\Delta^\vee$ vertex-decomposable. (For $d=1$ this boils down to ``$G$ chordal $\Longleftrightarrow$ $G^\vee$ vertex-decomposable'', a result closely related to Fröberg's theorem.)
(2) For subflag complexes, $\Delta$ is skeleton-E-chordal $\Longleftrightarrow$ it splits as $\Delta = \Delta_1 \cup \Delta_2$, with each $\Delta_i$ a skeleton-E-chordal induced subcomplex of $\Delta$, and with $\Delta_1 \cap \Delta_2$ a complex whose $1$-skeleton is a clique. (This generalizes ``$G$ chordal $\Longleftrightarrow$ $G$ splits as a union of chordal graphs that intersect in a common clique'').
(3) $\Delta$ skeleton-E-chordal $\Longleftrightarrow$ every nonempty induced subcomplex of $\Delta$ has a skeleton-E-simplicial vertex. (Generalizes ``$G$ chordal $\Leftrightarrow$ every nonempty induced subgraph has a simplicial vertex''.)
(4) $\Delta$ underclosed $\Rightarrow$ $\Delta$ skeleton-weakly-chordal and weakly-closed. (Generalizes ``$G$ interval $\Rightarrow$ $G$ chordal and co-comparability''.)
(5) All pure E-chordal complexes are vertex-chordal; all pure mid-chordal complexes are weakly-vertex-chordal; all pure very-weakly-chordal complexes are weakly-ridge-chordal. (This expands Bigdeli, Yazdan-Pour and Zaare-Nahandi's work on ridge-chordality.)
이 뉴스, 어떠셨어요?
탭 한 번으로 반응 · 로그인 불필요