Researches of semigroups with planar Cayley graphs: results and problems

D. V. Solomatin

Prikladnaâ diskretnaâ matematika, no. 4 (2021), pp. 5-57.

Résumé

The classical Cayley graphs for groups have long and thoroughly proven themselves in solving applied problems, finding application in various scientific fields, from cryptography to campanology. Recently, more and more attention has been paid to the researching the applied aspects of Cayley graphs of semigroups. In this paper, we survey a result obtained in investigations on semigroups with planar Cayley graphs and results on the study of planarity rank of a semigroup varieties. A number of unsolved problems are formulated, the solution of which finds application in the combinatorial theory of semigroups. Just as Cayley graphs of semigroups are used for constructing hash functions, the concluding part of the paper introduces the concept of the spectrum of planarity ranks for varieties of semigroups, with the help of which it becomes possible to hash semigroup varieties.

Détail

Keywords: semigroup, Cayley graph of semigroup, planar graph, semigroup variety, planarity rank.

Bibliographie

[1] Druţu C., Kapovich M., Geometric Group Theory, Colloquium Publ., 63, AMS, 2018, 819 pp. | DOI | MR | Zbl

[2] McCammond J., Rhodes J., Steinberg B., Geometric Semigroup Theory, 2011, arXiv: 1104.2301 [math.GR]

[3] Cayley A., “The theory of groups: graphical representation”, Amer. J. Math., 1 (1878), 174–176 | DOI | MR | Zbl

[4] Cooperman G., Finkelstein L., Sarawagi N., “Applications of Cayley graphs”, LNCS, 508, 1991, 367–378 | MR | Zbl

[5] Horwitz J. A., Applications of Cayley Graphs, Bilinearity, and Higher-Order Residues to Cryptology, Diss. for the Degree of Doctor of Philosophy, Stanford, 2004, 100 pp.

[6] Zémor G., “Hash functions and Cayley graphs”, Des. Codes Crypt., 4 (1994), 381–394 | DOI | MR | Zbl

[7] Tripi A., Cayley Graphs of Groups and Their Applications, MSU Graduate Theses, 3133, 2017, 47 pp.

[8] Sosnovski B., Cayley Graphs of Semigroups and Applications to Hashing, Diss. for the Degree of Doctor of Philosophy, City University of New York, 2016, 111 pp. | MR

[9] Maschke H., “The representation of finite groups, especially of the rotation groups of the regular bodies of three- and four-dimensional space, by Cayley's color diagrams”, Amer. J. Math., 18:2 (1896), 156–194 | DOI | MR | Zbl

[10] Belenkova Zh. T., Roman'kov V. A., Regular Cayley graphs, Dep. VINITI, No 802-97, 1997 (in Russian)

[11] Belenkova Zh. T., Roman'kov V. A., Plane Cayley graphs of finite groups, Preprint, OmSU, Omsk, 1997, 8 pp. (in Russian)

[12] Belenkova Zh. T., All plane Cayley graphs of the group $S_4$, Preprint, OmSU, Omsk, 1997, 12 pp. (in Russian)

[13] Belenkova Zh. T., Plane Cayley graphs, PhD Thesis, OmSU, Omsk, 1998 (in Russian)

[14] Droms C., Servatius B., Servatius H., “Connectivity and planarity of Cayley graphs”, Beiträge zur Algebra und Geometrie, 39:2 (1998), 269–282 | MR | Zbl

[15] Droms C., “Infinite-ended groups with planar Cayley graphs”, J. Group Theory, 9:4 (2006), 487–496 | DOI | MR | Zbl

[16] Dunwoody M. J., Planar Graphs and Covers, 2009, arXiv: 0708.0920

[17] Georgakopoulos A., “Characterising planar Cayley graphs and Cayley complexes in terms of group presentations”, Europ. J. Combinatorics, 36 (2014), 282–293 | DOI | MR | Zbl

[18] Georgakopoulos A., “The planar cubic Cayley graphs of connectivity 2”, Europ. J. Combinatorics, 64 (2017), 152–169 | DOI | MR | Zbl

[19] Georgakopoulos A., The planar cubic Cayley graphs, Mem. Amer. Math. Soc., 250, no. 1190, 2017, 82 pp. | MR

