Diagram monoids and Graham-Houghton graphs: idempotents and generating sets of ideals

DOI10.1016/J.JCTA.2016.09.001zbMATH Open1351.05227arXiv1404.2359OpenAlexW2962781288MaRDI QIDQ346439FDOQ346439

Authors: James East, R. Gray 

Publication date: 29 November 2016

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: We study the ideals of the partition, Brauer, and Jones monoid, establishing various combinatorial results on generating sets and idempotent generating sets via an analysis of their Graham--Houghton graphs. We show that each proper ideal of the partition monoid P_n is an idempotent generated semigroup, and obtain a formula for the minimal number of elements (and the minimal number of idempotent elements) needed to generate these semigroups. In particular, we show that these two numbers, which are called the rank and idempotent rank (respectively) of the semigroup, are equal to each other, and we characterize the generating sets of this minimal cardinality. We also characterize and enumerate the minimal idempotent generating sets for the largest proper ideal of P_n, which coincides with the singular part of P_n. Analogous results are proved for the ideals of the Brauer and Jones monoids; in each case, the rank and idempotent rank turn out to be equal, and all the minimal generating sets are described. We also show how the rank and idempotent rank results obtained, when applied to the corresponding twisted semigroup algebras (the partition, Brauer, and Temperley--Lieb algebras), allow one to recover formulae for the dimensions of their cell modules (viewed as cellular algebras) which, in the semisimple case, are formulae for the dimensions of the irreducible representations of the algebras. As well as being of algebraic interest, our results relate to several well-studied topics in graph theory including the problem of counting perfect matchings (which relates to the problem of computing permanents of {0,1}-matrices and the theory of Pfaffian orientations), and the problem of finding factorizations of Johnson graphs. Our results also bring together several well-known number sequences such as Stirling, Bell, Catalan and Fibonacci numbers.

Full work available at URL: https://arxiv.org/abs/1404.2359

Recommendations

• Enumeration of idempotents in diagram semigroups and algebras
• Motzkin monoids and partial Brauer monoids
• Twisted Brauer monoids
• Enumeration of idempotents in planar diagram monoids
• ON THE SINGULAR PART OF THE PARTITION MONOID

zbMATH Keywords

rankgenerating setsidempotentsdiagram algebraidempotent rankBrauer monoidGraham-Houghton graphJones monoidpartition monoid

Mathematics Subject Classification ID

Bell and Stirling numbers (11B73) Combinatorial aspects of representation theory (05E10) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Other combinatorial number theory (11B75)

Cites Work

