Talk:Cayley graph

History[edit]

What is the history of the Cayley graph? Did Arthur Cayley have anything to do with it? How about some theorems that use the notion? --Dbenbenn 05:46, 11 Dec 2004 (UTC)

TeX vs inline math[edit]

Mathematics Manual of Style recommends that inline math be used for very simple formulas, and it's now almost a universal practice for mathematics articles. Here most sections are still written using latex markup (I preserved the style in the section that I've just edited), but it seems like an overkill and I propose to uniformly switch to inline. Arcfrk (talk) 01:49, 29 February 2008 (UTC)[reply]

Moved from the article (OR)[edit]

I've removed the following text from the article. I am unfamiliar with the use of the term "Bruhat order" outside of the context of Coxeter groups, and in any case, there is very little of value for the topic of Cayley graphs (saying "minimal path" is the same as "reduced word" is the same as "minimal path" is nonsensical). Arcfrk (talk) 23:30, 11 April 2009 (UTC)[reply]

Ordering[edit]

The Cayley graph is a based graph, and determines two partial order, called the weak order and the Bruhat order. These are especially used for Coxeter groups. The associated metric is the word metric, and the norm is called a length function. Indeed, the word length makes it into a graded poset.

(Note that the relation given by walks on the graph does not in general give a partial order, since if the group has torsion (elements of finite order), this graph is not acyclic, hence the relation is not antisymmetric.)

Path from the origin to g correspond to words in the generators that equal g (paths from g to h correspond to paths from e to $g^{-1}h$ , hence to words for $g^{-1}h$ ), and minimal paths correspond to reduced words: the length of an element is the length of a shortest path or, equivalently, reduced word.

Then $g\leq h$ in the Bruhat order if a reduced word for g is contained in a reduced word for h, while $g\leq h$ in the weak order if a reduced word for g is contained as a prefix in a reduced word for h.

Geometrically, h exceeds g in the weak order if there is a minimal length path from e to h that passes through g.

The corresponding Hasse diagram diagram (for the weak order) can be obtained from the Cayley graph by removing some edges: only edges connecting an element of length k to an element of length $k+1$ are retained (these edges form the transitive reduction of the weak order).

terminology of this page[edit]

There are several issues about this page from the point of view of algebraic graph theory.

The definition produces a graph with coloured edges, but in algebraic graph theory the edges are almost always left uncoloured unless the name "Cayley colour graph" is used (which is rare). This convention can be seen also on this page with the theorem "A graph Γ is a Cayley graph of a group G if and only if it admits a simply transitive action of G by graph automorphisms." If the definition on this page was applied rigorously, Γ would need to be edge-coloured in a particular way before this theorem is true. However, the uncoloured version is true and less trivial.
The page requires Cayley graphs to be connected, but in algebraic graph theory the disconnected case is usually allowed too.

Suggestions for fixing this are solicited. McKay (talk) 07:58, 9 May 2009 (UTC)[reply]

So in the disconnected case, one has a group and a set of group elements that is not necessarily a generating set? Or a groupoid and a generating set for it? —David Eppstein (talk) 15:30, 9 May 2009 (UTC)[reply]

The former. For the directed case, a group G and a set of elements S of the group. In the undirected case, S must also be closed under inverse. In both cases, many authors disallow the identity element from being in S. Excluding the case where S doesn't generate G causes more graph-theoretic trouble than it's worth, for example it means that the complement of a Cayley graph may or may not be a Cayley graph, the tensor (direct) product of two Cayley graphs may or may not be a Cayley graph, etc. McKay (talk) 03:07, 10 May 2009 (UTC)[reply]

Quick survey of handbook-type sources with combinatorial bias:

Encyclopaedia of Mathematics, supp vol 3, p96: no edge colours, not necessarily connected, no loops
CRC concise encyclopedia of mathematics, p360: no edge colours, connected
Handbook of graph theory, p505: no edge colours, not necessarily connected, no loops
Handbook of discrete and combinatorial mathematics, p589: no edge colours, connected
Concise Encyclopedia of Supersymmetry, p84: no edge colours, not necessarily connected
Handbook of algebraic topology, p929: no edge colours, not necessarily connected
Handbook of computational group theory, p18: edge colours, connected