[20] Georgakopoulos A., Hamann M., “The planar Cayley graphs are effectively enumerable I: Consistently planar graphs”, Combinatorica, 39:5 (2019), 993–1019 | DOI | MR | Zbl

[21] Georgakopoulos A., Hamann M., The Planar Cayley Graphs are Effectively Enumerable II, 2019, arXiv: 1901.00347 | MR

[22] Varghese O., “Planarity of Cayley graphs of graph products of groups”, Discrete Math., 342:6 (2019), 1812–1819 | DOI | MR | Zbl

[23] Georgakopoulos A., “On planar Cayley graphs and Kleinian groups”, Trans. Amer. Math. Soc., 373:7 (2020), 4649–4684 | DOI | MR | Zbl

[24] Paalman A. B., “Topological representation of semigroups”, General Topology and its Relations to Modern Analysis and Algebra, Academia Publishing House AS CR, Praha, 1967, 276–282 | MR

[25] Bosák J., “The graphs of semigroups”, Proc. Symp. “Theory of Graphs and its Applications”, Praha, 1964, 119–125 | MR | Zbl

[26] Zelinka B., “The diameter of the graph of the system of proper semigroups of a commutative semigroup”, Mat.-Fyz. Cas. SAV, 15 (1965), 143–144 | MR

[27] Zelinka B., “Graphs of semigroups”, Cas. Pest. Mat., 1981, 407–408 | MR | Zbl

[28] Knauer K., Knauer U., “Toroidal embeddings of right groups”, Thai J. Math., 8:3 (2010), 483–490 | MR | Zbl

[29] Knauer K., Knauer U., “On planar right groups”, Semigroup Forum, 92:1 (2016), 142–157 | DOI | MR | Zbl

[30] Novye problemy algebry i logiki. Yubileinoe 900-e zasedanie seminara: Omskii algebraicheskii seminar (12 noyabrya 2015) http://www.mathnet.ru/php/seminars.phtml?presentid=12900

[31] Adian S. I., “Algorithmic unsolvability of problems of recognition of certain properties of groups”, Dokl. USSR Academy of Sciences, 103:4 (1955), 533–535 (in Russian) | MR | Zbl

[32] Rabin M. O., “Recursive unsolvability of group theoretic problems”, Ann. Math., 67 (1958), 172–174 | DOI | MR

[33] Zieschang H., Vogt E., Coldewey H. D., Surfaces and Planar Discontinuous Groups, Springer Verlag, Berlin, 1980, 336 pp. | MR | Zbl

[34] Margolis S. W., Meakin J. C., “$E$-unitary inverse monoids and the Cayley graph of a group representation”, J. Pure Appl. Algebra, 58 (1989), 45–76 | DOI | MR | Zbl

[35] Kelarev A. V., Quinn S. J., Abstracts (June 14–17, 2001, Linz, Austria), Arbeitstagung Allgemeine Algebra 62, 2001, 25 pp.

[36] Kelarev A. V., Praeger C. E., “On transitive Cayley graphs of groups and semigroups”, Europ. J. Combinatorics, 24 (2003), 59–72 | DOI | MR | Zbl

[37] Kelarev A. V., Quinn S. J., “A combinatorial property and Cayley graphs of semigroups”, Semigroup Forum, 66:1 (2002), 89–96 | DOI | MR

[38] Kelarev A. V., “On undirected Cayley graphs”, Australasian J. Combinatorics, 25 (2002), 73–78 | MR | Zbl

[39] Kelarev A. V., “On Cayley graphs of inverse semigroups”, Semigroup Forum, 72 (2006), 411–418 | DOI | MR | Zbl

[40] Khosravi Be., Khosravi Ba., “On Cayley graphs of semilattices of semigroups”, Semigroup Forum, 86 (2013), 114–132 | DOI | MR | Zbl

[41] Khosravi Be., Khosravi Ba., “A characterization of Cayley graphs of Brandt semigroups”, Bull. Malaysian Math. Sci. Soc., 2:2 (2012), 12–18 | MR

[42] Khosravi B., “On Cayley graphs of left groups”, Houston J. Math., 35:3 (2009), 745–755 | MR | Zbl

