# Recurrence Relations and Hilbert Series of the Monoid Associated with Star Topology

Authors: Jiang-Hua Tang; Zaffar Iqbal; Abdul Rauf Nizami; Mobeen Munir; Faiza Azam; Jia-Bao Liu
Journal: Journal of Mathematics
 (2020)

---

## Abstract

Affine monoids are the considered as natural discrete analogues of the finitely generated cones. The interconnection between these two objects has been an active area of research since last decade. Star network is one of the most common in computer network topologies. In this work, we study star topologySn and associate a Coxeter structure of affine type on it. We find a recurrence relation and the Hilbert series of the associated right-angled monoid MSn∞. We observe that the growth rate of the monoid MSn∞ is unbounded.


---

## Body

## 1. Introduction

Hilbert series of a graded commutative algebra is strongly related with dimensions of the homogeneous components of the algebra. This notion has been extended to filtered algebras and coherent sheaves over projective schemes [1]. Hilbert series is treated as a special case of Hilbert–Poincaré series of a graded vector space and is closely related with the number of words of an alphabet. Hilbert series helps counting words on an alphabet that do not contain a fixed set of words. This is also named as well-known forbidden subwords problem which can be translated at the level of monomial algebras. If we are given an alphabet X=X1,X2,…,Xn and words W=W1,W2,…,Wd, then it is known that the numbers of words on X avoiding this word W is in one-to-one correspondence with monomials in X having nonzero image in the ring L=ℂX/W. If L is a finitely generated monoid, then the coefficients of its Hilbert series satisfy a recursive relation. Hilbert series of several popular algebras appear as power series of rational functions [2]. Things become interesting especially when the monoid L has a rational Hilbert series. This happens exactly when we have a finitely presented monoid. Significance of Hilbert series can be described in terms of the growth of a monoid. The growth of a monoid is said to be polynomially bounded if the nth coefficient of its Hilbert series is 0nd for some number d. A monoid has exponential growth if the nth coefficient is larger than Cn for some C>1. Interestingly, monoids should have polynomially bounded growths. The smallest-degree polynomial bounding the growth is one less than the Krull dimension. In noncommutative settings, topologists used growth to study fundamental groups. Milnor proved that if a compact Riemannian manifold has all its sectional curvatures negative, then its fundamental group has exponential growth, and if a complete n-dimensional Riemannian manifold has its mean curvature tensor everywhere positive semidefinite, then the finitely generated subgroup of its fundamental group has polynomially bounded growth. In short, a monoid has either an exponential growth or a polynomial growth. The degree of the growth is one less than the order of the pole at 1 of the Hibert series.Coxeter groups were introduced by Canadian geometer H. S. M. Coxeter in 1934 to solve the well-known famous word problem, namely, whether two words occurring in generators of the presentation of groups correspond to same element or not. These groups have nice other properties such as having faithful linear representations as groups of reflections. In a nontrivial way, it can be proved that these groups are abstract analogues of the regular polytopes. These polytopes are convex-hull of some points inℝn. Coxeter groups have generators ai,i∈I and have relations ai2=1 and aiajai=ajaiaj with i,j∈I; finite and infinite groups are usually referred as spherical and affine.Star topology is one of the important topologies used in networking and other real-world problems. One way to study this topology is by using Dynkin diagram [3] (or Coxeter graph), and other way is by using monoids. Note that the removal of the relations ai2=1 gives Artin groups. So, Coxeter groups are quotient groups of the Artin groups. A finite Coxeter group is a discrete acting group of reflections of a sphere [3]. That is why, they are known as spherical. The Artin braid group, An, is a spherical Coxeter groups. The Infinite Coxeter groups are generated by reflections in affine spaces [3].In 2009, Saito [4] found spherical growth series of Artin monoids [5]. In [6], we gave a linear system for the canonical words of the braid monoid MBn which lead to find Hilbert series of MBn. In [7], we computed Hilbert series of MB4 in band generators. In 2006, Mairesse and Mathéus [8] gave dihedral-type growth series of Artin groups. In 1993, Parry [9] gave the growth series of Coxeter groups. In [10], we proved that the upper bound of the growth of spherical Artin monoids is 4. But, in the affine case, this result is not true. In [11], we found a recurrence relation and Hilbert series of the associated right-angled affine Artin monoid MA˜n∞ and showed that its growth rate is unbounded. In [12], we found the Hilbert series of MD˜n∞ and showed that its growth rate is also unbounded.In this paper, we study the star topologySn and find recurrence relations and the Hilbert series of the associated right-angled monoid MSn∞. We also compute growth rate of the monoid MSn∞ and observe that it is unbounded.


