2014/04/08 by James E. East, Robert M. Gray, East, James +1 · 3 citations
Computer Science · Mathematics · #Coding theory and cryptography #semigroups and automata theory #Algebraic structures and combinatorial models
paper · pdf · doi:10.48550/arxiv.1404.2359
We study the ideals of the partition, Brauer, and Jones monoid, establishing\nvarious combinatorial results on generating sets and idempotent generating sets\nvia an analysis of their Graham--Houghton graphs. We show that each proper\nideal of the partition monoid Pn is an idempotent generated semigroup, and\nobtain a formula for the minimal number of elements (and the minimal number of\nidempotent elements) needed to generate these semigroups. In particular, we\nshow that these two numbers, which are called the rank and idempotent rank\n(respectively) of the semigroup, are equal to each other, and we characterize\nthe generating sets of this minimal cardinality. We also characterize and\nenumerate the minimal idempotent generating sets for the largest proper ideal\nof Pn, which coincides with the singular part of Pn. Analogous results are\nproved for the ideals of the Brauer and Jones monoids; in each case, the rank\nand idempotent rank turn out to be equal, and all the minimal generating sets\nare described. We also show how the rank and idempotent rank results obtained,\nwhen applied to the corresponding twisted semigroup algebras (the partition,\nBrauer, and Temperley--Lieb algebras), allow one to recover formulae for the\ndimensions of their cell modules (viewed as cellular algebras) which, in the\nsemisimple case, are formulae for the dimensions of the irreducible\nrepresentations of the algebras. As well as being of algebraic interest, our\nresults relate to several well-studied topics in graph theory including the\nproblem of counting perfect matchings (which relates to the problem of\ncomputing permanents of 0,1-matrices and the theory of Pfaffian\norientations), and the problem of finding factorizations of Johnson graphs. Our\nresults also bring together several well-known number sequences such as\nStirling, Bell, Catalan and Fibonacci numbers.\n