Codegree and regularity of stable set polytopes
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910086365970432 |
|---|---|
| author | Matsushita, Koji Tsuchiya, Akiyoshi |
| author_facet | Matsushita, Koji Tsuchiya, Akiyoshi |
| contents | The codegree ${\rm codeg}(\mathcal{P})$ of a lattice polytope $\mathcal{P}$ is a fundamental invariant in discrete geometry. In the present paper, we investigate the codegree of the stable set polytope $\mathcal{P}_G$ associated with a simple graph $G$. Specifically, we establish the inequalities \[ ω(G) + 1 \leq {\rm codeg}(\mathcal{P}_G) \leq χ(G) + 1, \] where $ω(G)$ and $χ(G)$ denote the clique number and the chromatic number of $G$, respectively. Furthermore, an explicit formula for {\rm codeg}(\mathcal{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 $\mathcal{P}_G$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_10090 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Codegree and regularity of stable set polytopes Matsushita, Koji Tsuchiya, Akiyoshi Combinatorics Commutative Algebra 52B20, 05C15, 13C10 The codegree ${\rm codeg}(\mathcal{P})$ of a lattice polytope $\mathcal{P}$ is a fundamental invariant in discrete geometry. In the present paper, we investigate the codegree of the stable set polytope $\mathcal{P}_G$ associated with a simple graph $G$. Specifically, we establish the inequalities \[ ω(G) + 1 \leq {\rm codeg}(\mathcal{P}_G) \leq χ(G) + 1, \] where $ω(G)$ and $χ(G)$ denote the clique number and the chromatic number of $G$, respectively. Furthermore, an explicit formula for {\rm codeg}(\mathcal{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 $\mathcal{P}_G$. |
| title | Codegree and regularity of stable set polytopes |
| topic | Combinatorics Commutative Algebra 52B20, 05C15, 13C10 |
| url | https://arxiv.org/abs/2412.10090 |