Browse issues
no. 6
Codegree and regularity of stable set polytopes
Matsushita, Koji1; Tsuchiya, Akiyoshi2
1 Osaka University, Department of Pure and Applied Mathematics, Graduate School of Information Science and Technology, Suita, Osaka 565-0871 (Japan)
2 Toho University, Department of Information Science, Faculty of Science, 2-2-1 Miyama, Funabashi, Chiba 274-8510 (Japan)
Algebraic Combinatorics, Volume 8 (2025) no. 6, pp. 1743-1751

The codegree $\mathrm{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

\[ \omega (G) + 1 \le \mathrm{codeg}(\mathcal{P}_G) \le \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 $\mathrm{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$.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.460
Classification: 52B20, 05C15, 13C10
Keywords: stable set polytope, codegree, clique number, chromatic number, matching polytope, perfect graph, h-perfect graph, toric ring, regularity

Matsushita, Koji 1; Tsuchiya, Akiyoshi 2

1 Osaka University, Department of Pure and Applied Mathematics, Graduate School of Information Science and Technology, Suita, Osaka 565-0871 (Japan)
2 Toho University, Department of Information Science, Faculty of Science, 2-2-1 Miyama, Funabashi, Chiba 274-8510 (Japan)
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2025__8_6_1743_0,
     author = {Matsushita, Koji and Tsuchiya, Akiyoshi},
     title = {Codegree and regularity of stable set polytopes},
     journal = {Algebraic Combinatorics},
     pages = {1743--1751},
     year = {2025},
     publisher = {The Combinatorics Consortium},
     volume = {8},
     number = {6},
     doi = {10.5802/alco.460},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.460/}
}
TY  - JOUR
AU  - Matsushita, Koji
AU  - Tsuchiya, Akiyoshi
TI  - Codegree and regularity of stable set polytopes
JO  - Algebraic Combinatorics
PY  - 2025
SP  - 1743
EP  - 1751
VL  - 8
IS  - 6
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.460/
DO  - 10.5802/alco.460
LA  - en
ID  - ALCO_2025__8_6_1743_0
ER  - 
%0 Journal Article
%A Matsushita, Koji
%A Tsuchiya, Akiyoshi
%T Codegree and regularity of stable set polytopes
%J Algebraic Combinatorics
%D 2025
%P 1743-1751
%V 8
%N 6
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.460/
%R 10.5802/alco.460
%G en
%F ALCO_2025__8_6_1743_0
Matsushita, Koji; Tsuchiya, Akiyoshi. Codegree and regularity of stable set polytopes. Algebraic Combinatorics, Volume 8 (2025) no. 6, pp. 1743-1751. doi: 10.5802/alco.460

[1] Beck, Matthias; Robins, Sinai Computing the continuous discretely, Undergraduate Texts in Mathematics, Springer, New York, 2015, xx+285 pages | DOI | MR | Zbl

[2] Berge, Claude Les problèmes de coloration en théorie des graphes, Publ. Inst. Statist. Univ. Paris, Volume 9 (1960), pp. 123-160 | MR | Zbl

[3] Bruns, W.; Ichim, B.; Söger, C.; Ohe, U. von der Normaliz. Algorithms for rational cones and affine monoids, Available at https://www.normaliz.uni-osnabrueck.de

[4] Bruns, Winfried; Herzog, Jürgen Cohen-Macaulay rings, Cambridge Studies in Advanced Mathematics, 39, Cambridge University Press, Cambridge, 1993, xii+403 pages | MR | Zbl

[5] Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin The strong perfect graph theorem, Ann. of Math. (2), Volume 164 (2006) no. 1, pp. 51-229 | DOI | MR | Zbl

[6] Chvátal, V. On certain polytopes associated with graphs, J. Combinatorial Theory Ser. B, Volume 18 (1975), pp. 138-154 | DOI | MR | Zbl

[7] Edmonds, Jack Maximum matching and a polyhedron with 0,1-vertices, J. Res. Nat. Bur. Standards Sect. B, Volume 69B (1965), pp. 125-130 | MR | DOI | Zbl

[8] Grayson, Daniel R.; Stillman, Michael E. Macaulay2, a software system for research in algebraic geometry, Available at http://www2.macaulay2.com

[9] Hà, Huy Tài; Van Tuyl, Adam Monomial ideals, edge ideals of hypergraphs, and their graded Betti numbers, J. Algebraic Combin., Volume 27 (2008) no. 2, pp. 215-245 | DOI | MR | Zbl

[10] Herzog, Jürgen; Hibi, Takayuki; Ohsugi, Hidefumi Binomial ideals, Graduate Texts in Mathematics, 279, Springer, Cham, 2018, xix+321 pages | DOI | MR | Zbl

[11] Hofscheier, Johannes; Katthän, Lukas; Nill, Benjamin Ehrhart theory of spanning lattice polytopes, Int. Math. Res. Not. IMRN (2018) no. 19, pp. 5947-5973 | DOI | MR | Zbl

[12] Katzman, Mordechai Characteristic-independence of Betti numbers of graph ideals, J. Combin. Theory Ser. A, Volume 113 (2006) no. 3, pp. 435-454 | DOI | MR | Zbl

[13] Matsuda, Kazunori; Ohsugi, Hidefumi; Shibata, Kazuki Toric rings and ideals of stable set polytopes, Mathematics, Volume 7 (2019), p. 613 | DOI

[14] Ohsugi, Hidefumi; Hibi, Takayuki Convex polytopes all of whose reverse lexicographic initial ideals are squarefree, Proc. Amer. Math. Soc., Volume 129 (2001) no. 9, pp. 2541-2546 | DOI | MR | Zbl

[15] Ohsugi, Hidefumi; Hibi, Takayuki Special simplices and Gorenstein toric rings, J. Combin. Theory Ser. A, Volume 113 (2006) no. 4, pp. 718-725 | DOI | MR | Zbl

[16] Padberg, Manfred W. On the facial structure of set packing polyhedra, Math. Programming, Volume 5 (1973), pp. 199-215 | DOI | MR | Zbl

[17] Sbihi, N.; Uhry, J.-P. A class of h-perfect graphs, Discrete Math., Volume 51 (1984) no. 2, pp. 191-205 | DOI | MR | Zbl

Cited by Sources: