Symmetries of Cayley Graphs

凯莱图的对称性

• 批准号: RGPIN-2017-04905
• 负责人: Morris, Joy
• 金额: $ 1.17万
• 依托单位: University of Lethbridge
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=675792
• 关键词: 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图的对称性。 “图形”是网络的模型，其“顶点”（点）表示节点或终端，而代表连接的边缘。 Cayley图是具有强对称性的图形：一个简单的例子是Pentagram（Star），它具有旋转和反射对称性。****** cayley图是有趣的组合对象，可以研究自己的缘故。它们还提供了一类图表，可以为这些图表提供强大的群体理论技术（摘要代数）来探索困难问题。有一种典型的方式来着色Cayley图的边缘，以便图形的最自然对称性保留此规范着色。我将探索只有最自然的对称性才能保留这种着色的情况，并且额外的对称性可以保留这种着色。对边色进行了大量研究，因为它们可用于表示图形不同边缘（例如容量）变化的属性。但是，大多数边缘色破坏了大多数对称性。 ****** 2。如果Cayley图具有“ Cayley同构属性”，则代数技术使我们能够确定另一个Cayley图是否本质上是同一网络，只是绘制的方式不同。对于有限图，这已经进行了很多研究。我将研究这个问题向无限图的扩展，这吸引了更少的关注。我还将努力扩展我的一些先前的结果，其中有限图具有此属性。****** 3。有时，Cayley图被允许具有定向边缘，代表网络中的单向连接；如果他们这样做，我们称它们为Digraphs。众所周知，（除了某些例外）任何“不错的”对称集合（对称组）通过Cayley图具有“常规”表示，这意味着有一个cayley图，上面有这些“常规”对称性。 Cayley Digraphs也有类似的结果。但是，是否可以通过定向的Cayley图定期表示对称组（任何对顶点之间的边缘最多）是一个长期的开放问题。我和我最近为“不可溶解”对称组解决了这个问题。我们将尝试将我们的工作扩展到“可解决的”对称组。****** 4。将图形描述为Cayley图提供了有关其大量对称性的信息，但通常并非全部。我将努力表征可以以多种方式表示为Cayley图形的图形。第二个表示形式显着增强了我们理解所有这些图表的对称性的能力。