• Title not available (Why is that?)
• A characterization of convertible (0,1)-matrices
• Permanents, Pfaffian orientations, and even directed circuits
• Title not available (Why is that?)
• A survey of Pfaffian orientations of graphs
• The Subsemigroup Generated By the Idempotents of a Full Transformation Semigroup
• On products of idempotent matrices
• Cellular algebras
• Structure of regular semigroups. I
• Title not available (Why is that?)
• Title not available (Why is that?)
• Relations between the ‘percolation’ and ‘colouring’ problem and other graph-theoretical problems associated with regular planar lattices: some exact results for the ‘percolation’ problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On presentations of Brauer-type monoids.
• Cellular algebras and inverse semigroups.
• On the representation theory of partial Brauer algebras
• Title not available (Why is that?)
• Representations of the rook-Brauer algebra
• Partition algebras.
• On the structure of Brauer's centralizer algebras
• Title not available (Why is that?)
• On the irreducible representations of a finite semigroup
• The \(\mathfrak q\)-theory of finite semigroups.
• On the ranks of certain semigroups of order-preserving transformations
• The representation theory of affine Temperley-Lieb algebras
• When is a cellular algebra quasi-hereditary?
• On inverses of products of idempotents in regular semigroups
• Title not available (Why is that?)
• Brauer algebras and centralizer algebras for \(\text{SO}(2n,\mathbb{C})\)
• Standard modules, induction and the structure of the Temperley-Lieb algebra
• A criterion on the semisimple Brauer algebras.
• Regular * semigroups
• Krohn-Rhodes complexity of Brauer type semigroups.
• Equational theories of semigroups with involution.
• Cell algebras.
• Almost cellular algebras
• The semigroup generated by the idempotents of a partition monoid.
• Idempotent rank in the endomorphism monoid of a nonuniform partition.
• Idempotent generation in the endomorphism monoid of a uniform partition
• ON THE SINGULAR PART OF THE PARTITION MONOID
• ENDOMORPHISMS OF , , AND
• ON THE PARTITION MONOID AND SOME RELATED SEMIGROUPS
• Pseudovarieties generated by Brauer type monoids.
• Motzkin monoids and partial Brauer monoids
• Variants of finite full transformation semigroups.
• Idempotent rank in finite full transformation semigroups
• Presentation of the singular part of the Brauer monoid
• On the ranks of certain finite semigroups of transformations
• Products of idempotent endomorphisms of an independence algebra of finite rank
• Idempotent generators in finite full transformation semigroups
• Title not available (Why is that?)
• Products of idempotent endomorphisms of an independence algebra of infinite rank
• TEMPERLEY-LIEB ALGEBRAS FOR NON-PLANAR STATISTICAL MECHANICS — THE PARTITION ALGEBRA CONSTRUCTION
• The minimal number of generators of a finite semigroup.
• Title not available (Why is that?)
• Enumeration of idempotents in diagram semigroups and algebras
• Partition monoids and embeddings in 2-generator regular \(*\)-semigroups.
• Idempotent rank in endomorphism monoids of finite independence algebras
• HALL'S CONDITION AND IDEMPOTENT RANK OF IDEALS OF ENDOMORPHISM MONOIDS
• Products of idempotents in algebraic monoids
• Ideal Structure of the Kauffman and Related Monoids
• Generating Sets of Completely 0-Simple Semigroups
• Generators and relations for partition monoids and algebras.
• The finite basis problem for Kauffman monoids.
• Cellularity of diagram algebras as twisted semigroup algebras.
• Cellularity of twisted semigroup algebras.
• Homogeneous factorisations of Johnson graphs
• Biordered sets come from semigroups
• Completely O-simple semigroups and their associated graphs and groups
• On central idempotents in the partition algebra
• The Temperley-Lieb algebra at roots of unity
• A tower construction for the radical in Brauer's centralizer algebras
• Counting techniques to label constant weight Gray codes with links to minimal generating sets of semigroups
• Congruences on *-regular semigroups
• Ramified partition algebras.
• On representations of affine Temperley-Lieb algebras. II
• Solvable RSOS models based on the dilute BWM algebra
• On maximal subgroups of free idempotent generated semigroups.
• The representation theory of the Temperley-Lieb algebras
• A quotient of the affine Hecke algebra in the Brauer algebra
• The structure of the partition algebras
• Generating sets of finite singular transformation semigroups.
• Defining relations for idempotent generators in finite full transformation semigroups.
• Free idempotent generated semigroups and endomorphism monoids of free \(G\)-acts.
• A seminormal form for partition algebras
• Subgroups of free idempotent generated semigroups need not be free.
• A note on maximal subgroups of free idempotent generated semigroups over bands.
• A criterion on the semisimple Brauer algebras. II.
• RSK insertion for set partitions and diagram algebras
• Representations of graph Temperley-Lieb algebras
• A characteristic free approach to Brauer algebras
• Free idempotent generated semigroups over bands and biordered sets with trivial products
• Partitioned binary relations
• Maximal subgroups of free idempotent generated semigroups over the full linear monoid.
• Infinite partition monoids.
• Maximal subgroups of free idempotent-generated semigroups over the full transformation monoid.
• Basic Representations of Completely Simple Semigroups
• Embedding any countable semigroup in a 2-generated bisimple monoid
• Temperley-Lieb algebras and the long distance properties of statistical mechanical models
• PERIODIC ELEMENTS OF THE FREE IDEMPOTENT GENERATED SEMIGROUP ON A BIORDERED SET
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sets of idempotents that generate the semigroup of singular endomorphisms of a finite-dimensional vector space
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the growth of generating sets for direct powers of semigroups.
• John Macintosh Howie: work and legacy
• Defining relations for idempotent generators in finite partial transformation semigroups.
• Every group is a maximal subgroup of a naturally occurring free idempotent generated semigroup.
• Products of idempotents in the semigroup of singular endomorphisms of a finite-dimensional vector space
• COMBINATORIAL TECHNIQUES FOR DETERMINING RANK AND IDEMPOTENT RANK OF CERTAIN FINITE SEMIGROUPS
• Irreducible representations of Brauer algebras
• Title not available (Why is that?)
• The idempotent-generated subsemigroup of the Kauffman monoid
• On finite 0-simple semigroups and graph theory
• The number of irreducible tournaments
• Idempotents in partial transformation semigroups
• Matrix Representations of Completely Simple Semigroups
• Products of idempotent matrices
• A solution of the word problem for free \(^*\)-regular semigroups
• Characters of the partition algebras.
• A symmetrical presentation for the singular part of the symmetric inverse monoid.
• Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
• \(q\)-partition algebra combinatorics
• Cohomological stratification of diagram algebras.