## 2. Preliminaries

We start this section with the notion of Coxeter groups and Artin groups. We study the star topology as a Dynkin diagram and then convert it as a monoid. These basic preliminary facts and notations which will be required later for formulating our main results.Definition 1.
A square symmetric matrixM=msts,t∈S is said to be a Coxeter matrix over a nonempty set S such that all the diagonal entries are 1 and mst∈2,3,4,…,∞.Definition 2.
LetS be a set of vertices of a labeled graph Γ. We call Γ a Coxeter graph if any two of its vertices are connected by an edge and if the label of each edge is greater than 2.
By convention, each edge is labeled only if the label is greater than 3.Definition 3.
A group with generators and relations s2=1 and stmst=1 for all s,t∈S and mst≠∞ is called a Coxeter group such that msts,t∈S is the Coxeter matrix.Definition 4.
The Artin group is(1)A=s∈Ssts⋯︸mstfactors=tst⋯︸mstfactors.
If the Coxeter group is finite, thenA is called a spherical Artin group.Definition 5.
The right-angled Artin groups or monoids are obtained if all the labels, which are greater than or equal to 3, of spherical Coxeter graphs are replaced with∞.
The Artin spherical groups are usually represented by Coxeter graphs (see [3, 13]); these groups are An for n≥1, Bn for n≥2, Dn for n≥4, E6, E7, E8, F4, G2, H3, H4, and I2p for p≥5 and p≠6. Figure 1 contains these graphs.Figure 1
Spherical Coxeter graphs.Definition 6.
(see [14]). The length of a word g=s1,⋯,sn of a finitely generated group G is the smallest nonnegative integer n for which s1,…,sn∈S∪S−1, where S is the set of generators of G.Definition 7.
(see [14]). The spherical growth series of a finitely generated group G is HGt=∑k=0∞aktk, where ak is the number of words of length k.
Leta=b be a relation in a given monoid M. Then, in length-lexicographic order, a is greater then or equal to b. A word uwv has an ambiguity if uw and wv are left sides two relations. If α1v and uα2 are identical, then uwv is solvable. If α1v and uα2 differ by lexicographic order, then we get a new relation in M. A presentation is said to be complete if solutions of all ambiguities are identical. A reducible word is the left side of a relation of a complete presentation of a monoid. If w does not contain the LHS of any relation, then w is called a canonical word. The following notions are in [15–20] under different terminologies: Gröbner bases, complete presentation, rewriting system, and so on.


## 3. Main Results

In this part, we compute our main results.


### 3.1. Recurrence Relation of the MonoidMSn∞

