Codegree and regularity of stable set polytopes
| Autor: | Matsushita, Koji, Tsuchiya, Akiyoshi |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | The codegree ${\rm codeg}(P)$ of a lattice polytope $P$ is a fundamental invariant in discrete geometry. In the present paper, we investigate the codegree of the stable set polytope $P_G$ associated with a graph $G$. Specifically, we establish the inequalities \[ \omega(G) + 1 \leq {\rm codeg}(P_G) \leq \chi(G) + 1, \] where $\omega(G)$ and $\chi(G)$ denote the clique number and the chromatic number of G, respectively. Furthermore, an explicit formula for ${\rm codeg}(P_G)$ is given when G is either a line graph or an $h$-perfect graph. Finally, as an application of these results, we provide upper and lower bounds on the regularity of the toric ring associated with $P_G$. Comment: 8 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|