Symmetries of Cayley Graphs

凯莱图的对称性

• 批准号: RGPIN-2017-04905
• 负责人: Morris, Joy
• 金额: $ 1.17万
• 依托单位: University of Lethbridge
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=711288
• 关键词: Symmetries; Cayley; Graphs

My research program involves using permutation groups to study symmetries of Cayley graphs. A "graph" is a model of a network, with "vertices" (points) representing nodes or terminals, and edges representing connections. Cayley graphs are graphs with strong symmetry: a simple example is the pentagram (star), which has rotational and reflectional symmetries. Cayley graphs are interesting combinatorial objects to study for their own sakes. They also provide a class of graphs for which powerful techniques of group theory (abstract algebra) can be brought to bear in exploring difficult problems. I will continue to work with students, post-doctoral fellows, and collaborators, to explore open problems on symmetries of Cayley graphs, including: 1. There is a canonical way of colouring the edges of a Cayley graph so that the most natural symmetries of the graph preserve this canonical colouring. I will be exploring when it is the case that only the most natural symmetries preserve this colouring, and when extra symmetries might preserve this colouring. Edge-colourings are much studied since they can be used to represent properties that vary for different edges of the graph, such as capacity. However, most edge-colourings destroy most symmetry. 2. If a Cayley graph has the "Cayley Isomorphism property," algebraic techniques enable us to determine whether or not another Cayley graph is essentially the same network, just drawn differently. This has been much studied for finite graphs. I will be studying the extension of this problem to infinite graphs, which has attracted much less attention. I will also work to extend some previous results of mine on which finite graphs have this property. 3. Sometimes Cayley graphs are allowed to have directed edges, representing one-way connections in the network; if they do, we call them digraphs. It is known that (with some exceptions) any "nice" collection of symmetries (a symmetry group) has a "regular" representation by a Cayley graph, meaning that there is a Cayley graph with precisely these "regular" symmetries. There is a similar result for Cayley digraphs. However, whether or not a symmetry group can be regularly represented by an oriented Cayley graph (with at most one directed edge between any pair of vertices) is a long-standing open problem. A co-author and I recently solved this problem for "non-solvable" symmetry groups. We will try to extend our work to "solvable" symmetry groups. 4. Describing a graph as a Cayley graph provides information about a large number of its symmetries, but often not all of them. I will work to characterise graphs that can be represented as a Cayley graph in more than one way. The second representation significantly enhances our ability to understand all of the symmetries such graphs exhibit. These are steps toward solving recognition and isomorphism problems for Cayley graphs: extremely important open questions in algebraic graph theory.

我的研究计划涉及使用置换群来研究凯莱图的对称性。“图”是网络的模型，其中“顶点”（点）表示节点或终端，而边表示连接。凯莱图是具有强对称性的图：一个简单的例子是五角星（星星），它具有旋转和反射对称性。 凯莱图是有趣的组合对象研究自己的缘故。他们还提供了一类图，其中强大的群论（抽象代数）的技术可以带来承担探索困难的问题。 我将继续与学生，博士后研究员和合作者合作，探索Cayley图对称性的开放问题，包括： 1.有一个规范的方式着色的边缘凯莱图，使最自然的对称性的图保持这种规范的着色。我将探讨什么时候只有最自然的对称性才能保持这种着色，什么时候额外的对称性可能保持这种着色。边着色被广泛研究，因为它们可以用来表示图的不同边的不同属性，例如容量。然而，大多数边缘着色破坏了大多数对称性。 2.如果一个凯莱图具有“凯莱同构性质”，代数技术使我们能够确定另一个凯莱图是否本质上是相同的网络，只是绘制不同。对于有限图，这已经被研究了很多。我将研究这个问题扩展到无限图，这引起了较少的关注。我也将努力扩展我以前的一些结果，有限图有这个属性。 3.有时凯莱图允许有向边，表示网络中的单向连接;如果它们有向边，我们称之为有向图。已知（除了某些例外）任何对称性的“好”集合（对称群）都有一个“正则”的凯莱图表示，这意味着存在一个凯莱图，正好具有这些“正则”对称性。对于Cayley有向图也有类似的结果。然而，一个对称群是否可以用一个有向凯莱图（任何一对顶点之间至多有一条有向边）来正则表示是一个长期存在的问题。我和一位合著者最近解决了“不可解”对称群的这个问题。我们将尝试把我们的工作扩展到“可解”对称群。 4.将一个图描述为凯莱图提供了关于它的大量对称性的信息，但通常不是所有对称性。我将研究可以用多种方式表示为凯莱图的图。第二种表示法大大增强了我们理解这种图所展示的所有对称性的能力。 这些是解决凯莱图的识别和同构问题的步骤：代数图论中极其重要的开放问题。