In this paper, we study the star topologySn and find recurrence relations and the Hilbert series of the associated right-angled monoid MSn∞. We compute the growth rate of the monoid MSn∞, and using the graph, we show that it is unbounded. The Coxeter graph of the star topology Sn is given by the following graph (Figure 2):Figure 2
Sn.We denote the right-angled monoid associated withSn by MSn∞. In M, we fix a total order x1<x2<⋯<xn on the generators. Hence, clearly we have the following lemma.Lemma 1.
The monoidMSn∞ has generators x1,x2,…,xn and relations xixj=xjxi for 1≤j+1≤i≤n−1 and xnxk=xkxn for 2≤k≤n−2.
This section covers some useful results about recursive relations ofMSn∞: Consider a system [21] of linear relations:(2)uit+1=ai1tu1t+ai2tu2t+⋯+aintunt+fit,,1≤i≤n.
Equivalently,ut+1=Atut+ft, where(3)ut=u1t⋮unt,At=a11t⋯a1nt⋮⋱⋮an1t⋯annt,ft=f1t⋮fnt.
The solution of the systemut+1=Atut is ut=c1λ1tu1+⋯+ckλktuk, where λi and ui,1≤i≤k are, respectively, the eigenvalues and eigenvectors of At. The largest eigenvalue represents the growth rate of the sequence u1t,u2t,…,ukt.
In the following, byck and ck;i, we shall mean the number of canonical words of length k and words starting with xi.Lemma 2.
MSn∞ satisfies the relations c0=1, c1;i=1, and ck=∑i=1nck;i   k≥1, where ck;i is(4)ck;i=∑j=inck−1;j,1≤i≤n−1,ck;1,i=n.
LetSnλ denote the characteristic polynomial, then we have the following.Theorem 1.
The characteristic polynomialSnλ of the system of recursive relations of MSn∞ satisfies the relation:(5)Snλ=λSn−1λ−λλ−1n−2,where n≥2 and S1λ=λ−1.Proof.
The characteristic polynomial of the coefficient matrix of the system of recurrence relations given in Lemma2 is(6)Snλ=λ−1−1⋯−1−1−1−10λ−1⋯−1−1−1−1⋮⋮⋮⋮⋮⋮00⋯0λ−1−1−100⋯00λ−1−1−1−1⋯−1−1−1λ−1.
Adding the last row in the 2nd last row, we have(7)Snλ=λ−1−1⋯−1−1−1−10λ−1⋯−1−1−1−1⋮⋮⋮⋮⋮⋮00⋯0λ−1−1−1−1−1⋯−1−1λ−2λ−2−1−1⋯−1−1−1λ−1.
Now, subtracting the 2nd last column from the last column and simplifying, we haveSnλ=λTn−1λ, where(8)Tn−1λ=λ−1−1⋯−1−1−10λ−1⋯−1−1−1⋮⋮⋮⋮⋮00⋯−1λ−1−1−1−1⋯−1−1λ−2.
We writeTn−1λ=Un−1λ+Vn−1λ, where the determinants Un−1λ and Vn−1λ are obtained by splitting Tn−1λ such that the last row of Un−1λ is −1,…,−1,λ−1 and the last row of Vn−1λ is 0,…,0,−1. Hence, easily, we have Un−1λ=Sn−1λ and Vn−1λ=−λ−1n−2. Therefore, we have(9)Snλ=λSn−1λ−λλ−1n−2.
Here, we have an explicit formula forSnλ.Lemma 3.
InMSn∞, characteristic polynomial is given explicitly by(10)Snλ=λn−1λ−1−∑i=1n−1λiλ−1n−i−1.Proof.
From equation (5), we have Sn−kλ=λSn−k−1λ−λλ−1n−k−2,k≥0. Hence, we have(11)Snλ=λSn−1λ−λλ−1n−2=λ2Sn−2λ−λλ−1n−2−λ2λ−1n−3=λ3Sn−3λ−λλ−1n−2−λ2λ−1n−3−λ3λ−1n−4=λn−1Sn−n−1−∑i=1n−1λiλ−1n−i−1=λn−1λ−1−∑i=1n−1λiλ−1n−i−1.


### 3.2. Hilbert Series of the MonoidMSn∞