[43] Fan S., Zeng Y., “On Cayley graphs of Bands”, Semigroup Forum, 74 (2007), 99–105 | DOI | MR | Zbl

[44] Makarjev A. L., “About semigroups of idempotents with Cayley acyclic graphs”, Mathematics and Computer Science: Science and Education, 6 (2007), 26–34 (in Russian)

[45] Solomatin D. V., “Semigroups with outerplanar Cayley graphs”, Sib. Elektron. Mat. Izv., 8 (2011), 191–212 (in Russian) | MR

[46] Makar'ev A. L., “Nilpotent semigroups whose Cayley graph base is a tree”, Mathematics and Computer Science: Science and Education, 5 (2006), 40–46 (in Russian)

[47] Makar'ev A. L., “Semilattices with Cayley acyclic graphs”, Mathematics and Computer Science: Science and Education, 7 (2008), 28–33 (in Russian)

[48] Makar'ev A. L., “Ordinal sums of semigroups with Cayley acyclic graphs”, Herald of Omsk University, 4 (2008), 12–17 (in Russian)

[49] Martynov L. M., Solomatin D. V., “Semigroups of residues with cyclic groups of invertible elements admitting planar Cayley graphs”, Herald of Omsk University, 2 (2012), 57–62 (in Russian)

[50] Martynov P. O., Solomatin D. V., “Finite free commutative semigroups and semigroups with zero how admitting generalized outerplanar Cayley graphs”, Herald of Omsk University, 3 (2014), 22–26 (in Russian)

[51] Martynov P. O., “Finite free commutative monoids who admitted generalized outerplanar Cayley graphs”, Herald of Omsk University, 4 (2015), 6–9 (in Russian)

[52] Martynov P. O., “Crisp semigroups admit generalized outerplanar Cayley graphs”, Herald of Omsk University, 3 (2018), 6–9 (in Russian)

[53] Khosravi B., “Comparison of Cayley graphs of semigroups and Cayley graphs of groups”, Book of Abstracts Caucasian Math. Conf. CMC II, Turkish Math. Society, 2007, 18–19

[54] Molchanov V. A., “A universal planar automaton is determined by its semigroup of input symbols”, Semigroup Forum, 82 (2011), 1–9 | DOI | MR | Zbl

[55] Zhang X., “Clifford semigroups with genus zero”, Proc. Intern. Conf. Semigroups, Acts and Categories with Applications to Graphs (University of Tartu, June 27–30, 2007), EMS, Tartu, 2008, 151–160 | MR

[56] Shevrin L. N., “Semigroups”, Algebra, Ch. IV, v. 2, ed. L. A. Skornyakov, Nauka Publ., M., 1991, 11–191 (in Russian)

[57] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lectures on Graph Theory, Nauka Publ., M., 1990, 384 pp. (in Russian) | MR

[58] Martynova T. A., “The groupoid of $0$-reduced varieties of semigroups”, Semigroup Forum, 26 (1983), 249–274 | DOI | MR | Zbl

[59] Preston G., Clifford A., “The Algebraic Theory of Semigroups”, Amer. Math. Soc., 1:7 (1964), 169–174 | MR

[60] Solomatin D. V., “Planarity ranks of the varieties of commutative monoids”, Herald of Omsk University, 4 (2012), 41–45 (in Russian)

[61] Solomatin D. V., “On the admissibility of some graphs as Cayley graphs of semigroups”, Mathematics and Computer Science: Science and Education, 4 (2004), 32–34 (in Russian)

[62] Lempel A., Even S., Cederbaum I., “An algorithm for planarity testing of graphs”, Proc. Int. Symp. Theory Graphs (New York, 1967), 215–232 | MR | Zbl

[63] Klein P. N., Reif J. H., “An efficient parallel algorithm for planarity”, J. Computer System Sci., 37 (1988), 190–246 | DOI | MR | Zbl

[64] Bader D. A., Sreshta S. A., A New Parallel Algorithm for Planarity Testing, 2003 https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.65.2914&rep=rep1&type=pdf

[65] Solomatin D. V., “About the criteria of planarity for Cayley graphs of semigroups”, Mathematics and Computer Science: Science and Education, 9 (2010), 44–46 (in Russian)

