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.
Download file
Counter downloads: 44
- Title Researches of semigroups with planar Cayley graphs: results and problems
- Headline Researches of semigroups with planar Cayley graphs: results and problems
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 54
- Date:
- DOI 10.17223/20710410/54/1
Keywords
semigroup, Cayley graph of semigroup, planar graph, semigroup variety, planarity rankAuthors
References
Drufu C. and Kapovich M. Geometric Group Theory. Colloquium Publ. AMS. 2018. V. 63. 819 p.
McCammond J., Rhodes J., and Steinberg B. Geometric Semigroup Theory. arXiv:1104.2301 [math.GR]. 2011.
Cayley A. The theory of groups: graphical representation // Amer. J. Math. 1878. V. 1. P. 174-176.
Cooperman G., Finkelstein L., and Sarawagi N. Applications of Cayley graphs // LNCS. 1991. V. 508. P.367-378.
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 p.
Zemor G. Hash functions and Cayley graphs // Des. Codes Crypt. 1994. V.4. P.381-394.
Tripi A. Cayley Graphs of Groups and Their Applications. MSU Graduate Theses. 2017. V.3133. 47 p.
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 p.
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. 1896. V. 18. No.2. P.156-194.
Беленкова Ж. Т., Романьков В. А. Регулярные графы Кэли. Деп. ВИНИТИ. 1997. №802-V97. 37 c.
Беленкова Ж. Т., Романьков В. А. Плоские графы Кэли конечных групп. Препринт. Омск: ОмГУ, 1997. 8 с.
Беленкова Ж. Т. Все плоские графы Кэли группы S4. Препринт. Омск: ОмГУ, 1997. 12с.
Беленкова Ж. Т. Плоские графы Кэли: дис.. канд. физ.-мат. наук. Омск: ОмГУ, 1998.
Droms C., Servatius B., and Servatius H. Connectivity and planarity of Cayley graphs // Beitrage zur Algebra und Geometrie. 1998. V.39. No.2. P.269-282.
Droms C. Infinite-ended groups with planar Cayley graphs // J. Group Theory. 2006. V. 9. No. 4. P. 487-496.
Dunwoody M. J. Planar Graphs and Covers. https://arxiv.org/abs/0708.0920.2009.
Georgakopoulos A. Characterising planar Cayley graphs and Cayley complexes in terms of group presentations // Europ. J. Combinatorics. 2014. V. 36. P. 282-293.
Georgakopoulos A. The planar cubic Cayley graphs of connectivity 2 // Europ. J. Combinatorics. 2017. V. 64. P. 152-169.
Georgakopoulos A. The planar cubic Cayley graphs // Mem. Amer. Math. Soc. 2017. V. 250. No. 1190. 82 p.
Georgakopoulos A. and Hamann M. The planar Cayley graphs are effectively enumerable I: Consistently planar graphs // Combinatorica. 2019. V.39. No. 5. P.993-1019.
Georgakopoulos A. and Hamann M. The Planar Cayley Graphs are Effectively Enumerable II. https://arxiv.org/abs/1901.00347.2019.
Varghese O. Planarity of Cayley graphs of graph products of groups // Discrete Math. 2019. V. 342. No. 6. P.1812-1819.
Georgakopoulos A. On planar Cayley graphs and Kleinian groups // Trans. Amer. Math. Soc. 2020. V. 373. No. 7. P. 4649-4684.
Paalman A. B. Topological representation of semigroups // General Topology and its Relations to Modern Analysis and Algebra. Praha: Academia Publishing House AS CR, 1967. P. 276-282.
Bosak J. The graphs of semigroups // Proc. Symp. “Theory of Graphs and its Applications”. Praha, 1964. P.119-125.
Zelinka B. The diameter of the graph of the system of proper semigroups of a commutative semigroup // Mat.-Fyz. Cas. SAV. 1965. V. 15. P.143-144.
Zelinka B. Graphs of semigroups // Cas. Pest. Mat. 1981. P.407-408.
Knauer K. and Knauer U. Toroidal embeddings of right groups // Thai J. Math. 2010. V. 8. No. 3. P. 483-490.
Knauer K. and Knauer U. On planar right groups // Semigroup Forum. 2016. V. 92. No. 1. P. 142-157.
http://www.mathnet.ru/php/seminars.phtml?presentid=12900 - Новые проблемы алгебры и логики. Юбилейное 900-е заседание семинара: Омский алгебраический семинар, 12 ноября 2015.
Адян С. И. Алгоритмическая неразрешимость проблем распознавания некоторых свойств групп // Докл. АН СССР. 1955. Т. 103. №4. С. 533-535.
Rabin M. O. Recursive unsolvability of group theoretic problems // Ann. Math. 1958. V. 67. P. 172-174.
Zieschang H., Vogt E., and Coldewey H. D. Surfaces and Planar Discontinuous Groups. Berlin: Springer Verlag, 1980. 336 p.
Margolis S. W. and Meakin J. C. E-unitary inverse monoids and the Cayley graph of a group representation // J. Pure Appl. Algebra. 1989. V. 58. P.45-76.
Kelarev A. V. and Quinn S. J. On complete and bipartite Cayley graphs // Arbeitstagung Allgemeine Algebra 62, June 14-17, 2001. Abstracts. Linz: Austria, 2001. P.25.
Kelarev A. V. and Praeger C. E. On transitive Cayley graphs of groups and semigroups // Europ. J. Combinatorics. 2003. V. 24. P.59-72.
Kelarev A. V. and Quinn S. J. A combinatorial property and Cayley graphs of semigroups // Semigroup Forum. 2002. V. 66. No. 1. P.89-96.
Kelarev A. V. On undirected Cayley graphs // Australasian J. Combinatorics. 2002. V. 25. P. 73-78.
Kelarev A. V. On Cayley graphs of inverse semigroups // Semigroup Forum. 2006. V. 72. P.411-418.
Khosravi Be. and Khosravi Ba. On Cayley graphs of semilattices of semigroups // Semigroup Forum. 2013. V. 86. P.114-132.
Khosravi Be. and Khosravi Ba. A characterization of Cayley graphs of Brandt semigroups // Bull. Malaysian Math. Sci. Soc. 2012. V. 2. No. 2. P.12-18.
Khosravi B. On Cayley graphs of left groups // Houston J. Math. 2009. V. 35. No.3. P. 745-755.
Fan S. and Zeng Y. On Cayley graphs of Bands // Semigroup Forum. 2007. V. 74. P. 99-105.
Макарьев А. Л. О полугруппах идемпотентов с ациклическими графами Кэли // Математика и информатика: Наука и образование. 2007. Т. 6. С. 26-34.
Соломатин Д. В. Строение полугрупп, допускающих внешнепланарные графы Кэли // Сиб. электрон. матем. изв. 2011. Т. 8. С. 191-212.
Макарьев А. Л. Нильпотентные полугруппы, основа графа Кэли которых является деревом // Математика и информатика: Наука и образование. 2006. Т. 5. С. 40-46.
Макарьев А. Л. Полурешётки с ациклическими графами Кэли // Математика и информатика: Наука и образование. 2008. Т. 7. С. 28-33.
Макарьев А. Л. Ординальные суммы полугрупп с ациклическими графами Кэли // Вестник Омского университета. 2008. Т. 4. С. 12-17.
Мартынов Л. М., Соломатин Д. В. Полугруппы вычетов с циклическими группами обратимых элементов, допускающие планарные графы Кэли // Вестник Омского университета. 2012. Т.2. С.57-62.
Мартынов П. О., Соломатин Д. В. Конечные свободные коммутативные полугруппы и полугруппы с нулём, допускающие обобщенные внешнепланарные графы Кэли // Вестник Омского университета. 2014. Т. 3. С. 22-26.
Мартынов П. О. Конечные свободные коммутативные моноиды, допускающие обобщенно внешнепланарные графы Кэли // Вестник Омского университета. 2015. Т. 4. С. 6-9.
Мартынов П. О. Рассыпчатые полугруппы, допускающие обобщенные внешнепланарные графы Кэли // Вестник Омского университета. 2018. Т. 3. С. 6-9.
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. P. 18-19.
Molchanov V. A. A universal planar automaton is determined by its semigroup of input symbols // Semigroup Forum. 2011. V. 82. P. 1-9.
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. Tartu: EMS, 2008. P. 151-160.
Шеврин Л. Н. Полугруппы // Общая алгебра (ред. Л. А. Скорняков). Гл. IV. М.: Наука, 1991. Т. 2. С. 11-191.
Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384c.
Martynova T. A. The groupoid of 0-reduced varieties of semigroups // Semigroup Forum. 1983. V. 26. P. 249-274.
Preston G. and Clifford A. The Algebraic Theory of Semigroups // Amer. Math. Soc. 1964. V. 1. No. 7. P. 169-174.
Соломатин Д. В. Ранги планарности многообразий коммутативных моноидов // Вестник Омского университета. 2012. Т. 4. С. 41-45.
Соломатин Д. В. О допустимости некоторых графов в качестве графов Кэли полугрупп // Математика и информатика: Наука и образование. 2004. Т. 4. С. 32-34.
Lempel A, Even S., and Cederbaum I. An algorithm for planarity testing of graphs // Proc. Int. Symp. Theory Graphs. New York, 1967. P.215-232.
Klein P. N. and Reif J. H. An efficient parallel algorithm for planarity // J. Computer System Sci. 1988. V. 37. P. 190-246.
Bader D. A. and Sreshta S. A. A New Parallel Algorithm for Planarity Testing. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.65.2914&rep=rep1&type=pdf.2003.
Соломатин Д. В. О критериях планарности графов Кэли полугрупп // Математика и информатика: Наука и образование. 2010. Т. 9. С. 44-46.
Соломатин Д. В. Стохастический алгоритм поиска подграфа, гомеоморфного заданному // Стохастические модели в биологии и предельные алгебры (Омск, 2-7 августа 2010). Омск: ИМ им. С. Л. Соболева СО РАН, 2010. С. 98-100.
Kambites M. The loop problem for Rees matrix semigroups // Semigroup Forum. 2008. V. 76. No. 2. P.204-216.
Мелихов А. Н., Берштейн Л. С., Курейчик В. М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974. 304c.
Levinson H. On the genera of graphs of group presentations // Ann. New York Acad. Sci. 1970. V. 175. P. 277-284.
Соломатин Д. В. Свободные частично коммутативные n-веерные полурешетки с планарными графами Кэли // Математика и информатика: Наука и образование. 2009. Т. 8. С. 36-39.
Соломатин Д. В. Свободные частично коммутативные нильпотентные полугруппы с планарными графами Кэли // Вестник Омского университета. 2014. Т. 3. С. 28-36.
Соломатин Д. В. Конечные свободные коммутативные полугруппы с планарными графами Кэли // Математика и информатика: Наука и образование. 2003. Т. 3. С. 32-38.
Соломатин Д. В. Конечные свободные коммутативные моноиды, допускающие планарный граф Кэли // Вестник Омского университета. 2005. Т. 4. С. 36-38.
Birkhoff G. On the structure of abstract algebras // Proc. Camb. Phil. Soc. 1935. V. 31. P. 433-454.
Соломатин Д. В. Прямые произведения циклических полугрупп, допускающие планарный граф Кэли // Сиб. электрон. матем. изв. 2006. Т. 3. С. 238-252.
Соломатин Д. В. Прямые произведения циклических моноидов и полугрупп с нулем, допускающие планарные графы Кэли // Математика и информатика: Наука и образование. 2006. Т. 5. С. 51-64.
Соломатин Д. В. Критерий планарности для графов Кэли 0-прямых объединений нильпотентных полугрупп // Мальцевские чтения (2-6 мая 2010). Новосибирск: ИМ им. С. Л. Соболева СО РАН, 2010. C. 144.
Соломатин Д. В. Рассыпчатые полугруппы с планарными графами Кэли // Вестник Волгоградского государственного педагогического университета. 2005. Т. 4. С. 27-31.
Полякова Л. Ю. Резольвенты для свободных частично коммутативных моноидов // Сиб. матем. журн. 2007. Т. 48. С. 1295-1304.
Diekert V. and Metivier Y. Partial commutation and traces // Handbook of Formal Languages. Berlin: Springer Verlag, 1997. V. 3. P. 457-533.
Sedlacek J. On a generalization of outerplanar graphs // Casopis Pest. Mat. 1988. V. 2. No. 113. P.213-218.
Соломатин Д. В. Планарные гиперграфы мультипликативных полугрупп вычетов // Математика и информатика: Наука и образование. 2011. Т. 10. С. 30-34.
Булатов А. А. Алгебраические методы исследования комбинаторных задач: дис.. докт. физ.-мат. наук. Екатеринбург, 2008.
Zinbiel G. W. Encyclopedia of Types of Algebras 2010. arXiv:1101.0267v1. 2010.
Sudoplatov S. V. Hypergraphs of prime models and distributions of countable models of small theories // J. Math. Sci. 2010. V. 169. No. 5. P.680-695.
Зыков А. А. Гиперграфы // Успехи матем. наук. 1974. Т. 29. №6(180). С. 89-154.
Соломатин Д. В. Конечно порожденные полугруппы с одним определяющим соотношением и тождеством, допускающие планарный граф Кэли // Математика и информатика: Наука и образование. 2007. Т. 6. С. 42-48.
Соломатин Д. В. Ординальные суммы прямоугольных полугрупп, допускающие планарные графы Кэли // Математика и информатика: Наука и образование. 2008. Т. 7. С. 33-41.
Соломатин Д. В. Планарные многообразия полугрупп // Сиб. электрон. матем. изв. 2015. Т. 12. С. 232-247.
Соломатин Д. В. Планарные многообразия коммутативных полугрупп // Вестник Омского университета. 2015. Т. 2. С.17-22.
Соломатин Д. В. Ранги планарности многообразий коммутативных полугрупп // Прикладная дискретная математика. 2016. №4(34). С. 50-64.
Соломатин Д. В. О рангах планарности многообразий полугрупп идемпотентов, ниль-полугрупп и полугрупп с перестановочным тождеством // Вестник Омского университета. 2017. Т. 4. №86. С. 11-21.
Соломатин Д. В. О рангах планарности многообразий нильполугрупп // Вестник Омского университета. 2019. Т. 2. №24. С. 17-22.
Соломатин Д. В. Ранги планарности многообразий полугрупп // Вестник Омского университета. 2019. Т. 4. С. 9-15.
Hopcroft J. and Tarjan R. Efficient planarity testing // J. ACM. 1974. V. 21. No. 4. P. 549-568.
Chiba N., Yamanouchi T., and Nishizeki T. Linear algorithms for convex drawings of planar graphs // J.A. Bondy, U.S.R. Murty (eds.). Progress in Graph Theory. London: Academic Press, P. 153-173.
Head T. J. The varieties of commutative monoids // Nieuw Archief voor Wiskunde. 1968. V.3. No. 16. P.203-206.
Соломатин Д. В. Ранги планарности многообразий полугрупп, заданных тождеством x ~ xn // Вестник Омского Университета. 2020. Т. 3. №25. С. 13-17.
Evans T. The lattice of semigroup varieties // Semigroup Forum. 1971. V. 2. P. 1-43.
Arthan R. and Oliva P. Studying algebraic structures using Prover9 and Mace4 // G. Hanna et al. (eds.) Proof Technology in Mathematics Research and Teaching. Ch. 5. Springer, 2020.
Fennemore C. All varieties of bands // Semigroup Forum. 1970. V. 1. P. 172-179.
Green J. A. and Rees D. On semigroups in which xr = x, Proc. Cambridge Philos. Soc. 1952. V. 48. P. 35-40.
Howie J. M. Fundamentals of Semigroup Theory. London Math. Society Monographs. New Series, 12. Oxford Science Publ. N.Y.: Clarendon Press, Oxford University Press, 1995. 351 p.
Preston G. and Clifford A. The algebraic theory of semigroups // Amer. Math. Soc. 1961. V. 1. No. 1. P. 12-31.
Ljapin E. S. Semigroups. Amer. Math. Soc. 4th ed. 1963. 519 p.
Соломатин Д. В. Теория представлений: учеб. пособие. Омск: ОмГПУ, 2015. 64 с.
Гуревич Ю. Ш. Проблема равенства слов для некоторых классов полугрупп // Алгебра и логика. 1966. Т. 5. №5. С. 25-35.
De Verdiere Y. C. Sur un Nouvel Invariant des Graphes et un Critere de Planarite // J. Combinat. Theory. Ser. B. 1990. No. 50. P.11-21.
Канторович Л. В., Крылов В. И. Приближенные методы высшего анализа. 5-е изд. М.,Л.: Физматгиз, 1962. 708с.
Fedorov F. M. On the theory of infinite systems of linear algebraic equations // TWMS J. Pure Appl. Math. 2015. V.2. No.6. P.202-212.
Мартынов Л. М. Полнота, редуцированность, примарность и чистота для алгебр: результаты и проблемы // Сиб. электрон. матем. изв. 2016. Т. 13. С. 181-241.
Researches of semigroups with planar Cayley graphs: results and problems | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2021. № 54. DOI: 10.17223/20710410/54/1
Download full-text version
Counter downloads: 71