I propose:

Edge colours be treated only as an option and not as the starting definition
Connectivity be treated from the start as a point on which there is common disagreement between sources.

McKay (talk) 03:43, 10 May 2009 (UTC)[reply]

No objections from me. —David Eppstein (talk) 04:17, 10 May 2009 (UTC)[reply]

Word Problem[edit]

When reading this article, I was somewhat surprised to see that although Cayley graphs are referred to as begin "a central tool in combinatorial and geometric group theory", no reference is made to the association with the Word Problem, one of the central problems in these areas! So I have added in a quick line about this in what I deemed to be a somewhat appropriate part of the article. I appologise for the sloppy editing, it is the first time I have referenced something on here!

I have also added a few alternative names for the Cayley graph which have been used in the literature (for instance, color group was used by both Cayley and Burnside). —Preceding unsigned comment added by 130.209.6.40 (talk) 09:42, 22 April 2010 (UTC)[reply]

Too much 'discretion'[edit]

The article right now (17:47, 19 October 2010 (UTC)) explicitly defines Cayley graphs for discrete groups; but if I do not miss something subtle, no explicit reference to the topological properties is made, and nor is any comparison or reference made to any kind of extension of the concept to groups equipped with more general topologies. My impression is that "discrete" just is a kind of substitute for "in most examples, finitely generated; and often finite". Of course, the discrete topology is the trivial one, and thus, if you don't employ the topology, "a group with a discrete topology" is synonymous with the simpler "a group".

The reason this bothers me, is that it does cause confusion. Recently, there was a math reference desk question Wikipedia:Reference_desk/Archives/Mathematics/2010_October_15#could_you_explain_cayley_graph, asking for a simpler explanation than our article; and the first answer began like this:

The trouble is that a simplified explanation will lack formal mathematical rigor, and these are complicated and subtle concepts. A Cayley graph is a representation of a discrete group. This is a concept that requires subtle understanding of continuity and discreteness (as well as formal definitions of graphs and groups).

Now, it would be rather hard to understand the definition of a Cayley graph for a student who does not have a good grasp of elementary ("naive") set theory. Just "understanding" graphs and groups by means of familiarising yourself with some examples (which is what school pupils often do, in lieu of assimilating formal definitions), is hardly enough in this case. This indeed may make the Cayley graphs a bit hard to digest for eight graders (even bright ones). However, there is no need whatsoever to learn about topology in general or topological groups in particular, in order to grasp the definition; and certainly no need to learn the differences between e.g. discreteness and connectedness for Hausdorff spaces, for a first understanding of Cayley graphs.

IMHO, the formulation "discrete group" thus is fooling not just eighth graders, but also reference desk answererers, getting them to believe that the concept is more complicated than it is. I'll remove it, and suggest that if it is reinstated the information that the group may be viewed as having the trivial topology is postponed until it is employed (if it is). JoergenB (talk) 17:47, 19 October 2010 (UTC)[reply]

Order of compositions[edit]

The order of compositions of isometries in the Cayley graph of dihedral group (with generators a,b) is wrong on the picture. For example, element ab should be symmetry first, then rotation and letter F near ab should be interchanged with letter F near a^3b. Similarly on the other diagonal. 95.40.141.15 (talk) 19:10, 21 February 2011 (UTC)[reply]

ab stands for "clockwise 90° rotation, than horizontal reflection",
a³b stands for "clockwise 270° rotation, than horizontal reflection".

For the case, that you want to call ba what is now called ab, etc.:
As the Cayley table on the right illustrates, group elements can be represented by permutations and thus by permutation matrices. You may check in the Cayley table, that p1 * p2 = p4 and p2 * p1 = p3. When ab wouldn't stand for "doing a, than doing b", it wouldn't correspond with matrix multiplication. We can also define Dih4 with permutations - and a * b with the group elements a and b and * denoting the group operation should correspond to a * b with the permutation matrices a and b and * denoting matrix multiplication.
Watchduck (talk) 09:03, 23 February 2011 (UTC)[reply]

Thank you for your reply, but I still don't understand.