[66] Solomatin D. V., “Stochastic algorithm for search a homeomorphic subgraph”, Conference paper: Stochastic Models in Biology and Limit Algebras (Omsk, 2–7 August 2010), Sobolev Institute of Mathematics SB RAS, 2010, 98–100 (in Russian)

[67] Kambites M., “The loop problem for Rees matrix semigroups”, Semigroup Forum, 76:2 (2008), 204–216 | DOI | MR | Zbl

[68] Melikhov A. N., Bershtein L. S., Kureichik V. M., Application of Graphs in the Design of Discrete Devices, Nauka, M., 1974, 304 pp. (in Russian)

[69] Levinson H., “On the genera of graphs of group presentations”, Ann. New York Acad. Sci., 175 (1970), 277–284 | DOI | MR | Zbl

[70] Solomatin D. V., “Free partially commutative semigroups and the $n$-fan semilattices with planar Cayley graphs”, Mathematics and Computer Science: Science and Education, 8 (2009), 36–39 (in Russian) | MR

[71] Solomatin D. V., “Free partially commutative nilpotent semigroups with planar Cayley graphs”, Herald of Omsk University, 3 (2014), 28–36 (in Russian)

[72] Solomatin D. V., “Finite free commutative semigroups with planar Cayley graphs”, Mathematics and Computer Science: Science and Education, 3 (2003), 32–38 (in Russian)

[73] Solomatin D. V., “Finite free commutative monoids admitting planar Cayley graph”, Herald of Omsk University, 4 (2005), 36–38 (in Russian)

[74] Birkhoff G., “On the structure of abstract algebras”, Proc. Camb. Phil. Soc., 31 (1935), 433–454 | DOI

[75] Solomatin D. V., “Direct products of cyclic semigroups admitting a planar Caley graph”, Sib. Elektron. Mat. Izv., 3 (2006), 238–252 (in Russian) | MR | Zbl

[76] Solomatin D. V., “Direct products of cyclic monoids and semigroups with zero admitting planar Cayley graphs”, Mathematics and Computer Science: Science and Education, 5 (2006), 51–64 (in Russian) | MR

[77] Solomatin D. V., “A planarity criterion for Cayley graphs of $0$-direct unions of nilpotent semigroups”, Conf. paper: Maltsev Meeting 2010 (Novosibirsk, May 2–6, 2010), Sobolev Institute of Mathematics SB RAS, 2010, 144 (in Russian)

[78] Solomatin D. V., “Crisp semigroups with planar Cayley graphs”, Herald of Volgograd State Pedagogical University, 4 (2005), 27–31 (in Russian)

[79] Polyakova L. Yu., “Resolutions of free partially commutative monoids”, Siberian Math. J., 48 (2007), 1295–1304 (in Russian) | Zbl

[80] Diekert V., Métivier Y., “Partial commutation and traces”, Handbook of Formal Languages, v. 3, Springer Verlag, Berlin, 1997, 457–533 | DOI | MR

[81] Sedláček J., “On a generalization of outerplanar graphs”, Časopis Pěst. Mat., 2:113 (1988), 213–218 (in Czech) | MR | Zbl

[82] Solomatin D. V., “Planar hypergraphs of the multiplicative semigroup of residues”, Mathematics and Computer Science: Science and Education, 10 (2011), 30–34 (in Russian)

[83] Bulatov A. A., Algebraic methods in the study of combinatorial problems, Diss. of the Doctor Phys.-Mat. Sci., Ekaterinburg, 2008 (in Russian)

[84] Zinbiel G. W., Encyclopedia of Types of Algebras, 2010, arXiv: 1101.0267v1 | MR

[85] Sudoplatov S. V., “Hypergraphs of prime models and distributions of countable models of small theories”, J. Math. Sci., 169:5 (2010), 680–695 | DOI | MR | Zbl

[86] Zykov A. A., “Hypergraphs”, Uspekhi Mat. Nauk, 29:6(180) (1974), 89–154 (in Russian) | MR | Zbl

[87] Solomatin D. V., “Finitely generated semigroups with one defining relation and identity admitting planar Cayley graph”, Mathematics and Computer Science: Science and Education, 6 (2007), 42–48 (in Russian) | MR

