Relational depth of transformation semigroups and their ideals N. Ruškuc, Z. Yayi Abstract . We introduce the concept of relational depth of a finite semigroup S S whose 𝒥 \mathcal{J} -classes form a chain. It captures how far down in the ideal structure one is obliged to go in order to define the semigroup by generators and defining relations. We determine the exact value for the relational depth of an arbitrary ideal in the full transformation monoid, symmetric inverse monoid and in the partial transformation monoid. 1991 Mathematics Subject Classification 20M05, 20M20 1. Introduction Generating sets and defining relations (presentations) for classical transformation semigroups – such as the partial transformation semigroup \mathcal{PT}_{n} , the full transformation semigroup \mathcal{T}_{n} , and the symmetric inverse semigroup \mathcal{I}_{n} – have over time received a lot of attention. For example, it is known that each of them is generated by the symmetric group (i.e. its group of units) together with one or two transformations of rank n-1 ; see [ 9 , Section 3.1] . Presentations for these semigroups were first established in [ 15 , 1 , 17 ] respectively. Another presentation for \mathcal{I}_{n} was given in [ 13 ] , and there is a nice exposition in [ 9 , Chapter 9] . All the known presentations for these semigroups have the property that every defining relation represents a transformation of rank n , n-1 or n-2 . Ideals of these semigroups have likewise been of interest. It is known that the ideal I_{m} consisting of all transformations of rank \leq m is generated by transformations of rank precisely m ; see [ 11 , Lemma 4] . Nice presentations for these ideals are much harder to find. There is some work on the largest proper ideal I_{n-1} [ 3 , 4 , 5 , 6 , 7 , 8 ] . These presentations are already quite large, but have the intriguing property that all the defining relations represent elements of ranks n-1 and n-2 only. Very recent relevant work includes: • [ 14 ] where Mitchell and Whyte investigate, and in certain cases determine, shortest (in terms of the number of defining relations) presentations for \mathcal{T}_{n} , \mathcal{I}_{n} and \mathcal{PT}_{n} . • [ 2 ] where the authors discuss a theoretical underpinning for some of the East’s singular presentations for [ 3 , 4 , 5 , 6 , 7 , 8 ] . The purpose of this paper is to investigate systematically how ‘deep’ inside the ideal structure of I_{m} one must go in order to define the semigroup I_{m} . We now make this idea more formal. Throughout this paper, we will consider semigroups S whose \mathcal{J} -classes form a chain J_{\epsilon}\theta , \mathcal{C}_{i} defines I_{m} if and only if i\leq 2m-n . Our Main Theorem follows from this and Proposition 3.1 . The rest of the paper is devoted to proving Theorem 3.3 , which is achieved in Theorem 6.11 , 7.12 , 8.19 for \mathcal{I}_{n},\mathcal{T}_{n} and \mathcal{PT}_{n} respectively. 4. Lower bound In this section we aim to find the lower bound for the depths of proper ideals of \mathcal{I}_{n},\mathcal{T}_{n} and \mathcal{PT}_{n} , by proving the following proposition. Proposition 4.1 . Consider mr>{\rm max}(2m-n,\epsilon) , then \mathcal{C}_{r}=\langle X_{r,m}\ |\ \mathcal{R}_{r,m}\rangle does not define I_{m} . We will derive Proposition 4.2 from the following technical, but more general, result: Proposition 4.3 . Let S be any finite semigroup whose \mathcal{J} -classes form a chain, J_{\epsilon}<\dotsr>{\rm max}(2m-n,1) , the \ker(\beta) -classes [m+1,2m-r] and [2m-r+1,n] are non-empty, and indeed \alpha,\beta\in J_{m} . With some calculation, it can be shown that \displaystyle\alpha\beta=\beta^{2}=\alpha\beta^{2} \displaystyle=\small\begin{pmatrix}1&2&\dots&r-2&[r-1,n]\\ 1&2&\dots&r-2&r-1\end{pmatrix}\in J_{r-1}. Hence, by Proposition 4.3 , the relation x_{\alpha}x_{\beta}^{2}=x_{\beta}^{2} cannot be deduced from \mathcal{R}_{r,m} , and \mathcal{C}_{r} does not define I_{m} . For S=\mathcal{I}_{n} or \mathcal{PT}_{n} , consider r>{\rm max}(2m-n,0) . Consider partial bijections \displaystyle\alpha=\small\begin{pmatrix}a_{1}&a_{2}&\dots&a_{m}\\ a_{1}&a_{2}&\dots&a_{m}\end{pmatrix},{\rm\ and\ }\beta=\small\begin{pmatrix}a_{1}&\dots&a_{r-1}&b_{r}&\dots&b_{m}\\ a_{1}&\dots&a_{r-1}&b_{r}^{\prime}&\dots&b_{m}^{\prime}\end{pmatrix}. The fact that r>2m-n guarantees that we can choose \image(\beta) such that \displaystyle\image(\beta)\cap\ker(\beta)=\{a_{1},\dots,a_{r-1}\}{\rm\ and\ }\alpha\beta=\alpha\beta^{2}=\beta^{2}=\small\begin{pmatrix}a_{1}&\dots&a_{r-1}\\ a_{1}&\dots&a_{r-1}\end{pmatrix}\in J_{r-1}. From here we proceed as for \mathcal{T}_{n} . ∎ Proof of Proposition 4.1 . Immediate consequence of Proposition 4.2 . ∎ Furthermore, we now know the exact depths of small ideals. Corollary 4.5 . Let I_{m} be an ideal of S\in\{\mathcal{PT}_{n},\mathcal{I}_{n},T_{n}\} . Define \epsilon=0 for S\in\{\mathcal{PT}_{n},\mathcal{I}_{n}\} and \epsilon=1 when S=\mathcal{T}_{n} . If m\leq\frac{n+\epsilon}{2} , then \depth(I_{m})=m+1 . Proof. Follows from Proposition 4.1 . ∎ Remark 4.6 . Similar issues are treated by Mitchell and Whyte in [ 14 ] in their analysis of minimal presentations in terms of the number of defining relations. For example, in Lemmas 3.6, 3.7 they show that to define the symmetric inverse monoid \mathcal{I}_{n} one has to use at least two relations of depth (in our terminology) n-1 and at least one of depth n-2 . Similar assertions are proved for \mathcal{T}_{n} and \mathcal{PT}_{n} in the subsequent sections of that paper. 5. Upper bound: Preliminaries In this section, we state and prove some technical lemmas that will subsequently be used to find the upper bounds for the relational depths of \mathcal{I}_{n} , \mathcal{T}_{n} , and \mathcal{PT}_{n} . For now, consider S\in\{\mathcal{I}_{n},\mathcal{T}_{n},\mathcal{PT}_{n}\} . Then S=J_{\epsilon}\cup\dots\cup J_{n} , where \epsilon=0\text{ if }S\in\{\mathcal{PT}_{n},\mathcal{I}_{n}\}\text{, and }\epsilon=1\text{ if }S=\mathcal{T}_{n} . The following lemma states the three conditions for deducing relations of rank r in an ideal I_{m} using relations from \mathcal{R}_{r+1,m} . Lemma 5.1 . Let I_{m} be an ideal of S , then I_{m}=J_{\epsilon}\cup\dots\cup J_{m} . Let r\leq 2m-n-1 . Suppose that the following statements hold. (P1) For \alpha,\beta,\gamma,\delta\in J_{r+1} , if \alpha\beta=\gamma\delta\in J_{r} , then we can deduce the relation x_{\alpha}x_{\beta}=x_{\gamma}x_{\delta} using relations in \mathcal{R}_{r+1,m} . (P2) For \alpha,\beta,\gamma\in J_{r+1} , if \alpha\beta,\beta\gamma,\alpha\beta\gamma\in J_{r} , then we can obtain a word x_{\alpha^{\prime}}x_{\gamma^{\prime}} from x_{\alpha}x_{\beta}x_{\gamma} , where \alpha^{\prime},\gamma^{\prime}\in J_{r+1} using relations in \mathcal{R}_{r+1,r+2} . (P3) For \gamma\delta\in J_{r} , if \rank(\gamma),\rank(\delta)\geq r+1 , we can obtain a word x_{\alpha}x_{\beta} from x_{\gamma}x_{\delta} , where \alpha,\beta\in J_{r+1} using relations in \mathcal{R}_{r+1,m} . Then the following are true: (i) For any \alpha_{1},\dots,\alpha_{k}\in J_{r+1}\cup\dots\cup J_{m} such that \alpha_{1}\dots\alpha_{k}\in J_{r} , there exist \gamma,\delta\in J_{r+1} such that \beta\gamma=\alpha_{1}\alpha_{2}\dots\alpha_{k} , and x_{\beta}x_{\gamma}=x_{\alpha_{1}}x_{\alpha_{2}}\dots x_{\alpha_{k}} is a consequence of \mathcal{R}_{r+1,m} . (ii) If \epsilon\leq r\leq 2m-n-1 , and w,v are words that represent the same rank- r element, then we can obtain v from w using \mathcal{R}_{r+1,m} . Proof. (i) For w=x_{\alpha_{1}}x_{\alpha_{2}}\dots x_{\alpha_{k}} , define r(w)=\sum_{i=1}^{k}\rank(\alpha_{i}) . Let w=x_{\alpha_{1}}\dots x_{\alpha_{k}} be a word that satisfies the condition of the theorem. Consider the following claim. Claim 1 . If r(w)>2r+2 , then there exist w^{\prime}=x_{\alpha_{1}^{\prime}}\dots x_{\alpha_{l}^{\prime}} such that (a) \alpha_{1}^{\prime},\dots,\alpha_{l}^{\prime}\in J_{r+1}\cup\dots\cup J_{m} (b) w=w^{\prime} is a consequence of \mathcal{R}_{r+1,m} (c) r(w^{\prime})r+1 or \rank(\alpha_{2})>r+1 , then by (P3) , there exist \alpha_{1}^{\prime},\alpha_{2}^{\prime}\in J_{r+1} such that x_{\alpha_{1}^{\prime}}x_{\alpha_{2}^{\prime}} can be obtained from x_{\alpha_{1}}x_{\alpha_{2}} using \mathcal{R}_{r+1,m} . Clearly r(\alpha_{1}\alpha_{2})2r+2 and r(\alpha_{1}\alpha_{2})=2r+2 , we have k\geq 3 . Consider the prefix x_{\alpha_{1}}x_{\alpha_{2}}x_{\alpha_{3}} . Since \rank(\alpha_{2}\alpha_{3})\leq\rank(\alpha_{2})=r+1 , we have \alpha_{2}\alpha_{3}\in J_{r}\cup J_{r+1} . If \alpha_{2}\alpha_{3}\in J_{r+1} , then x_{\alpha_{2}}x_{\alpha_{3}}=x_{\alpha_{2}\alpha_{3}} is a relation in \mathcal{R}_{r+1,m} . Therefore r(x_{\alpha_{1}}x_{\alpha_{2}\alpha_{3}}x_{\alpha_{4}}\dots x_{\alpha_{k}})r , and x_{\beta}\in X_{r+1,m} . Similarly, either x_{\gamma}=u_{\gamma} is a relation in P_{1} , or x_{\gamma}\in X_{r+1,m} . We consider the 4 possible combinations of the ranks of \beta and \gamma . If \beta,\gamma\in J_{r} , then x_{\beta}x_{\gamma},u_{\beta\gamma}\in X_{r+1,m}^{+} such that they represent the same rank- r map. Then x_{\beta}x_{\gamma}=u_{\beta\gamma}\in R_{r}^{\prime} and is a consequence of \mathcal{C}_{r+1} and hence P_{1} . If \beta,\gamma\in J_{r} , since u_{\beta}=x_{\beta},u_{\gamma}=x_{\gamma} are relations in P_{1} , and u_{\beta}u_{\gamma}=u_{\beta\gamma}\in R_{r}^{\prime} , we can deduce x_{\beta}x_{\gamma}=x_{\beta\gamma} from P_{1} . If exactly one of \beta and \gamma is of rank r , say \beta\in J_{r} and \gamma\notin J_{r} , then x_{\beta}=u_{\beta} is a relation in P_{1} . The words u_{\beta}x_{\gamma},u_{\beta\gamma}\in X_{r+1,m}^{+} represent the same map \beta\gamma , so u_{\beta}x_{\gamma}=u_{\beta\gamma}\in R_{r}^{\prime} and is a consequence of \mathcal{C}_{r} and hence P_{1} . A similar argument holds for the case when \beta\notin J_{r} and \gamma\in J_{r} . In all cases R_{r}^{\prime\prime} follows from P_{1} . So adding R_{r}^{\prime\prime} we obtain P_{2} . Notice that \mathcal{R}_{r,m}=\mathcal{R}_{r+1,m}\cup\{x_{\beta}x_{\gamma}=x_{\beta\gamma}\colon\beta\in J_{r}{\rm\ or\ }\gamma\in J_{r}{\ \rm or\ }\beta\gamma\in J_{r}\}=\mathcal{R}_{r+1,m}\cup R_{r}^{\prime\prime} , so P_{2}=\langle X_{r,m}\ |\ \mathcal{R}_{r,m},x_{\alpha}=u_{\alpha}\ (\alpha\in J_{r})\rangle . Step 3 : Consider a relation of the form x_{\alpha}=u_{\alpha} where \alpha\in J_{r} . We have u_{\alpha}\equiv x_{\alpha_{1}}x_{\alpha_{2}}\dots x_{\alpha_{k}}\in X_{r+1,m}^{+} . The sequence of relations x_{\alpha_{1}\alpha_{2}\dots\alpha_{k}}=x_{\alpha_{1}}x_{\alpha_{2}\dots\alpha_{k}}=\dots=x_{\alpha_{1}}x_{\alpha_{2}}\dots x_{\alpha_{k}} is a consequence of \langle X_{r,m}\ |\ \mathcal{R}_{r,m}\rangle . Therefore removing \{x_{\alpha}=u_{\alpha}\colon\alpha\in J_{r}\} from P_{2} we obtain \mathcal{C}_{r} . ∎ Theorem 5.3 . Suppose that for \epsilon\leq r\leq 2m-n-1 , S satisfies \ref{P1}-\ref{P3} . Let s=2m-n . Then \mathcal{C}_{s} defines a presentation for I_{m} . Proof. By repeatedly applying Proposition 5.2 , C_{\epsilon},C_{\epsilon+1},...,C_{s} all define the same semigroup. However, C_{\epsilon} is the Cayley table of I_{m} , and hence defines I_{m} itself. ∎ Given a semigroup \mathcal{S} where \mathcal{S} is one of \mathcal{I}_{n},\mathcal{T}_{n},\mathcal{PT}_{n} or their ideals, we have established a way of proving that a given depth is an upper bound for \depth(\mathcal{S}) by proving that (P1) - (P3) hold. In Sections 6 , 7 , and 8 , we will find out the conditions when (P1) - (P3) are satisfied for \mathcal{I}_{n} , \mathcal{T}_{n} and \mathcal{PT}_{n} respectively, therefore obtaining an upper bound for the depth of each of them. 6. Upper bound for \mathcal{I}_{n} In this section we consider the upper bound for the relational depth of ‘large’ ideals I_{m} in \mathcal{I}_{n} , where m>\frac{n}{2} . This is achieved in Proposition 6.10 . Together with Proposition 4.1 , this will yield Theorem 3.3 for \mathcal{I}_{n} . Suppose that I_{m} is a proper ideal of \mathcal{I}_{n} , and that rm>\frac{n}{2} , then \depth(I_{m})\leq n-m+1 . Proof. We have proved in Lemmas 6.7 - 6.9 that when m>\frac{n}{2} , \ref{P1}-\ref{P3} hold. It follows from Theorem 5.3 that \depth(I_{m})\leq m-(2m-n)+1=n-m+1 . ∎ Theorem 6.11 . Let I_{m} be an ideal of \mathcal{I}_{n} . Then \depth(I_{m})=\begin{cases}3&m=n\\ n-m+1&n>m>\frac{n}{2}\\ m+1&m\leq\frac{n}{2}\end{cases} . Proof. When m\leq\frac{n}{2} , the exact value for \depth(I_{m}) is given in Corollary 4.5 . When n>m>\frac{n}{2} , the lower bound for \depth(I_{m}) is found in Proposition 4.1 , which is shown to be an upper bound in Proposition 6.10 . Finally, we know that \depth(\mathcal{I}_{n})\leq 3 , as \depth(I_{n-1})=2 . Consider partial bijections \displaystyle\alpha=\small\begin{pmatrix}1&2&\dots&n-1\\ 1&2&\dots&n-1\end{pmatrix},\beta=\small\begin{pmatrix}1&\dots&n-2&n\\ 1&\dots&n-2&n-1\end{pmatrix}. Then \alpha\beta^{2}=\alpha\beta=\beta^{2}=\small\begin{pmatrix}1&2&...&n-2\\ 1&2&...&n-2\end{pmatrix}. However, we cannot obtain x_{\alpha}{x_{\beta}}^{2} from {x_{\beta}}^{2} using relations from \mathcal{R}_{n-1,n} , as \alpha,\beta satisfy the condition in Proposition 4.3 . Hence \mathcal{C}_{n-1}=\langle X_{n-1,n}\ |\ \mathcal{R}_{n-1,n}\rangle does not define a presentation for \mathcal{I}_{n} , and \depth(\mathcal{I}_{n})>2 , which gives \depth(\mathcal{I}_{n})=3 . ∎ 7. Upper bound for \mathcal{T}_{n} We now move to the ideals of the full transformation monoid \mathcal{T}_{n} . We follow the same trajectory as in the previous section, but technical details are different due to the different nature of the elements of \mathcal{T}_{n} compared to \mathcal{I}_{n} . To begin with, we find some relations that can be deduced from \mathcal{R}_{r,m} in an ideal I_{m} of \mathcal{T}_{n} . Let 1\leq r1 , change \ker(\delta) by moving a_{l} from D_{j} to D_{l} (iii) . Otherwise, |D_{j}|=1 . In that case, change \ker(\delta) by moving c^{\prime}\notin\{a_{l}\}\cup\image(\gamma) to D_{j} (iii) . Then change \image(\gamma) by swapping c_{j}=a_{l} for c^{\prime} (ii) , and \ker(\delta) by moving a_{l} from D_{j} to D_{l} (iii) . Step 2 : Change \image(\gamma) by changing the image of X_{l} from c_{l} to a_{l} (ii) . Define the resulting map to be \gamma_{l} and \delta^{\prime} . Next, we repeat the above until every element in \image(\gamma) is changed to an element in \image(\alpha) accordingly. To avoid ambiguity in the notation, we need to update the definition for \gamma and \delta , as well as keeping track of the number of repetitions of Step 1 and 2. Step 3 : If l=r+1 , go to the next Step. Otherwise, let \gamma=\gamma_{l} , \delta=\delta^{\prime} , l=l+1 , and go back to Step 1. So far we have obtained \gamma_{r+1} , where \image(\gamma_{r+1})=\image(\alpha) . Since i=k , we have obtained x_{\alpha}x_{\delta^{\prime}} from x_{\gamma}x_{\delta} . Finally, we show that we can obtain x_{\alpha}x_{\beta} from x_{\alpha}x_{\delta}^{\prime} . Step 4 : Using rule (iii) , we may obtain \beta^{\prime} from \delta^{\prime} by moving elements between the kernel classes of \delta^{\prime} , where \ker(\beta^{\prime})=\ker(\beta) . Step 5 : We obtain \beta from \beta^{\prime} , by changing the image of B_{r+1} from z to y (i) . We have obtained x_{\alpha}x_{\beta} from x_{\alpha}x_{\delta^{\prime}} , completing the case. Case 2 : i\neq k . We show that we could obtain \gamma^{\prime} from \gamma using the rules from the corollary, such that \gamma^{\prime} and \alpha satisfy the condition for Case 1. Step 1 : If |D_{i}|\neq 1 , let c\in D_{i}\setminus\{c_{i}\} , and go to Step 2. Otherwise, if |D_{i}|=1 , change \ker(\delta) by moving c\in[n]\setminus\image(\gamma) to D_{i} (iii) . Step 2 : Rule (iv) allows us to change the kernel classes of \gamma and obtain \gamma^{\prime} such that \gamma^{\prime}=\small\begin{pmatrix}X_{1}&\dots&X_{i-1}&X_{i1}&X_{i2}&X_{i+1}\dots&X_{k}&\dots&X_{r}\\ c_{1}&\dots&c_{i-1}&c_{i}&c&c_{i+1}\dots&c_{k1}&\dots&c_{r}\end{pmatrix}. Step 3 : Now \gamma^{\prime} and \alpha satisfy the condition for Case 1. Apply the method in Case 1. ∎ Recall that, if n>m\geq 2 , \depth(I_{m})\geq 2 by Proposition 4.1 . It follows that a presentation for I_{m} must contain at least relations of rank m and m-1 . As a result, from now on, we consider m>\frac{n+1}{2},2\leq r\leq{\rm min}\{m-2,2m-n-1\}=2m-n-1 . Lemma 7.9 . Let 1\leq r\leq 2m-n-1 . If \alpha,\beta,\gamma\in J_{r+1},\alpha\beta,\beta\gamma,\alpha\beta\gamma\in J_{r} , then a relation of the form x_{\alpha}x_{\beta}x_{\gamma}=x_{\alpha^{\prime}}x_{\gamma} where \alpha^{\prime} is some map in J_{r+1} , is a consequence of \mathcal{R}_{r+1,r+2} . Proof. Let \displaystyle\alpha=\small\begin{pmatrix}A_{1}&A_{2}&\dots&A_{r+1}\\ a_{1}&a_{2}&\dots&a_{r+1}\end{pmatrix},\ \beta=\small\begin{pmatrix}B_{1}&B_{2}&\dots&B_{r+1}\\ b_{1}&b_{2}&\dots&b_{r+1}\end{pmatrix},\ \gamma=\small\begin{pmatrix}C_{1}&C_{2}&\dots&C_{r+1}\\ c_{1}&c_{2}&\dots&c_{r+1}\end{pmatrix}. Since \alpha\beta,\beta\gamma,\alpha\beta\gamma\in D_{r} , \image(\alpha) intersects with r of \ker(\beta) -classes, and \image(\beta),\image(\alpha\beta) intersect with r of \ker(\gamma) -classes. Therefore the \ker(\gamma) -class that contains two elements in \image(\beta) only contains one element from \image(\alpha\beta) . We may assume that a_{r},a_{r+1}\in B_{r} , and for 1\leq i\leq r-1 , a_{i}\in B_{i} , and \image(\alpha\beta)=\{b_{1},\dots,b_{r}\} . Then if i\neq j\leq r , b_{i}\gamma\neq b_{j}\gamma . Hence we may let b_{i}\in C_{i} for i\leq r-1 , and b_{r},b_{r+1}\in C_{r} . Then \alpha\beta\gamma=\small\begin{pmatrix}A_{1}&A_{2}&\dots&A_{r-1}&A_{r}\cup A_{r+1}\\ c_{1}&c_{2}&\dots&c_{r-1}&c_{r}\end{pmatrix}. Let b\in C_{r+1} . Define \beta^{\prime}=\small\begin{pmatrix}B_{1}&B_{2}&\dots&B_{r+1}\\ b_{1}&b_{2}&\dots&b\end{pmatrix},\alpha^{\prime}=\small\begin{pmatrix}A_{1}&A_{2}&\dots&A_{r}&A_{r+1}\\ b_{1}&b_{2}&\dots&b_{r}&b_{r+1}\end{pmatrix}\in J_{r+1}. Then by Lemma 7.1 , \alpha\beta=\alpha\beta^{\prime} , and x_{\alpha}x_{\beta}=x_{\alpha}x_{\beta^{\prime}} is a consequence of \mathcal{R}_{r+1,r+2} . Notice that \beta^{\prime}\gamma=\small\begin{pmatrix}B_{1}&B_{2}&\dots&B_{r+1}\\ c_{1}&c_{2}&\dots&c_{r+1}\end{pmatrix}\in J_{r+1},\text{ and }\alpha^{\prime}\gamma=\small\begin{pmatrix}A_{1}&\dots&A_{r-1}&A_{r}\cup A_{r+1}\\ c_{1}&\dots&c_{r-1}&c_{r}\end{pmatrix}=\alpha\beta^{\prime}\gamma. Hence we have \displaystyle\begin{aligned} x_{\alpha}x_{\beta}x_{\gamma}&=x_{\alpha}x_{\beta^{\prime}}x_{\gamma}\ \ &&(x_{\alpha}x_{\beta}=x_{\alpha}x_{\beta^{\prime}})\\ &=x_{\alpha}x_{\beta^{\prime}\gamma}\ \ &&(x_{\beta^{\prime}}x_{\gamma}=x_{\beta^{\prime}\gamma}{\rm\ is\ a\ relation\ in}\ \mathcal{R}_{r+1,r+2})\\ &=x_{\alpha^{\prime}}x_{\gamma}\ \ &&({\rm Lemma}\ \ref{lem: Tn: all length-2 words obtained from r+1,r+2}).\end{aligned} ∎ Lemma 7.10 . Let 1\leq r\leq 2m-n-1 . If \gamma\delta\in J_{r} where \rank(\gamma),\rank(\delta)\geq r+1 , there exist \alpha,\beta\in J_{r+1} such that \alpha\beta=\gamma\delta , and x_{\alpha}x_{\beta}=x_{\gamma}x_{\delta} is a consequence of \mathcal{R}_{r+1,m} . Proof. Consider \gamma,\delta where \rank(\gamma)=i,\rank(\delta)=j . Let \gamma=\small\begin{pmatrix}C_{1}&C_{2}&\dots&C_{i}\\ c_{1}&c_{2}&\dots&c_{i}\end{pmatrix},\text{ and }\delta=\small\begin{pmatrix}D_{1}&D_{2}&\dots&D_{j}\\ d_{1}&d_{2}&\dots&d_{j}\end{pmatrix}. Since \rank(\gamma\delta)=r , the elements in \image(\gamma) belong to r of \ker(\delta) -classes, D_{1},D_{2},\dots,D_{r} , say. Relabel the \ker(\gamma) -classes and their images, \gamma=\small\begin{pmatrix}C_{11}&\dots&C_{1k_{1}}&C_{21}&\dots&C_{2k_{2}}&\dots&C_{r1}&\dots&C_{rk_{r}}\\ c_{11}&\dots&c_{1k_{1}}&c_{21}&\dots&c_{2k_{2}}&\dots&c_{r1}&\dots&c_{r{k_{r}}}\end{pmatrix}, where k_{l}=|D_{l}\cap\image(\gamma)| , and \{c_{l1},\dots,c_{lk_{l}}\}\subseteq{D_{l}} for 1\leq l\leq r . Notice that with the assumption r\leq 2m-n-1 , it is not possible that \gamma,\delta\in J_{m} whereas \gamma\delta\in J_{r} . In the following, we can exclude the situation when i=j=m . Case 1 : r+1\leq i\leq j\leq m . Let c\in D_{r+1} . Define \gamma_{1}=\small\begin{pmatrix}c_{11}&\dots&c_{1k_{1}}&\dots&c_{r1}&\dots&c_{rk_{r}}&[n]\setminus\{c_{11},\dots,c_{rk_{r}}\}\\ c_{11}&\dots&c_{1k_{1}}&\dots&c_{r1}&\dots&c_{r{k_{r}}}&c\end{pmatrix}\in J_{i+1}, and \delta_{1}=\small\begin{pmatrix}\{c_{11},\dots,c_{1k_{1}}\}&\{c_{21},\dots,c_{2k_{2}}\}&\dots&\{c_{r1},\dots,c_{rk_{r}}\}&[n]\setminus\{c_{11},\dots,c_{rk_{r}}\}\\ d_{1}&d_{2}&\dots&d_{r}&d_{r+1}\end{pmatrix}. Then we have \gamma\gamma_{1}=\gamma , and \gamma_{1}\delta=\delta_{1} . Notice that \gamma_{1},\delta_{1}\in J_{r+1}\cup\dots\cup J_{m} , hence \displaystyle\begin{aligned} x_{\gamma}x_{\delta}&=x_{\gamma}x_{\gamma_{1}}x_{\delta}\ \ &&(x_{\gamma}=x_{\gamma}x_{\gamma_{1}}\ {\rm\ is\ a\ relation\ in\ }\mathcal{R}_{r+1,m})\\ &=x_{\gamma}x_{\delta_{1}}\ \ &&(x_{\delta_{1}}=x_{\gamma_{1}}x_{\delta}\ {\rm\ is\ a\ relation\ in\ }\mathcal{R}_{r+1,m})\end{aligned} is a consequence of \mathcal{R}_{r+1,m} . Case 2 : r+1\leq jr+1 , there exists a \ker(\delta) -class that contains at least 2 elements of \image(\gamma) . Here, we consider the situation where k_{r}\geq 2 , and the proofs for other cases are similar. Let c_{r1},c_{r2}\in D_{r} . For r+1\leq i\leq j , let d_{i}^{\prime}\in D_{i} . Define \displaystyle\delta_{1} \displaystyle=\small\begin{pmatrix}D_{1}&\dots&D_{r-1}&c_{r1}&D_{r}\setminus\{c_{r1}\}&D_{r+1}&\dots&D_{j}\\ c_{11}&\dots&c_{(r-1)1}&c_{r1}&c_{r2}&d_{r+1}^{\prime}&\dots&d_{j}^{\prime}\end{pmatrix}, \displaystyle\gamma_{1} \displaystyle=\small\begin{pmatrix}\cup^{k_{1}}_{i=1}C_{1i}&\dots&\cup^{k_{r-1}}_{i=1}C_{(r-1)i}&C_{r1}&\cup^{k_{r}}_{i=2}C_{ri}\\ c_{11}&\dots&c_{(r-1)1}&c_{r1}&c_{r2}\end{pmatrix}. We have \delta_{1}\delta=\delta , \gamma\delta_{1}=\gamma_{1} , and \gamma_{1}\in J_{r+1},\ \delta_{1}\in J_{j+1} . Hence x_{\gamma}x_{\delta}=x_{\gamma}x_{\delta_{1}}x_{\delta}=x_{\gamma_{1}}x_{\delta} is a consequence of \mathcal{R}_{r+1,m} . Now if \gamma\in D_{i} and \delta\in D_{j} such that r+1\leq i\leq j\leq m , apply the method in Case 1 to x_{\gamma}x_{\delta} and obtain a word u . If u contains a letter that represents a map of rank greater than s , apply the method in Case 2 to u . The resulting word should be made up of two letters that represent maps of rank r+1 . Otherwise, if \gamma\in D_{i} and \delta\in D_{j} such that r+1\leq jm>\frac{n+1}{2} , then \depth(I_{m})\leq n-m+1 . Proof. We have proved in Lemma 7.8 - 7.10 that when m>\frac{n+1}{2} , \ref{P1}-\ref{P3} hold. It follows from Theorem 5.3 that \depth(I_{m})\leq m-(2m-n)+1=n-m+1 . ∎ Theorem 7.12 . Let I_{m} be an ideal of \mathcal{T}_{n} . Then \depth(I_{m})=\begin{cases}3&m=n\\ n-m+1&m>\frac{n+1}{2}\\ m&m\leq\frac{n+1}{2}\end{cases} . Proof. When m\leq\frac{n+1}{2} , the exact value for \depth(I_{m}) is given in Corollary 4.5 . When n>m>\frac{n+1}{2} , the lower bound for \depth(I_{m}) is found in Proposition 4.1 , which is shown to be an upper bound in Proposition 7.11 . Finally, we know that \depth(\mathcal{T}_{n})\leq 3 , as \depth(I_{n-1})=2 . Consider transformations \displaystyle\alpha=\small\begin{pmatrix}1&2&\dots&n-2&\{n-1,n\}\\ 1&2&\dots&n-2&n-1\end{pmatrix},\beta=\small\begin{pmatrix}1&\dots&n-3&\{n-2,n-1\}&n\\ 1&\dots&n-3&n-2&n-1\end{pmatrix}. Then \alpha\beta^{2}=\alpha\beta=\beta^{2}=\small\begin{pmatrix}1&2&...&n-3&[n-2,n]\\ 1&2&...&n-3&n-2\end{pmatrix}\in J_{n-2}. However, we cannot obtain x_{\alpha}{x_{\beta}}^{2} from {x_{\beta}}^{2} using relations from \mathcal{R}_{n-1,n} , as \alpha,\beta satisfy the condition in Proposition 4.3 . Hence \mathcal{C}_{n-1}=\langle X_{n-1,n}\ |\ \mathcal{R}_{n-1,n}\rangle does not define a presentation for \mathcal{T}_{n} , and \depth(\mathcal{T}_{n})>2 , which gives \depth(\mathcal{T}_{n})=3 . ∎ 8. Upper bound for \mathcal{PT}_{n} Finally, we look at ideals of \mathcal{PT}_{n} . Assume that, unless stated otherwise, \displaystyle\alpha \displaystyle=\small\begin{pmatrix}A_{1}&A_{2}&\dots&A_{r}&A_{r+1}\\ a_{1}&a_{2}&\dots&a_{r}&a_{r+1}\end{pmatrix},\ \beta=\small\begin{pmatrix}B_{1}&B_{2}&\dots&B_{r}&B_{r+1}\\ b_{1}&b_{2}&\dots&b_{r}&b_{r+1}\end{pmatrix}. Define A=[n]\setminus\dom(\alpha),B=[n]\setminus\dom(\beta) . We consider the two possible ways of obtaining a partial map of rank r from a composition of two rank- (r+1) partial maps. Case 1 : \image(\alpha)\subseteq\dom(\beta) . In this case both a_{r},a_{r+1}\in B_{r} , and \alpha\beta=\small\begin{pmatrix}A_{1}&A_{2}&\dots&A_{r-1}&A_{r}\cup A_{r+1}\\ b_{1}&b_{2}&\dots&b_{r-1}&b_{r}\end{pmatrix}. Case 2 : |\image(\alpha)\ \cap\dom(\beta)^{c}|=1 . In this case we have a_{r+1}\in B , and \alpha\beta=\small\begin{pmatrix}A_{1}&A_{2}&\dots&A_{r-1}&A_{r}\\ b_{1}&b_{2}&\dots&b_{r-1}&b_{r}\end{pmatrix}. \mathcal{T}_{n} has a similar pattern to Case 1, and \mathcal{I}_{n} is like Case 2. In fact, some of the results that were established in Sections 6 and 7 can also be applied to \mathcal{PT}_{n} with some generalisations. Therefore we will not repeat the arguments that are the same in the previous sections. First we consider Case 1. Lemma 8.1 . Let b_{r+1}^{\prime}\in[n]\setminus\image(\beta) . Define \beta^{\prime}=\small\begin{pmatrix}B_{1}&B_{2}&\dots&B_{r}&B_{r+1}\\ b_{1}&b_{2}&\dots&b_{r}&b_{r+1}^{\prime}\end{pmatrix}. Then \alpha\beta=\alpha\beta^{\prime} , and the relation x_{\alpha}x_{\beta}=x_{\alpha}x_{\beta^{\prime}} is a consequence of \mathcal{R}_{r+1,r+2} . Proof. The proof for Lemma 7.1 also works here, with the only difference being the definition of \beta_{1}^{\prime} , which is now a partial map. Here, under the same definition of b_{r}^{\prime} and b_{r+1}^{\prime} , the rest of the proof is identical to that of Lemma 7.1 . ∎ Lemma 8.2 . If |B_{r+1}|\geq 2 , let b\in B_{r+1} . Let 1\leq i\leq r+1 . Define \beta^{\prime}=\small\begin{pmatrix}B_{1}&B_{2}&\dots&B_{i}\cup\{b\}&\dots&B_{r}&B_{r+1}\setminus\{b\}\\ b_{1}&b_{2}&\dots&b_{i}&\dots&b_{r}&b_{r+1}\end{pmatrix}. Then \alpha\beta=\alpha\beta^{\prime} , and the relation x_{\alpha}x_{\beta}=x_{\alpha}x_{\beta^{\prime}} is a consequence of \mathcal{R}_{r+1,r+2} . Proof. The proof is the same as that of Lemma 7.2 . When defining \beta_{1} and \beta_{1}^{\prime} , we let B be the complement of their domains. ∎ Lemma 8.3 . For 1\leq i\neq j\leq r+1 , if |B_{i}\setminus\image(\alpha)|\geq 1 , let b\in B_{i}\setminus\image(\alpha) , define \beta_{ij}^{\prime}=\small\begin{pmatrix}B_{1}&B_{2}&\dots&B_{i}\setminus\{b\}&\dots&B_{j}\cup\{b\}&\dots&B_{r}&B_{r+1}&B\\ b_{1}&b_{2}&\dots&b_{i}&\dots&b_{j}&\dots&b_{r}&b_{r+1}&-\end{pmatrix}. Then \alpha\beta=\alpha\beta_{ij}^{\prime} , and the relation x_{\alpha}x_{\beta}=x_{\alpha}x_{\beta_{ij}^{\prime}} is a consequence of \mathcal{R}_{r+1,r+2} . Proof. This follows from Lemma 8.2 . ∎ Lemma 8.4 . If |A_{r}|\geq 2 , let a\in A_{r} . Define \alpha^{\prime}=\small\begin{pmatrix}A_{1}&A_{2}&\dots&A_{r}\setminus\{a\}&A_{r+1}\cup\{a\}\\ a_{1}&a_{2}&\dots&a_{r}&a_{r+1}\end{pmatrix}. Then \alpha\beta=\alpha^{\prime}\beta , and the relation x_{\alpha}x_{\beta}=x_{\alpha^{\prime}}x_{\beta} is a consequence of \mathcal{R}_{r+1,r+2} . Proof. Similar to the proof strategy of the above lemmas, the proof for Lemma 7.4 can be applied to maps in \mathcal{PT}_{n} , with the consideration of the complements A and B of the domains in the definitions of \alpha_{1},\alpha_{2} and \beta_{1} . ∎ Lemma 8.5 . Let 1\leq i\leq r-1 . If |A_{i}|\geq 2 and |B_{i}|\geq 2 , let a_{i1},a_{i2}\in B_{i} , let A_{i1},A_{i2} partition A_{i} . Define \alpha^{\prime}=\small\begin{pmatrix}A_{1}&A_{2}&\dots&A_{i1}&A_{i2}&\dots&A_{r}\cup A_{r+1}\\ a_{1}&a_{2}&\dots&a_{i1}&a_{i2}&\dots&a_{r}\end{pmatrix}. Then \alpha\beta=\alpha^{\prime}\beta , and the relation x_{\alpha}x_{\beta}=x_{\alpha^{\prime}}x_{\beta} is a consequence of \mathcal{R}_{r+1,r+2} . Proof. The proof is the same as that of Lemma 7.5 , except that \alpha_{1} is defined to be a partial map and that A=[n]\setminus\dom(\alpha) . ∎ Lemma 8.6 . Let 1\leq i\leq r+1 . If |B_{i}\setminus(B_{i}\cap\image(\alpha))|\geq 1 , let a_{i}^{\prime}\in B_{i}\setminus\image(\alpha) . Define \alpha^{\prime}=\small\begin{pmatrix}A_{1}&A_{2}&\dots&A_{i}&\dots&A_{r}&A_{r+1}\\ a_{1}&a_{2}&\dots&a_{i}^{\prime}&\dots&a_{r}&a_{r+1}\end{pmatrix}. Then \alpha\beta=\alpha^{\prime}\beta , and the relation x_{\alpha}x_{\beta}=x_{\alpha^{\prime}}x_{\beta} is a consequence of \mathcal{R}_{r+1,r+2} . Proof. The proof is the same as that of Lemma 7.6 , except that \alpha_{1} is defined to be a partial map and that A=[n]\setminus\dom(\alpha) . ∎ Lemma 8.7 . Let \alpha,\beta,\gamma,\delta\in J_{r+1} such that \alpha\beta=\gamma\delta\in J_{r} are of Case 1. Then x_{\alpha}x_{\beta}=x_{\gamma}x_{\delta} is a consequence of \mathcal{R}_{r+1,r+2} . Proof. To prove the lemma, it suffices to follow the proof for Lemma 7.7 on applying Lemmas 8.1 to 8.6 . ∎ Next, we look at words that are obtained as in Case 2. Lemma 8.8 . Suppose that |A_{r+1}|\geq 2 . Let a^{\prime}\in A_{r+1} . Define \alpha^{\prime}=\small\begin{pmatrix}A_{1}&A_{2}&\dots&A_{r}&A_{r+1}\setminus\{a\}\\ a_{1}&a_{2}&\dots&a_{r}&a_{r+1}\end{pmatrix}. Then \alpha\beta=\alpha^{\prime}\beta , and the relation x_{\alpha}x_{\beta}=x_{\alpha^{\prime}}x_{\beta} is a consequence of \mathcal{R}_{r+1,r+2} . Proof. Let a\in[n]\setminus\image(\alpha),a^{\prime\prime}\in B_{r+1} . Define \displaystyle\alpha_{1} \displaystyle=\small\begin{pmatrix}A_{1}&\dots&A_{r}&A_{r+1}\setminus\{a\}&a\\ a_{1}&\dots&a_{r}&a_{r+1}&a^{\prime}\end{pmatrix},\ \alpha_{2}=\small\begin{pmatrix}a_{1}&\dots&a_{r}&\{a_{r+1},a^{\prime}\}&a^{\prime\prime}\\ a_{1}&\dots&a_{r}&a_{r+1}&a^{\prime\prime}\end{pmatrix}, \displaystyle\alpha_{2}^{\prime} \displaystyle=\small\begin{pmatrix}a_{1}&\dots&a_{r}&a_{r+1}&a^{\prime\prime}\\ a_{1}&\dots&a_{r}&a_{r+1}&a^{\prime\prime}\end{pmatrix}. Then \alpha_{1}\alpha_{2}=\alpha , \alpha_{1}\alpha_{2}^{\prime}=\alpha^{\prime} , and \alpha_{2}\beta=\alpha_{2}^{\prime}\beta=\small\begin{pmatrix}a_{1}&\dots&a_{r}&a^{\prime\prime}\\ b_{1}&\dots&b_{r}&b_{r+1}\end{pmatrix}\in J_{r+1}. Hence \displaystyle\begin{aligned} x_{\alpha}x_{\beta}&=x_{\alpha_{1}}x_{\alpha_{2}}x_{\beta}\ \ &&(x_{\alpha}=x_{\alpha_{1}}x_{\alpha_{2}})\\ &=x_{\alpha_{1}}x_{\alpha_{2}^{\prime}}x_{\beta}\ \ &&(x_{\alpha_{2}}x_{\beta}=x_{\alpha_{2}^{\prime}}x_{\beta})\\ &=x_{\alpha^{\prime}}x_{\beta}\ \ &&(x_{\alpha^{\prime}}=x_{\alpha_{1}}x_{\alpha_{2}^{\prime}}).\end{aligned} ∎ Lemma 8.9 . Suppose that |B|\geq 2 . Let a_{r+1}^{\prime}\in B\setminus\{a_{r+1}\} . Define \alpha^{\prime}=\small\begin{pmatrix}A_{1}&A_{2}&\dots&A_{r}&A_{r+1}\\ a_{1}&a_{2}&\dots&a_{r}&a_{r+1}^{\prime}\end{pmatrix}. Let 1\leq i\leq r . Suppose that |B_{i}|\geq 2 , let a_{i}^{\prime}\in B_{i}\setminus\{a_{i}\} . Define \alpha^{\prime\prime}=\small\begin{pmatrix}A_{1}&\dots&A_{i}&\dots&A_{r}&A_{r+1}\\ a_{1}&\dots&a_{i}^{\prime}&\dots&a_{r}&a_{r+1}\end{pmatrix}. Then \alpha\beta=\alpha^{\prime}\beta , \alpha\beta=\alpha^{\prime\prime}\beta , and the relation x_{\alpha}x_{\beta}=x_{\alpha^{\prime}}x_{\beta},x_{\alpha}x_{\beta}=x_{\alpha^{\prime\prime}}x_{\beta} are consequences of \mathcal{R}_{r+1,r+2} . Proof. Let b\in[n]\setminus\image(\beta) . Define \displaystyle\beta_{1} \displaystyle=\small\begin{pmatrix}B_{1}&\dots&B_{r+1}&\{a_{r+1},a_{r+1}^{\prime}\}\\ b_{1}&\dots&b_{r+1}&b\end{pmatrix},\ \beta_{2}=\small\begin{pmatrix}b_{1}&\dots&b_{r+1}\\ b_{1}&\dots&b_{r+1}\end{pmatrix}. Then \beta_{1}\beta_{2}=\beta,\alpha\beta_{1}=\alpha^{\prime}\beta\in J_{r+1} . We have \displaystyle\begin{aligned} x_{\alpha}x_{\beta}&=x_{\alpha}x_{\beta_{1}}x_{\beta_{2}}\ \ &&(x_{\beta}=x_{\beta_{1}}x_{\beta_{2}})\\ &=x_{\alpha^{\prime}}x_{\beta_{1}}x_{\beta_{2}}\ \ &&(x_{\alpha}x_{\beta_{1}}=x_{\alpha^{\prime}}x_{\beta_{1}})\\ &=x_{\alpha^{\prime}}x_{\beta}\ \ &&(x_{\beta_{1}}x_{\beta_{2}}=x_{\beta}).\end{aligned} For the second part, it suffices to prove the lemma when i=1 . Let a_{1}^{\prime}\in B_{1}\setminus\{a_{1}\} . Define \displaystyle\alpha_{1} \displaystyle=\small\begin{pmatrix}a_{1}&a_{2}&\dots&a_{r+1}&a\\ a_{1}&a_{2}&\dots&a_{r+1}&a\end{pmatrix},\ \alpha_{1}^{\prime}=\small\begin{pmatrix}a_{1}&a_{2}&\dots&a_{r+1}&a\\ a_{1}^{\prime}&a_{2}&\dots&a_{r+1}&a\end{pmatrix}. Then \alpha\alpha_{1}=\alpha,\alpha\alpha_{1}^{\prime}=\alpha^{\prime\prime} , and \alpha_{1}\beta=\alpha_{1}^{\prime}\beta\in J_{r+1} . Hence \displaystyle\begin{aligned} x_{\alpha}x_{\beta}&=x_{\alpha}x_{\alpha_{1}}x_{\beta}\ \ &&(x_{\alpha}=x_{\alpha}x_{\alpha_{1}})\\ &=x_{\alpha}x_{\alpha_{1}^{\prime}}x_{\beta}\ \ &&(x_{\alpha_{1}}x_{\beta}=x_{\alpha_{1}^{\prime}}x_{\beta})\\ &=x_{\alpha^{\prime\prime}}x_{\beta}\ \ &&(x_{\alpha}x_{\alpha_{1}^{\prime}}=x_{\alpha^{\prime\prime}}).\end{aligned} ∎ Lemma 8.10 . Suppose that |B|\geq 2 . Let b\in B\setminus\{a_{r+1}\} . For 1\leq i\leq r+1 , define \beta^{\prime}=\small\begin{pmatrix}B_{1}&B_{2}&\dots&B_{i}\cup\{b\}&\dots&B_{r}&B_{r+1}\\ b_{1}&b_{2}&\dots&b_{i}&\dots&b_{r}&b_{r+1}\end{pmatrix}. Then \alpha\beta=\alpha\beta^{\prime} , and the relation x_{\alpha}x_{\beta}=x_{\alpha}x_{\beta^{\prime}} is a consequence of \mathcal{R}_{r+1,r+2} . Proof. Without loss of generality, let i=1 . Let a\in B_{r+1} . Define \displaystyle\begin{aligned} \beta_{1}&=\small\begin{pmatrix}B_{1}&\dots&B_{r}&B_{r+1}&b\\ a_{1}&\dots&a_{r}&a&a_{r+1}\end{pmatrix},\ \beta_{1}^{\prime}=\small\begin{pmatrix}B_{1}&\dots&B_{r}&B_{r+1}&b\\ a_{1}&\dots&a_{r}&a&b\end{pmatrix},\\ \beta_{2}&=\small\begin{pmatrix}\{a_{1},b\}&a_{2}&\dots&a_{r+1}\\ b_{1}&b_{2}&\dots&b_{r+1}\end{pmatrix},\ \alpha_{1}=\small\begin{pmatrix}a_{1}&\dots&a_{r+1}&a\\ a_{1}&\dots&a_{r+1}&a\end{pmatrix}.\end{aligned} Then \beta_{1}\beta_{2}=\beta,\beta_{1}^{\prime}\beta_{2}=\beta^{\prime} , \alpha\alpha_{1}=\alpha , and \alpha_{1}\beta_{1}=\alpha_{1}\beta_{1}^{\prime}\in J_{r+1} . Then \displaystyle\begin{aligned} x_{\alpha}x_{\beta}&=x_{\alpha}x_{\alpha_{1}}x_{\beta_{1}}x_{\beta_{2}}\ \ &&(x_{\alpha}=x_{\alpha}x_{\alpha_{1}},x_{\beta}=x_{\beta_{1}}x_{\beta_{2}})\\ &=x_{\alpha}x_{\alpha_{1}}x_{\beta_{1}^{\prime}}x_{\beta_{2}}\ \ &&(x_{\alpha_{1}}x_{\beta_{1}}=x_{\alpha_{1}}x_{\beta_{1}^{\prime}})\\ &=x_{\alpha}x_{\beta^{\prime}}\ \ &&(x_{\beta_{1}^{\prime}}x_{\beta_{2}}=x_{\beta^{\prime}}).\end{aligned} ∎ Lemma 8.11 . Let b_{r+1}^{\prime}\in[n]\setminus\image(\beta) . Define \beta^{\prime}=\small\begin{pmatrix}B_{1}&B_{2}&\dots&B_{r}&B_{r+1}&B\\ b_{1}&b_{2}&\dots&b_{r}&b_{r+1}^{\prime}&-\end{pmatrix}. Then \alpha\beta=\alpha\beta^{\prime} , and the relation x_{\alpha}x_{\beta}=x_{\alpha}x_{\beta^{\prime}} is a consequence of \mathcal{R}_{r+1,r+2} . Proof. Let b\in[n]\setminus(\image(\beta)\cup\image(\beta^{\prime})) . Define \displaystyle\alpha_{1} \displaystyle=\small\begin{pmatrix}a_{1}&\dots&a_{r+1}\\ a_{1}&\dots&a_{r+1}\end{pmatrix},\ \beta_{1}=\small\begin{pmatrix}B_{1}&\dots&B_{r+1}&B\\ b_{1}&\dots&b_{r+1}&b\end{pmatrix}, \displaystyle\beta_{1}^{\prime} \displaystyle=\small\begin{pmatrix}B_{1}&\dots&B_{r+1}&B\\ b_{1}&\dots&b_{r+1}^{\prime}&b\end{pmatrix},\ \beta_{2}=\small\begin{pmatrix}b_{1}&\dots&b_{r+1}&b_{r+1}^{\prime}\\ b_{1}&\dots&b_{r+1}&b_{r+1}^{\prime}\end{pmatrix}. Then \displaystyle\begin{aligned} x_{\alpha}x_{\beta}&=x_{\alpha}x_{\alpha_{1}}x_{\beta_{1}}x_{\beta_{2}}\ \ &&(x_{\alpha}=x_{\alpha}x_{\alpha_{1}})\\ &=x_{\alpha}x_{\alpha_{1}}x_{\beta_{1}^{\prime}}x_{\beta_{2}}\ \ &&(x_{\alpha_{1}}x_{\beta_{1}}=x_{\alpha_{1}}x_{\beta_{1}^{\prime}})\\ &=x_{\alpha}x_{\beta^{\prime}}\ \ &&(x_{\beta_{1}^{\prime}}x_{\beta_{2}}=x_{\beta^{\prime}}).\end{aligned} ∎ Lemma 8.12 . Let \alpha,\beta be as defined above, and suppose that \alpha^{\prime} , \beta^{\prime} are obtained from \alpha,\beta using one of the following rules: (i) If |A_{r+1}|\geq 2 , and a\in A_{r+1} , let \alpha^{\prime} be obtained from \alpha by changing the kernel class A_{r+1} by moving a to A , and let \beta^{\prime}=\beta . (ii) If |B|\geq 2 , and a_{r+1}^{\prime}\in B\setminus\{a_{r+1}\} , let \alpha^{\prime} be obtained from \alpha by changing the image of A_{r+1} from a_{r+1} to a_{r+1}^{\prime} , and let \beta^{\prime}=\beta . (iii) For 1\leq i\leq r , if |B_{i}|\geq 2 , and a_{i}^{\prime}\in B\setminus\{a_{i}\} , let \alpha^{\prime} be obtained from \alpha by changing the image of A_{i} from a_{i} to a_{i}^{\prime} , and let \beta^{\prime}=\beta . (iv) For 1\leq i\leq r , if |B|\geq 2 , and b\in B\setminus\{a_{r+1}\} , let \beta^{\prime} be obtained from \beta by changing the kernel by moving b from B to B_{i} , and let \alpha^{\prime}=\alpha . (v) If b_{r+1}^{\prime}\in[n]\setminus\image(\beta) , let \beta^{\prime} be obtained from \beta by changing the image of B_{r+1} from b_{r+1} to b_{r+1}^{\prime} , and let \alpha^{\prime}=\alpha . Then the word x_{\alpha^{\prime}}x_{\beta^{\prime}} can be obtained from x_{\alpha}x_{\beta} using \mathcal{R}_{r+1,r+2} . Proof. This follows from Lemmas 8.8 - 8.11 . ∎ Using Lemma 8.12 , we aim to show that given a word u of length 2 as in Case 2, we can obtain any other word v which represents the same partial map, if v is also of Case 2. Lemma 8.13 . Let \alpha,\beta,\gamma,\delta\in J_{r+1} such that \alpha\beta=\gamma\delta\in J_{r} are of type 2 . Then x_{\alpha}x_{\beta}=x_{\gamma}x_{\delta} is a consequence of \mathcal{R}_{r+1,r+2} . Proof. Suppose that \alpha\beta=\gamma\delta=\small\begin{pmatrix}A_{1}&\dots&A_{r}&X\\ b_{1}&\dots&b_{r}&-\end{pmatrix}. Without loss of generality, \displaystyle\alpha \displaystyle=\small\begin{pmatrix}A_{1}&\dots&A_{r}&X_{1}&X_{1}^{\prime}\\ a_{1}&\dots&a_{r}&a_{r+1}&-\end{pmatrix},\ \beta=\small\begin{pmatrix}B_{1}&\dots&B_{r}&B_{r+1}&B\\ b_{1}&\dots&b_{r}&b_{r+1}&-\end{pmatrix}, \displaystyle\gamma \displaystyle=\small\begin{pmatrix}A_{1}&\dots&A_{r}&X_{2}&X_{2}^{\prime}\\ c_{1}&\dots&c_{r}&c_{r+1}&-\end{pmatrix},\ \delta=\small\begin{pmatrix}D_{1}&\dots&D_{r}&D_{r+1}&D\\ b_{1}&\dots&b_{r}&d_{r+1}&-\end{pmatrix}, where a_{i}\in B_{i} and c_{i}\in D_{i} for 1\leq i\leq r , a_{r+1}\in B and c_{r+1}\in D . We will show that we can obtain x_{\alpha}x_{\beta} from x_{\gamma}x_{\delta} using rules in Lemma 8.12 . We first show that we can obtain a word of the form x_{\alpha}x_{\delta^{\prime}} from x_{\gamma}x_{\delta} . Let i=1 . Step 1 : If a_{i}\in D_{i} , go to Step 2. Otherwise, a_{i}\in D_{j} . If |D_{j}|>1 , change \ker(\delta) by moving a_{i} from D_{j} to D_{i} (iv) . If |D_{j}|=1 , first move some element c^{\prime}\in[n]\setminus(\image(\gamma)\cup\{a_{i}\}) from another \ker(\delta) -class to D_{j} (iv) , then change \gamma by changing the image of C_{j} from a_{i} to c^{\prime} (iii) , and change the kernel of \delta by moving a_{i} to D_{i} (iv) . Step 2 : Change \gamma by changing the image of A_{i} from c_{i} to a_{i} (iii) . Step 3 : If i=r , proceed. Otherwise let i=i+1 , and return to Step 1. Step 4 : If a_{r+1}\in D , change \image(\gamma) by changing the image of X_{2} from c_{r+1} to a_{r+1} (ii) . Otherwise, if a_{r+1}\notin D , move elements between D and \ker(\delta) -classes until a_{r+1} is moved to D (iv) , then change \image(\gamma) as in the previous situation (ii) . Step 5 : Change \delta by moving elements between X_{2} and X_{2}^{\prime} until we have X_{1}=X_{2} and X_{1}^{\prime}=X_{2}^{\prime} (i) . So far we have obtained x_{\alpha}x_{\delta^{\prime}} from x_{\gamma}x_{\delta} . Step 6 : Change \image(\delta^{\prime}) by replacing the image of X_{1} from d_{r+1} by b_{r+1} (v) . Step 7 : Change \delta^{\prime} by moving elements between the kernel classes, until we obtain \beta (iv) . ∎ Then, we show that relations that equates words of Case 1 and Case 2 can be deduced from \mathcal{R}_{r+1,r+2} . Lemma 8.14 . Suppose that \alpha,\beta\in J_{r+1} such that \alpha\beta\in J_{r} and is type 2. Suppose that |B_{r}|\geq 2 . Let a_{r1},a_{r2}\in B_{r} , let A_{r1},A_{r2} partition A_{r} . Define \alpha^{\prime}=\small\begin{pmatrix}A_{1}&A_{2}&\dots&A_{r-1}&A_{r1}&A_{r2}\\ a_{1}&a_{2}&\dots&a_{r-1}&a_{r1}&a_{r2}\end{pmatrix}. Then \alpha\beta=\alpha^{\prime}\beta , and the relation x_{\alpha}x_{\beta}=x_{\alpha^{\prime}}x_{\beta} is a consequence of \mathcal{R}_{r+1,r+2} . Proof. Let b\in B_{r+1} . Define \displaystyle\alpha_{1} \displaystyle=\small\begin{pmatrix}A_{1}&\dots&A_{r1}&A_{r2}&A_{r+1}\\ a_{1}&\dots&a_{r1}&a_{r2}&a_{r+1}\end{pmatrix},\ \alpha_{2}=\small\begin{pmatrix}a_{1}&\dots&a_{r-1}&\{a_{r1},a_{r2}\}&a_{r+1}&a_{r}\\ a_{1}&\dots&a_{r-1}&a_{r}&a_{r+1}&b\end{pmatrix}, \displaystyle\alpha_{2}^{\prime} \displaystyle=\small\begin{pmatrix}a_{1}&\dots&a_{r-1}&a_{r1}&a_{r2}&a_{r}\\ a_{1}&\dots&a_{r-1}&a_{r1}&a_{r2}&b\end{pmatrix}. Then \alpha_{1}\alpha_{2}=\alpha,\alpha_{1}\alpha_{2}^{\prime}=\alpha^{\prime} , and \alpha_{2}\beta=\alpha_{2}^{\prime}\beta=\small\begin{pmatrix}a_{1}&\dots&a_{r-1}&\{a_{r1},a_{r2}\}&a_{r}\\ b_{1}&\dots&b_{r-1}&b_{r}&b_{r+1}\end{pmatrix}\in J_{r+1}. Hence \displaystyle\begin{aligned} x_{\alpha}x_{\beta}&=x_{\alpha_{1}}x_{\alpha_{2}}x_{\beta}\ \ &&(x_{\alpha}=x_{\alpha_{1}}x_{\alpha_{2}})\\ &=x_{\alpha_{1}}x_{\alpha_{2}^{\prime}}x_{\beta}\ \ &&(x_{\alpha_{2}}x_{\beta}=x_{\alpha_{2}^{\prime}}x_{\beta})\\ &=x_{\alpha^{\prime}}x_{\beta}\ \ &&(x_{\alpha_{1}}x_{\alpha_{2}^{\prime}}=x_{\alpha^{\prime}}).\end{aligned} ∎ Lemma 8.15 . Let \alpha,\beta,\gamma,\delta\in J_{r+1} such that \alpha\beta=\gamma\delta\in J_{r} . Then x_{\alpha}x_{\beta}=x_{\gamma}x_{\delta} is a consequence of \mathcal{R}_{r+1,r+2} . Proof. If \alpha\beta and \gamma\delta are both of Case 1 or Case 2, the result follows from Lemma 8.7 or Lemma 8.13 . Otherwise, \alpha\beta and \gamma\delta do not have the same type. Without loss of generality, assume that \alpha\beta is as in Case 2. Then by Lemma 8.14 , we can obtain some x_{\alpha^{\prime}}x_{\beta} from x_{\alpha}x_{\beta} such that \alpha^{\prime}\beta is Case 1. Finally, apply the result of Lemma 8.7 to x_{\alpha^{\prime}}x_{\beta} . ∎ Lemma 8.16 . Let 0\leq r\leq 2m-n-1 . If \alpha,\beta,\gamma\in J_{r+1},\alpha\beta,\beta\gamma,\alpha\beta\gamma\in J_{r} , then there is a relation of the form x_{\alpha}x_{\beta}x_{\gamma}=x_{\alpha^{\prime}}x_{\gamma} where \alpha^{\prime} is some map in J_{r+1} , is a consequence of \mathcal{R}_{r+1,r+2} . Proof. Let \alpha=\small\begin{pmatrix}A_{1}&\dots&A_{r+1}\\ a_{1}&\dots&a_{r+1}\end{pmatrix},\beta=\small\begin{pmatrix}B_{1}&\dots&B_{r+1}\\ b_{1}&\dots&b_{r+1}\end{pmatrix},\gamma=\small\begin{pmatrix}C_{1}&\dots&C_{r+1}\\ c_{1}&\dots&c_{r+1}\end{pmatrix}. Since \alpha\beta\gamma,\alpha\beta,\beta\gamma\in J_{r} , the elements in \image(\alpha\beta) are in r of \ker(\gamma) -classes, and \image(\alpha) are in r of \ker(\beta\gamma) -classes. Therefore, for 1\leq i\leq r+1 , if b_{i}\in\image(\alpha\beta) , then b_{i}\in\dom(\gamma) . Moreover, b_{i}\gamma\neq b_{j}\gamma if b_{i},b_{j}\in\image(\alpha\beta) for i\neq j . Without loss of generality, we may assume that either \alpha\beta=\small\begin{pmatrix}A_{1}&\dots&A_{r}\\ b_{1}&\dots&b_{r}\end{pmatrix},\text{\ or\ }\alpha\beta=\small\begin{pmatrix}A_{1}&\dots&A_{r-1}&A_{r}\cup A_{r+1}\\ b_{1}&\dots&b_{r-1}&b_{r}\end{pmatrix}. Similarly, we have that \beta\gamma=\small\begin{pmatrix}B_{1}&\dots&B_{r}\\ c_{1}&\dots&c_{r}\end{pmatrix},\text{\ or\ }\beta\gamma=\small\begin{pmatrix}B_{1}&\dots&B_{r-1}&B_{r}\cup B_{r+1}\\ c_{1}&\dots&c_{r-1}&c_{r}\end{pmatrix}. Define \alpha^{\prime}=\small\begin{pmatrix}A_{1}&\dots&A_{r}&A_{r+1}\\ b_{1}&\dots&b_{r}&b_{r+1}\end{pmatrix},\ \beta^{\prime}=\small\begin{pmatrix}B_{1}&\dots&B_{r}&B_{r+1}\\ b_{1}&\dots&b_{r}&b_{r+1}^{\prime}\end{pmatrix}, where b_{r+1}^{\prime}\in C_{r+1} , and we consider every combination of \alpha\beta and \beta\gamma . In fact, different combinations lead to the same proof. In the following we consider one possible combination, where \alpha\beta=\small\begin{pmatrix}A_{1}&\dots&A_{r}\\ b_{1}&\dots&b_{r}\end{pmatrix},\text{\ and\ }\beta\gamma=\small\begin{pmatrix}B_{1}&\dots&B_{r}\\ c_{1}&\dots&c_{r}\end{pmatrix}, and the proofs for the other three are identical. We have that \alpha\beta\gamma=\small\begin{pmatrix}A_{1}&\dots&A_{r}\\ c_{1}&\dots&c_{r}\end{pmatrix} . Then \beta^{\prime}\gamma\in J_{r+1} , and \alpha\beta=\alpha\beta^{\prime},\alpha^{\prime}\gamma=\alpha(\beta^{\prime}\gamma) . We can obtain x_{\alpha^{\prime}}x_{\gamma} from x_{\alpha}x_{\beta}x_{\gamma} via the following, \displaystyle\begin{aligned} x_{\alpha}x_{\beta}x_{\gamma}&=x_{\alpha}x_{\beta^{\prime}}x_{\gamma}\ \ &&(x_{\alpha}x_{\beta}=x_{\alpha}x_{\beta^{\prime}})\\ &=x_{\alpha}x_{\beta^{\prime}\gamma}\ \ &&(\beta^{\prime},\gamma,\beta^{\prime}\gamma\in J_{r+1})\\ &=x_{\alpha^{\prime}}x_{\gamma}\ \ &&(x_{\alpha}x_{\beta^{\prime}\gamma}=x_{\alpha^{\prime}}x_{\gamma}).\end{aligned} ∎ Lemma 8.17 . Let 0\leq r\leq 2m-n-1 . If \gamma\delta\in J_{r} where \rank(\gamma),\rank(\delta)\geq r+1 , there exist \alpha,\beta\in J_{r+1} such that \alpha\beta=\gamma\delta , and x_{\alpha}x_{\beta}=x_{\gamma}x_{\delta} is a consequence of \mathcal{R}_{r+1,m} . Proof. Consider \gamma=\small\begin{pmatrix}C_{1}&\dots&C_{i}\\ c_{1}&\dots&c_{i}\end{pmatrix}\in J_{i},\ \delta=\small\begin{pmatrix}D_{1}&\dots&D_{j}\\ d_{1}&\dots&d_{j}\end{pmatrix}\in J_{j}, and let D denote [n]\setminus\dom(\delta) . Since \gamma\delta\in J_{r} , there are at least r , say s where s\geq r , elements in \image(\gamma) that are in r \ker(\delta) -classes, say D_{1},\dots,D_{r} , and the rest of \image(\gamma) is in D . Let c\in D_{r+1} . Relabel the \ker(\gamma) -classes and their images as the following, \gamma=\small\begin{pmatrix}C_{11}&\dots&C_{1k_{1}}&\dots&C_{r1}&\dots&C_{rk_{r}}&C_{(r+1)1}&\dots&C_{(r+1)(i-s)}\cr c_{11}&\dots&c_{1k_{1}}&\dots&c_{r1}&\dots&c_{rk_{r}}&c_{(r+1)1}&\dots&c_{(r+1)(i-s)}\end{pmatrix}, where k_{l}=|D_{l}\cap\image(\gamma)| , \{c_{l1},\dots,c_{lk_{l}}\}\subseteq D_{l} for 1\leq l\leq r , and c_{(r+1)1},\dots,c_{(r+1)(i-s)}\in D . Notice that with the assumption r\leq 2m-n-1 , there does not exist \gamma,\delta\in J_{m} such that \gamma\delta\in J_{r} , therefore in the following, we exclude the situation when i=j=m . Case 1 : r+1\leq i\leq j\leq m . Let d\in D . Define \gamma_{1}=\small\begin{pmatrix}c_{11}&\dots&c_{1k_{1}}&\dots&c_{(r+1)1}&\dots&c_{(r+1)(i-s)}&[n]\setminus\image(\gamma)\\ c_{11}&\dots&c_{1k_{1}}&\dots&c_{(r+1)1}&\dots&c_{(r+1)(i-s)}&c\end{pmatrix}\in J_{i+1}, notice that the preimage of c is non-empty as ir+1 , there is a \ker(\delta) -class D_{l} , or D , that contains more than 1 elements of \image(\gamma) . If k_{l}\geq 2 for some 1\leq l\leq r , let c_{l1},c_{l2}\in D_{l} . It suffices to consider l=r , as the proof for the other possibilities should be similar. For r+1\leq k\leq j , let d_{k}^{\prime}\in D_{k} . Define \delta_{1}=\small\begin{pmatrix}D_{1}&\dots&D_{r-1}&c_{r1}&D_{r}\setminus\{c_{r1}\}&D_{r+1}&\dots&D_{j}\\ c_{11}&\dots&c_{(r-1)1}&c_{r1}&c_{r2}&d_{r+1}^{\prime}&\dots&d_{j}^{\prime}\end{pmatrix}\in J_{j+1}, and \gamma_{1}=\small\begin{pmatrix}\cup^{k_{1}}_{i=1}C_{1i}&\dots&\cup^{k_{r-1}}_{i=1}C_{(r-1)i}&C_{r1}&\cup^{k_{r}}_{i=2}C_{ri}\\ c_{11}&\dots&c_{(r-1)1}&c_{r1}&c_{r2}\end{pmatrix}\in J_{r+1}. Otherwise, k_{l}=1 for all 1\leq l\leq r , i.e. each of D_{1},\dots,D_{r} contains exactly one element of \image(\gamma) , and the rest (i-r) elements of \image(\gamma) are in D . Then \gamma=\small\begin{pmatrix}C_{11}&\dots&C_{r1}&C_{(r+1)1}&\dots&C_{(r+1)(i-r)}\cr c_{11}&\dots&c_{r1}&c_{(r+1)1}&\dots&c_{(r+1)(i-r)}\end{pmatrix}. Let d\in D . Define \delta_{1}=\small\begin{pmatrix}D_{1}&\dots&D_{r}&D_{r+1}&\dots&D_{j}&c_{(r+1)1}\\ c_{11}&\dots&c_{r1}&d_{r+1}^{\prime}&\dots&d_{j}^{\prime}&d\end{pmatrix}\in J_{j+1}, and \gamma_{1}=\small\begin{pmatrix}C_{11}&\dots&C_{r1}&C_{(r+1)1}\\ c_{11}&\dots&c_{r1}&d\end{pmatrix}\in J_{r+1}. In both situations, \delta_{1}\delta=\delta , \gamma\delta_{1}=\gamma_{1} , and \gamma_{1}\in J_{r+1},\ \delta_{1}\in J_{j+1} . Hence x_{\gamma}x_{\delta}=x_{\gamma}x_{\delta_{1}}x_{\delta}=x_{\gamma_{1}}x_{\delta} is a consequence of \mathcal{R}_{r+1,m} . Now if \gamma\in D_{i} and \delta\in D_{j} such that r+1\leq i\leq j\leq m , apply the method in Case 1 to x_{\gamma}x_{\delta} and obtain a word u . If u contains a letter that represents a map of rank greater than s , apply Case 2 to u . The resulting word is made up of two letters that represent maps of rank r+1 . Otherwise, if \gamma\in D_{i} and \delta\in D_{j} such that r+1\leq jm>\frac{n}{2} , then \depth(I_{m})\leq n-m+1 . Proof. We have proved in Lemma 8.15 - 8.17 that when m>\frac{n}{2} , \ref{P1}-\ref{P3} hold. It follows from Theorem 5.3 that \depth(I_{m})\leq m-(2m-n)+1=n-m+1 . ∎ Theorem 8.19 . Let I_{m}<\mathcal{PT}_{n} . Then \depth(I_{m})=\begin{cases}3&m=n\\ n-m+1&m>\frac{n}{2}\\ m+1&m\leq\frac{n}{2}\end{cases} . Proof. When m\leq\frac{n}{2} , the exact value for \depth(I_{m}) is given in Corollary 4.5 . When n>m>\frac{n}{2} , the lower bound for \depth(I_{m}) is found in Proposition 4.1 , which is shown to be an upper bound in Proposition 8.18 . Finally, we know that \depth(\mathcal{PT}_{n})\leq 3 , as \depth(I_{n-1})=2 . Consider the partial bijections \alpha,\beta defined in the proof for Theorem 6.11 . Since \alpha,\beta are also elements of \mathcal{PT}_{n} , and that they satisfy the conditions in Proposition 4.3 , as a result we cannot obtain x_{\alpha}{x_{\beta}}^{2} from {x_{\beta}}^{2} using relations from \mathcal{R}_{n-1,n} . Hence \mathcal{C}_{n-1}=\langle X_{n-1,n}\ |\ \mathcal{R}_{n-1,n}\rangle does not define a presentation for \mathcal{PT}_{n} , and \depth(\mathcal{PT}_{n})>2 , which gives \depth(\mathcal{PT}_{n})=3 . ∎ 9. Conclusion Most work in proving our Main Theorem was to show that the lower bounds for the depth of an ideal of \mathcal{T}_{n},\mathcal{I}_{n},\mathcal{PT}_{n} are also upper bounds. Now let us mention the relationship between the lower bounds and another interesting concept. Let S be a finite semigroup whose \mathcal{J} -classes form a chain, namely J_{\epsilon}<\dots\frac{n+1}{2} , and \depth(I_{m})=m-r+1 , where r=2m-n . Define the Rees quotient semigroup I_{m}^{\prime}=I_{m}\setminus I_{r-1} . Notice that the \mathcal{J} -classes of I_{m}^{\prime} are \{0\}