From the Cayley table of S_3 that you quoted we can read that (23) (12) = (132) (where (23) is element from third row, (12) is element from second column). If you composed these permutations from left to right, then first would interchange 2 to 3 and second would do nothing, and the result would be (123) permutation.

The usual matrix multiplication represents usual composition of linear transformations and these are composed from right to left.

Also, this is a quote from the page about dihedral groups:

"For example, S2S1 = R1 because the reflection S1 followed by the reflection S2 results in a 120-degree rotation. (This is the normal backwards order for composition.)"

(see also a picture in this article)

Best regards, 95.41.221.51 (talk) 05:45, 24 February 2011 (UTC)[reply]

You are right. The article function composition states, that (g∘f)(x) = g(f(x)) is the correct interpretation. It's just mentioned that

In the mid-20th century, some mathematicians decided that writing "g∘f" to mean "first apply f, then apply g" was too confusing and decided to change notations.

It's indeed confusing. The German article states, that the other interpretation is also possible. However - I will change the graphics above, and use the "g after f" notation.

What I wrote about matrix multiplication of permutation matrices makes sense, when the permutation's tuple representation is a row vector - and almost always the permuted elements are written horizontally. Only when column vectors are permuted, g after f and g times f go hand in hand. Sadly we have conflicting conventiones here. Greetings, Watchduck (talk) 18:55, 24 February 2011 (UTC)[reply]

Clash of conventions in definition and example[edit]

The definition of the Cayley graph in the Definition section says that we have an edge going from 'g' to 'gs', labeled 's'; so that the edge represents multiplication on the right by the element labeling the edge. However, the fourth example and the attached graph use the opposite convention, by using a red arrow associated to 'a' to connect 'x' with 'ax'. The text correctly states that the arrow represents multiplication by 'a' on the left (rather than the right), but it is perhaps somewhat confusing to have this change of convention without any "announcement." Perhaps one might add somewhere along the line that one can likewise define the graph using left multiplication instead of right, or to modify the image/description to avoid the issue. Magidin (talk) 22:22, 19 May 2012 (UTC)[reply]

That is correct, and I have changed it. Five years ago, in the discussion above, the IP has convinced my to change it to prefix notation - but that seems to be unusual in Cayley graphs. There was a Stackexchange discussion BTW, whether or not the prefix notation was wrong: http://math.stackexchange.com/questions/146923/is-the-cayley-diagram-for-d4-in-wikimedia-commons-wrong --Watchduck (quack) 00:54, 28 November 2016 (UTC)[reply]

Why does "Cayley diagram" redirect to Cognate_linkage rather than here?[edit]

77.126.182.100 (talk) 11:36, 2 November 2012 (UTC)[reply]

wrong definition of cayley graph[edit]

"Suppose that G=\mathbb{Z} \! is the infinite cyclic group and the set S consists of the standard generator 1 and its inverse (−1 in the additive notation) then the Cayley graph is an infinite chain." no it isn't!!! between n and n+1 there are TWO edges, non one!--93.66.195.134 (talk) 12:26, 5 April 2013 (UTC)[reply]

Reference dead link[edit]

The reference to the connectivity of the graph (Babai's Technical Report TR-94-10) is a dead link. — Preceding unsigned comment added by 180.48.56.132 (talk) 09:48, 15 March 2015 (UTC)[reply]

Fixed (replaced by published version). —David Eppstein (talk) 18:00, 15 March 2015 (UTC)[reply]

Elementary properties[edit]

This is a poor heading for a jumbled collection of properties, conventions and theorems; some of which are anything but elementary, because they assume a knowledgeable reader. yoyo (talk) 16:22, 13 December 2018 (UTC)[reply]

Expansion[edit]

I reworked the recently added section on expanding Cayley graphs, which contained some wrong statements, most notably about the relation between property (T) and expansion. Prperyy (T) is not equivalent to expansion of the Cayley graphs, for example free groups have an expanding Cayley graph but are not Kazhdan. It is not even equivalent to uniform expansion of all quotients since this condition holds for the non-Kazhdan group SL_2(Z[sqrt 2]). The example of abelian groups is not relevant for an article of which expansion is not the primary topic so i removed it. jraimbau (talk) 13:27, 19 November 2021 (UTC)[reply]