Skip to main content
SpringerLink
Log in

Ranks of ideals in inverse semigroups of difunctional binary relations

  • RESEARCH ARTICLE
  • Published:
Semigroup Forum Aims and scope Submit manuscript

Abstract

The set \(\mathcal {D}_n\) of all difunctional relations on an n element set is an inverse semigroup under a variation of the usual composition operation. We solve an open problem of Kudryavtseva and Maltcev (Publ Math Debrecen 78(2):253–282, 2011), which asks: What is the rank (smallest size of a generating set) of \(\mathcal {D}_n\)? Specifically, we show that the rank of \(\mathcal {D}_n\) is \(B(n)+n\), where B(n) is the nth Bell number. We also give the rank of an arbitrary ideal of \(\mathcal {D}_n\). Although \(\mathcal {D}_n\) bears many similarities with families such as the full transformation semigroups and symmetric inverse semigroups (all contain the symmetric group and have a chain of \(\mathscr {J}\)-classes), we note that the fast growth of \({\text {rank}}(\mathcal {D}_n)\) as a function of n is a property not shared with these other families.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. We note that Proposition 7 in an earlier version of [11], available at http://arxiv.org/pdf/math/0602623v1.pdf, leads to a lower bound for \({\text {rank}}(\mathcal {D}_n)\) that is fairly close to the precise value.

References

  1. Aĭzenštat, A.J.: Defining relations of finite symmetric semigroups. Matematicheskii Sbornik 45(87), 261–280 (1958). (in Russian)

    MathSciNet  Google Scholar 

  2. East, J.: Generators and relations for partition monoids and algebras. J. Algebra 339, 1–26 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  3. East, J., Gray, R.D.: Diagram monoids and Graham–Houghton graphs: idempotents and generating sets of ideals. J. Comb. Theory Ser. A 146, 63–128 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  4. Garba, G.U.: Idempotents in partial transformation semigroups. Proc. R. Soc. Edinb. Sect. A 116(3–4), 359–366 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  5. Gomes, G., Howie, J.M.: On the ranks of certain finite semigroups of transformations. Math. Proc. Camb. Philos. Soc. 101(3), 395–403 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  6. Gray, R.D.: The minimal number of generators of a finite semigroup. Semigroup Forum 89(1), 135–154 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  7. Hellman, M.: A cryptanalytic time–memory trade-off. IEEE Trans Inf Theory 26(4), 401–406 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  8. Howie, J.M.: Fundamentals of semigroup theory, volume 12 of London Mathematical Society monographs. New series. The Clarendon Press, Oxford University Press, New York. Oxford Science Publications (1995)

  9. Howie, J.M., McFadden, R.B.: Idempotent rank in finite full transformation semigroups. Proc. R. Soc. Edinb. Sect. A 114(3–4), 161–167 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  10. Howie, J.M., Ruškuc, N., Higgins, P.M.: On relative ranks of full transformation semigroups. Commun. Algebra 26(3), 733–748 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  11. Kudryavtseva, G., Maltcev, V.: Two generalisations of the symmetric inverse semigroups. Publ. Math. Debrecen 78(2), 253–282 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  12. Lawson, M.V.: Inverse semigroups. The theory of partial symmetries. World Scientific, River Edge (1998)

    Book  MATH  Google Scholar 

  13. Moore, E.H.: Concerning the abstract groups of order \(k!\) and \(\tfrac{1}{2}k!\) holohedrically isomorphic with the symmetric and the alternating substitution-groups on \(k\) letters. Proc. Lond. Math. Soc. 28(1), 357–366 (1897)

    MathSciNet  MATH  Google Scholar 

  14. Popova, L.M.: Defining relations in some semigroups of partial transformations of a finite set. Uchenye Zap. Leningrad Gos. Ped. Inst. 218, 191–212 (1961). (in Russian)

    Google Scholar 

  15. Riguet, J.: Relations binaires, fermetures, correspondances de Galois. Bull. Soc. Math. France 76, 114–155 (1948)

    Article  MathSciNet  MATH  Google Scholar 

  16. The on-line encyclopedia of integer sequences. http://oeis.org/ (2016)

  17. Vernitski, A.: A generalization of symmetric inverse semigroups. Semigroup Forum 75(2), 417–426 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  18. Vorob’ev, N.N.: On symmetric associative systems. Leningrad. Gos. Ped. Inst. Uč. Zap. 89, 161–166 (1953)

    MathSciNet  Google Scholar 

  19. Zhao, P., Fernandes, V.H.: The ranks of ideals in various transformation monoids. Commun. Algebra 43(2), 674–692 (2015)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Centre for Research in Mathematics, School of Computing, Engineering and Mathematics, Western Sydney University, Locked Bag 1797, Penrith, NSW, 2751, Australia

    James East

  2. Department of Mathematical Sciences, University of Essex, Colchester, UK

    Alexei Vernitski

Authors
  1. James East
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alexei Vernitski
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to James East.

Additional information

Communicated by Norman R. Reilly.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

East, J., Vernitski, A. Ranks of ideals in inverse semigroups of difunctional binary relations. Semigroup Forum 96, 21–30 (2018). https://doi.org/10.1007/s00233-017-9846-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00233-017-9846-9

Keywords

Search

Navigation