From now on,HMnt=∑k≥0cktk will denote the Hilbert series of MSn∞, and HM;int=∑k≥1ck;intk will denote the Hilbert series of MSn∞ of the words starting with xi.Following Lemma2 we get the following.Theorem 2.
ForMSn∞, we have(1)
HMnt=1+∑i=1nHM;int(2)
HM;int=t+t∑j=inHM;jnt,1≤i≤n−1(3)
HM;1nt=HM;nntProof.
(1)
Sinceck=∑i=1nck;i,k≥1, HMnt=∑k≥0cktk=c0+∑k≥1cktk=1+∑k≥1∑i=1nck;itk=1+∑i=1n∑k≥1ck;itk=1+∑i=1nHM;int.(2)
Also, from Lemma2, we have ck;i=∑j=inck−1;j1≤i≤n−1. Hence, HM;int=∑k≥1nck;ittk=c1;itt+∑k≥2nck;ittk=t+∑k≥2n∑j=inck−1;jttk=t+t∑j=in∑k≥2nck−1;jttk−1=t+t∑j=inHM;jnt.(3)
It can be proved similarly.
The linear system of Theorem2 takes the form WnX=B, where(12)Wn=1−t−t⋯−t−t−t01−t⋯−t−t−t00⋯−t−t−t⋮⋮⋮⋮⋮00⋯01−t−t−t−t⋯−t−t1−t,X=HM;1ntHM;2nt⋮HM;nnt,B=tt⋮t.Lemma 4.
ForMSn∞, we have HM;mnt=t1−tm−1/tnSn1/t,m=1,2,…,n−1.
For the system of equations given in Theorem2, we have the following.Lemma 5.
(13)detWn=tnSn1t.Proof.
It is obvious to Just factor outt from each row of detWn.Lemma 6.
(14)HM;mnt=t1−tm−1tnSn1/t,m=1,2,…,n−1.Proof.
The solution of the systemWnX=B is HM;mnt=Tm/detWn, where Tm is the determinant of the matrix obtained by replacing 0 in the mth column of Wn by B. That is,(15)Tm=1−t−t⋯−tt⋯−t−t01−t⋯−tt⋯−t−t00⋯−tt⋯−t−t⋮⋮⋮⋮⋮⋮00⋯0t⋯01−t.
Addingmth column of Tm to its column numbers m+1,m+2,…,n, we get HM;mnt=t1−tm−1/tnSn1/t,m=1,2,…,n−1.
The following result gives the Hilbert series ofMSn∞.Theorem 3.
(16)HMnt=1tnSn1/t.Proof.
Equation (5) gives tnSn1/t=tn−1Sn−11/t−t1−tn−2. Hence, Lemma 6 and Theorem 2 imply that(17)HMnt=1+HM;1nt+HM;2nt+⋯+HM;n−1nt+HM;nnt=1tnSn1/ttnSn1t+t+t1−t+t1−t2+⋯+t1−tn−2+t=1tnSn1/ttn−1Sn−11t+2t+t1−t+t1−t2+⋯+t1−tn−3=tS11/t−ttnSn1/t=1tnSn1/t.


### 3.3. Conclusions

Here, we gave, by constructing the affine-type Coxeter structure on star topology, a recursive relation and the Hilbert series of the right-angled monoidMSn∞ associated with a star graph. The main result is HMnt=1/tnSn1/t. We also computed the growth rate, rn, of MSn∞ using Mathematica; some initial values are: r3=2.618, r4=3.147, r5=3.629, r6=4.079, r7=4.506, r8=4.915, r9=5.309, r10=5.691, r11=6.063, r12=6.426, r13=6.781, r14=7.130, r15=7.472, r16=7.809, r17=8.141, r18=8.468, r19=8.790, r20=9.109. We also compute r40=14.93, r60=20.15, r80=25.04, r100=29.7, and r120=34.2. We have the following graph representing the behavior of the growth rate of Snλ (Figure 3)Figure 3
Sn∞.We observe that the growth rate forMSn∞ increases and is unbounded. Hence, at the end, we have the following natural open problem emerging from our research.An open problem: the growth rate ofMSn∞ is unbounded.


## 3.1. Recurrence Relation of the MonoidMSn∞

