Codegree and regularity of stable set polytopes
Koji Matsushita, Akiyoshi Tsuchiya · 2024
Read Codegree and regularity of stable set polytopes by Koji Matsushita, Akiyoshi Tsuchiya (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-10090.txt.
Introduction
Koji Matsushita and Akiyoshi Tsuchiya wrote a 2024 math paper on shapes tied to graphs. For any graph, the stable set shape gathers all sets of points with no edge between them. A key number for such a shape, its codegree, was not well known for this family.
The authors trap that number between two graph values: the size of the largest full linked group, and the least count of colors needed to color the graph. Both bounds shift by one to frame the codegree. For line graphs and one more graph class, they give an exact formula. They then use the results to bound a growth measure for the algebra ring tied to the shape.
Catalog record
| CREATOR | Koji Matsushita, Akiyoshi Tsuchiya |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 27 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-10090
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Codegree and regularity of stable set polytopes Koji Matsushita, Akiyoshi Tsuchiya Abstract . The codegree codeg ( 𝒫 ) {\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 𝒫 G {\mathcal{P}}_{G} associated with a simple graph G G . Specifically, we establish the inequalities ω ( G ) + 1 ≤ codeg ( 𝒫 G ) ≤ χ ( G ) + 1 , \omega(G)+1\leq{\rm codeg}({\mathcal{P}}_{G})\leq\chi(G)+1, where ω ( G ) \omega(G) and χ ( G ) \chi(G) denote the clique number and the chromatic number of G G , respectively. Furthermore, an explicit formula for codeg ( 𝒫 G ) {\rm codeg}({\mathcal{P}}_{G}) is given when G G is either a line graph or an h 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 𝒫 G {\mathcal{P}}_{G} . 2020 Mathematics Subject Classification 52B20, 05C15, 13C10 1. Introduction A lattice polytope is a convex polytope all of whose vertices have integer coordinates. Let {\mathcal{P}}\subset{\mathbb{R}}^{n} be a full-dimensional lattice polytope. Then the codegree of {\mathcal{P}} , denoted by {\rm codeg}({\mathcal{P}}) , is the smallest positive integer k such that the k th dilated polytope k{\mathcal{P}} of {\mathcal{P}} has an interior lattice point. On the other hand, the degree of {\mathcal{P}} , denoted by {\rm deg}({\mathcal{P}}) , is defined by {\rm deg}({\mathcal{P}})=n+1-{\rm codeg}({\mathcal{P}}) . Then {\rm deg}({\mathcal{P}}) coincides with the degree of the h^{*} -polynomial of {\mathcal{P}} , which encodes the number of lattice points in the dilatations of {\mathcal{P}} . The codegree and the degree are fundamental invariants of lattice polytopes, playing significant roles in various fields, particularly in discrete geometry and commutative algebra. See, e.g., [ 1 ] for detailed information for the degree and codegree of lattice polytopes. Throughout the present paper, we only treat simple graphs, which we simply call graphs instead of simple graphs. The stable set polytope {\mathcal{P}}_{G} associated with a graph G is the convex hull of the indicator vectors of all stable sets of G , where a set of vertices of G is called stable if no two of its elements are adjacent. In the present paper, we investigate the codegree of {\mathcal{P}}_{G} . The following is the first main result: Theorem 1.1 . Let G be a graph. Then one has \omega(G)+1\leq{\rm codeg}({\mathcal{P}}_{G})\leq\chi(G)+1, where \omega(G) and \chi(G) denote the clique number and the chromatic number of G, respectively. In particular, if G is perfect, then we obtain \omega(G)+1={\rm codeg}({\mathcal{P}}_{G})=\chi(G)+1. It is well known that \omega(G)\leq\chi(G) for any graph G . From the above theorem, we can regard {\rm codeg}({\mathcal{P}}_{G})-1 as an invariant lying between these two important invariants in graph theory. Furthermore, it is an important fact that there exists a graph G satisfying \omega(G)<{\rm codeg}({\mathcal{P}}_{G})-1<\chi(G) (see Example 5.1 ). Also, Theorem 1.1 implies that {\rm codeg}({\mathcal{P}}_{G}) can be computed by using invariants of the underlying graph G when G is a perfect graph. Next, for several classes of graphs, we give an explicit formula of {\rm codeg}({\mathcal{P}}_{G}) in terms of G . The matching polytope {\mathcal{M}}_{G} of G is the convex hull of the indicator vectors of all matchings of G , where a set of edges of G is called a matching if no two of its elements share a common endpoint. We can regard {\mathcal{M}}_{G} as the stable set polytope of the line graph of G . Namely, {\mathcal{M}}_{G}={\mathcal{P}}_{L(G)} , where L(G) denotes the line graph of G . Then an explicit formula for {\rm codeg}({\mathcal{M}}_{G}) is given as follows: Theorem 1.2 . Let G be a graph with connected components G_{1},\ldots,G_{r} . Then one has {\rm codeg}({\mathcal{M}}_{G})=\begin{cases}\Delta(G)+2&\left(\mbox{if $\Delta(G)$ is even and each $G_{i}$ with $\Delta(G_{i})=\Delta(G)$ is a complete graph}\right),\\ \Delta(G)+1&(\mbox{otherwise}),\end{cases} where \Delta(G) denotes the maximal degree of G . Note that \omega(L(G))=\Delta(G) unless G is a triangle, and if G is a complete graph with an odd number of vertices \geq 5 , then one has \Delta(G)+1=\omega(L(G))+1<{\rm codeg}({\mathcal{P}}_{L(G)})=\chi(L(G))+1=\Delta(G)+2. A graph is said to be h -perfect if {\mathcal{P}}_{G} is defined by the constraints corresponding to cliques and odd holes, and the nonnegativity constraints. Note that every perfect graph is h -perfect. Then for an h -perfect graph G , an explicit formula for {\rm codeg}({\mathcal{P}}_{G}) is given as follows: Theorem 1.3 . Let G be an h -perfect graph. Then one has \displaystyle{\rm codeg}({\mathcal{P}}_{G}) \displaystyle=\omega(G)+1. Note that if G is an odd cycle of length \geq 5 , then G is h -perfect and one has 3=\omega(G)+1={\rm codeg}({\mathcal{P}}_{G})<\chi(G)+1=4. Finally, we discuss the regularity of the toric ring of {\mathcal{P}}_{G} . In combinatorial commutative algebra, finding methods to evaluate algebraic invariants using combinatorial invariants is an important problem. For example, in [ 9 ] and [ 12 ] , the regularity of edge ideals is evaluated using invariants of the underlying graphs. Similarly, in this paper, we establish upper and lower bounds for the regularity of the toric rings of stable set polytopes in terms of invariants of the underlying graphs. For a lattice polytope {\mathcal{P}} , let K[{\mathcal{P}}] be the toric ring associated with {\mathcal{P}} over a field K and {\rm reg}(K[{\mathcal{P}}]) the regularity of K[{\mathcal{P}}] . As an application of Theorem 1.1 , we obtain the following. Theorem 1.4 . Let G be a graph with n vertices. Then one has n-\chi(G)\leq{\rm reg}(K[{\mathcal{P}}_{G}]). Moreover, if K[{\mathcal{P}}_{G}] is normal, then we obtain {\rm reg}(K[{\mathcal{P}}_{G}])\leq n-\omega(G). In particular, if G is perfect, then one has n-\chi(G)={\rm reg}(K[{\mathcal{P}}_{G}])=n-\omega(G). The present paper is organized as follows: In Section 2 , after recalling the definitions and properties of stable set polytopes and perfect graphs, we give a proof of Theorem 1.1 . Section 3 gives explicit formulas for {\rm codeg}({\mathcal{P}}_{G}) in the cases where G is a line graph or an h -perfect graph. In particular, Section 3.1 proves Theorem 1.2 , and Section 3.2 proves Theorem 1.3 . Section 4 discusses the regularity of K[{\mathcal{P}}_{G}] , with a focus on proving Theorem 1.4 . Finally, Section 5 considers examples related to the inequalities in Theorem 1.1 . 2. bounds on the codegree of stable set polytopes In this section, a proof of Theorem 1.1 is given. First, we recall the definition of stable set polytopes. Let G be a graph on [n]:=\{1,2,\ldots,n\} with edge set E(G) . A subset S\subset[n] is called a stable set (or an independent set ) of G if \{i,j\}\notin E(G) for all i,j\in S with i\neq j . In particular, the empty set \emptyset and any singleton \{i\} with i\in[n] are stable sets of G . Let S(G) be the set of all stable sets of G . For a subset A\subset[n] , we denote {\mathbf{e}}_{A}\in{\mathbb{R}}^{n} the indicator vector of A , namely, {\mathbf{e}}_{A}=\sum_{i\in A}{\mathbf{e}}_{i} , where {\mathbf{e}}_{i} is the i th unit coordinate vector in {\mathbb{R}}^{n} . Remark that {\mathbf{e}}_{\emptyset}=\mathbf{0}:=(0,\ldots,0)\in{\mathbb{R}}^{n} . Then the stable set polytope of G is defined as {\mathcal{P}}_{G}=\operatorname{conv}\{{\mathbf{e}}_{S}:S\in S(G)\}\subset{\mathbb{R}}^{n}. Note that \dim{\mathcal{P}}_{G} is equal to the number of vertices of G . Next, we define a perfect graph. A subset C\subset[n] is said to be clique of G if