[88] Solomatin D. V., “Ordinal sums of rectangular semigroups admitting a planar Cayley graph”, Mathematics and Computer Science: Science and Education, 7 (2008), 33–41 (in Russian)

[89] Solomatin D. V., “Planar varieties of semigroups”, Sib. Elektron. Mat. Izv., 12 (2015), 232–247 (in Russian) | MR | Zbl

[90] Solomatin D. V., “Planar varieties of commutative semigroups”, Herald of Omsk University, 2 (2015), 17–22 (in Russian)

[91] Solomatin D. V., “The ranks of planarity for varieties of commutative semigroups”, Prikladnaya Diskretnaya Matematika, 2016, no. 4(34), 50–64 (in Russian) | MR | Zbl

[92] Solomatin D. V., “On ranks of the planarity of varieties of all idempotent semigroups, nilsemigroups, and semigroups with the permutation identity”, Herald of Omsk University, 4:86 (2017), 11–21 (in Russian)

[93] Solomatin D. V., “On ranks of planarity of nil-semigroups varieties”, Herald of Omsk University, 2:24 (2019), 17–22 (in Russian)

[94] Solomatin D. V., “The ranks of the planarity for varieties of semigroups”, Herald of Omsk University, 4 (2019), 9–15 (in Russian)

[95] Hopcroft J., Tarjan R., “Efficient planarity testing”, J. ACM, 21:4 (1974), 549–568 | DOI | MR | Zbl

[96] Chiba N., Yamanouchi T., Nishizeki T., “Linear algorithms for convex drawings of planar graphs”, Progress in Graph Theory, eds. J. A. Bondy, U. S. R. Murty, Academic Press, London, 153–173 | MR

[97] Head T. J., “The varieties of commutative monoids”, Nieuw Archief voor Wiskunde, 3:16 (1968), 203–206 | MR

[98] Solomatin D. V., “Ranks of planarity for the variety of semigroups defined by the identity $x\approx x^n$”, Herald of Omsk University, 25:3 (2020), 13–17 (in Russian)

[99] Evans T., “The lattice of semigroup varieties”, Semigroup Forum, 2 (1971), 1–43 | DOI | MR | Zbl

[100] Arthan R. and Oliva P., “Studying algebraic structures using Prover9 and Mace4”, Proof Technology in Mathematics Research and Teaching, Ch. 5, eds. G. Hanna et al., Springer, 2020 | Zbl

[101] Fennemore C., “All varieties of bands”, Semigroup Forum, 1 (1970), 172–179 | DOI | MR | Zbl

[102] Green J. A., Rees D., “On semigroups in which $x^r= x$”, Proc. Cambridge Philos. Soc., 48 (1952), 35–40 | DOI | MR | Zbl

[103] Howie J. M., Fundamentals of Semigroup Theory, London Math. Society Monographs. New Series, 12, Oxford Science Publ.; Clarendon Press, Oxford University Press, N.Y., 1995, 351 pp. | MR | Zbl

[104] Preston G., Clifford A., “The algebraic theory of semigroups”, Amer. Math. Soc., 1:1 (1961), 12–31 | MR

[105] Ljapin E. S., Semigroups, Amer. Math. Soc., 4th ed., 1963, 519 pp. | MR

[106] Solomatin D. V., Representation Theory, Tutorial, OmSPU Publ., Omsk, 2015, 64 pp. (in Russian)

[107] Gurevich Yu. Sh., “The word problem for some classes of semigroups”, Algebra and Logic, 5:5 (1966), 25–35 (in Russian) | Zbl

[108] De Verdière Y. C., “Sur un Nouvel Invariant des Graphes et un Critère de Planarité”, J. Combinat. Theory. Ser. B, 1990, no. 50, 11–21 | DOI | MR | Zbl

[109] Kantorovich L. V., Krylov V. I., Approximate Methods of Higher Analysis, Interscience Interscience, Noordhoff, 1958, 704 pp. | MR | MR

[110] Fedorov F. M., “On the theory of infinite systems of linear algebraic equations”, TWMS J. Pure Appl. Math., 2:6 (2015), 202–212 | MR | Zbl

[111] Martynov L. M., “Completeness, reducibility, primarity and purity for algebras: results and problems”, Sib. Elektron. Mat. Izv., 13 (2016), 181–241 (in Russian) | Zbl