In this paper, we study the star topologySn and find recurrence relations and the Hilbert series of the associated right-angled monoid MSn∞. We compute the growth rate of the monoid MSn∞, and using the graph, we show that it is unbounded. The Coxeter graph of the star topology Sn is given by the following graph (Figure 2):Figure 2
Sn.We denote the right-angled monoid associated withSn by MSn∞. In M, we fix a total order x1<x2<⋯<xn on the generators. Hence, clearly we have the following lemma.Lemma 1.
The monoidMSn∞ has generators x1,x2,…,xn and relations xixj=xjxi for 1≤j+1≤i≤n−1 and xnxk=xkxn for 2≤k≤n−2.
This section covers some useful results about recursive relations ofMSn∞: Consider a system [21] of linear relations:(2)uit+1=ai1tu1t+ai2tu2t+⋯+aintunt+fit,,1≤i≤n.
Equivalently,ut+1=Atut+ft, where(3)ut=u1t⋮unt,At=a11t⋯a1nt⋮⋱⋮an1t⋯annt,ft=f1t⋮fnt.
The solution of the systemut+1=Atut is ut=c1λ1tu1+⋯+ckλktuk, where λi and ui,1≤i≤k are, respectively, the eigenvalues and eigenvectors of At. The largest eigenvalue represents the growth rate of the sequence u1t,u2t,…,ukt.
In the following, byck and ck;i, we shall mean the number of canonical words of length k and words starting with xi.Lemma 2.
MSn∞ satisfies the relations c0=1, c1;i=1, and ck=∑i=1nck;i   k≥1, where ck;i is(4)ck;i=∑j=inck−1;j,1≤i≤n−1,ck;1,i=n.
LetSnλ denote the characteristic polynomial, then we have the following.Theorem 1.
The characteristic polynomialSnλ of the system of recursive relations of MSn∞ satisfies the relation:(5)Snλ=λSn−1λ−λλ−1n−2,where n≥2 and S1λ=λ−1.Proof.
The characteristic polynomial of the coefficient matrix of the system of recurrence relations given in Lemma2 is(6)Snλ=λ−1−1⋯−1−1−1−10λ−1⋯−1−1−1−1⋮⋮⋮⋮⋮⋮00⋯0λ−1−1−100⋯00λ−1−1−1−1⋯−1−1−1λ−1.
Adding the last row in the 2nd last row, we have(7)Snλ=λ−1−1⋯−1−1−1−10λ−1⋯−1−1−1−1⋮⋮⋮⋮⋮⋮00⋯0λ−1−1−1−1−1⋯−1−1λ−2λ−2−1−1⋯−1−1−1λ−1.
Now, subtracting the 2nd last column from the last column and simplifying, we haveSnλ=λTn−1λ, where(8)Tn−1λ=λ−1−1⋯−1−1−10λ−1⋯−1−1−1⋮⋮⋮⋮⋮00⋯−1λ−1−1−1−1⋯−1−1λ−2.
We writeTn−1λ=Un−1λ+Vn−1λ, where the determinants Un−1λ and Vn−1λ are obtained by splitting Tn−1λ such that the last row of Un−1λ is −1,…,−1,λ−1 and the last row of Vn−1λ is 0,…,0,−1. Hence, easily, we have Un−1λ=Sn−1λ and Vn−1λ=−λ−1n−2. Therefore, we have(9)Snλ=λSn−1λ−λλ−1n−2.
Here, we have an explicit formula forSnλ.Lemma 3.
InMSn∞, characteristic polynomial is given explicitly by(10)Snλ=λn−1λ−1−∑i=1n−1λiλ−1n−i−1.Proof.
From equation (5), we have Sn−kλ=λSn−k−1λ−λλ−1n−k−2,k≥0. Hence, we have(11)Snλ=λSn−1λ−λλ−1n−2=λ2Sn−2λ−λλ−1n−2−λ2λ−1n−3=λ3Sn−3λ−λλ−1n−2−λ2λ−1n−3−λ3λ−1n−4=λn−1Sn−n−1−∑i=1n−1λiλ−1n−i−1=λn−1λ−1−∑i=1n−1λiλ−1n−i−1.


## 3.2. Hilbert Series of the MonoidMSn∞

