Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group, is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cayley), and uses a specified set of generators for the group. It is a central tool in combinatorial and geometric group theory. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing families of expander graphs. Let be a group and be a generating set of . The Cayley graph is an edge-colored directed graph constructed as follows: Each element of is assigned a vertex: the vertex set of is identified with Each element of is assigned a color . For every and , there is a directed edge of color from the vertex corresponding to to the one corresponding to . Not every source requires that generate the group. If is not a generating set for , then is disconnected and each connected component represents a coset of the subgroup generated by . If an element of is its own inverse, then it is typically represented by an undirected edge. The set is sometimes assumed to be symmetric (i.e. ) and not containing the identity element of the group. In this case, the uncolored Cayley graph can be represented as a simple undirected graph. In geometric group theory, the set is often assumed to be finite which corresponds to being locally finite. Suppose that is the infinite cyclic group and the set consists of the standard generator 1 and its inverse (−1 in the additive notation); then the Cayley graph is an infinite path. Similarly, if is the finite cyclic group of order and the set consists of two elements, the standard generator of and its inverse, then the Cayley graph is the cycle . More generally, the Cayley graphs of finite cyclic groups are exactly the circulant graphs. The Cayley graph of the direct product of groups (with the cartesian product of generating sets as a generating set) is the cartesian product of the corresponding Cayley graphs.
Andreas Peter Burg, Alexios Konstantinos Balatsoukas Stimming, Andreas Toftegaard Kristensen, Yifei Shen, Yuqing Ren, Leyu Zhang, Chuan Zhang
Pierre Vandergheynst, Felix Naef, Cédric Gobet, Francesco Craighero, Mohan Vamsi Nallapareddy