Cited In (36)

• Presentations for singular wreath products
• Lattice paths and submonoids of \(\mathbb{Z}^2\)
• Title not available (Why is that?)
• The idempotent-generated subsemigroup of the Kauffman monoid
• Computing finite semigroups
• Standard paths and standard monomials fixed by a diagram automorphism
• Monoidal categories, representation gap and cryptography
• On the determinants of the square-type Stirling matrix and Bell matrix
• Enumeration of idempotents in planar diagram monoids
• Presentations for rook partition monoids and algebras and their singular ideals
• Ehresmann theory and partition monoids
• Identities of the Kauffman Monoid $$\mathcal {K}_4$$ and of the Jones Monoid $$\mathcal {J}_4$$
• Structure of principal one-sided ideals
• Idempotents and one-sided units in infinite partial Brauer monoids
• Ranks of ideals in inverse semigroups of difunctional binary relations
• Maximal subsemigroups of finite transformation and diagram monoids
• Twisted Brauer monoids
• A groupoid approach to regular \(\ast \)-semigroups
• Congruence lattices of finite diagram monoids
• Presentations for wreath products involving symmetric inverse monoids and categories
• Motzkin monoids and partial Brauer monoids
• Sandwich semigroups in diagram categories
• HALL'S CONDITION AND IDEMPOTENT RANK OF IDEALS OF ENDOMORPHISM MONOIDS
• Ideal Structure of the Kauffman and Related Monoids
• Enumeration of idempotents in diagram semigroups and algebras
• Identities of the Kauffman monoid \(\mathcal{K}_3\)
• On groups generated by involutions of a semigroup.
• Heights of one- and two-sided congruence lattices of semigroups
• Classification of congruences of twisted partition monoids
• Free idempotent generated semigroups: the word problem and structure via gain graphs
• Presentations for (singular) partition monoids: a new approach
• Congruence Lattices of Ideals in Categories and (Partial) Semigroups
• Idempotents and one-sided units: lattice invariants and a semigroup of functors on the category of monoids
• On the number of principal ideals in \(d\)-tonal partition monoids
• Variants of finite full transformation semigroups.
• Alternating submodules for partition algebras, rook algebras, and rook-Brauer algebras

Uses Software

• GAP
• Semigroups

This page was built for publication: Diagram monoids and Graham-Houghton graphs: idempotents and generating sets of ideals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q346439)