From now on,HMnt=∑k≥0cktk will denote the Hilbert series of MSn∞, and HM;int=∑k≥1ck;intk will denote the Hilbert series of MSn∞ of the words starting with xi.Following Lemma2 we get the following.Theorem 2.
ForMSn∞, we have(1)
HMnt=1+∑i=1nHM;int(2)
HM;int=t+t∑j=inHM;jnt,1≤i≤n−1(3)
HM;1nt=HM;nntProof.
(1)
Sinceck=∑i=1nck;i,k≥1, HMnt=∑k≥0cktk=c0+∑k≥1cktk=1+∑k≥1∑i=1nck;itk=1+∑i=1n∑k≥1ck;itk=1+∑i=1nHM;int.(2)
Also, from Lemma2, we have ck;i=∑j=inck−1;j1≤i≤n−1. Hence, HM;int=∑k≥1nck;ittk=c1;itt+∑k≥2nck;ittk=t+∑k≥2n∑j=inck−1;jttk=t+t∑j=in∑k≥2nck−1;jttk−1=t+t∑j=inHM;jnt.(3)
It can be proved similarly.
The linear system of Theorem2 takes the form WnX=B, where(12)Wn=1−t−t⋯−t−t−t01−t⋯−t−t−t00⋯−t−t−t⋮⋮⋮⋮⋮00⋯01−t−t−t−t⋯−t−t1−t,X=HM;1ntHM;2nt⋮HM;nnt,B=tt⋮t.Lemma 4.
ForMSn∞, we have HM;mnt=t1−tm−1/tnSn1/t,m=1,2,…,n−1.
For the system of equations given in Theorem2, we have the following.Lemma 5.
(13)detWn=tnSn1t.Proof.
It is obvious to Just factor outt from each row of detWn.Lemma 6.
(14)HM;mnt=t1−tm−1tnSn1/t,m=1,2,…,n−1.Proof.
The solution of the systemWnX=B is HM;mnt=Tm/detWn, where Tm is the determinant of the matrix obtained by replacing 0 in the mth column of Wn by B. That is,(15)Tm=1−t−t⋯−tt⋯−t−t01−t⋯−tt⋯−t−t00⋯−tt⋯−t−t⋮⋮⋮⋮⋮⋮00⋯0t⋯01−t.
Addingmth column of Tm to its column numbers m+1,m+2,…,n, we get HM;mnt=t1−tm−1/tnSn1/t,m=1,2,…,n−1.
The following result gives the Hilbert series ofMSn∞.Theorem 3.
(16)HMnt=1tnSn1/t.Proof.
Equation (5) gives tnSn1/t=tn−1Sn−11/t−t1−tn−2. Hence, Lemma 6 and Theorem 2 imply that(17)HMnt=1+HM;1nt+HM;2nt+⋯+HM;n−1nt+HM;nnt=1tnSn1/ttnSn1t+t+t1−t+t1−t2+⋯+t1−tn−2+t=1tnSn1/ttn−1Sn−11t+2t+t1−t+t1−t2+⋯+t1−tn−3=tS11/t−ttnSn1/t=1tnSn1/t.


## 3.3. Conclusions

Here, we gave, by constructing the affine-type Coxeter structure on star topology, a recursive relation and the Hilbert series of the right-angled monoidMSn∞ associated with a star graph. The main result is HMnt=1/tnSn1/t. We also computed the growth rate, rn, of MSn∞ using Mathematica; some initial values are: r3=2.618, r4=3.147, r5=3.629, r6=4.079, r7=4.506, r8=4.915, r9=5.309, r10=5.691, r11=6.063, r12=6.426, r13=6.781, r14=7.130, r15=7.472, r16=7.809, r17=8.141, r18=8.468, r19=8.790, r20=9.109. We also compute r40=14.93, r60=20.15, r80=25.04, r100=29.7, and r120=34.2. We have the following graph representing the behavior of the growth rate of Snλ (Figure 3)Figure 3
Sn∞.We observe that the growth rate forMSn∞ increases and is unbounded. Hence, at the end, we have the following natural open problem emerging from our research.An open problem: the growth rate ofMSn∞ is unbounded.



---

*Source: 5215631-2020-08-27.xml*