Are Cayley Graphs weakly or strongly connected?
I'm working my way through Meier's Groups, Graphs and Trees and I'm confused by the proof he gives for one of Cayley's Theorems, namely
Every finitely generated group can be represented as a symmetry group of a
connected, directed, locally finite graph.
The proof basically begins by constructing something very similar to Cayley graph, then when it comes to proving connectedness it seems to me that the directedness of the graphs is just brushed over without consideration. So are Cayley graphs weakly connected, in the sense that they are connected only when we ignore direction, or are they strongly connected?
group-theory graph-theory algebraic-graph-theory cayley-graphs
asked Dec 28 '18 at 14:47
JayJay
61
add a comment |
I'm working my way through Meier's Groups, Graphs and Trees and I'm confused by the proof he gives for one of Cayley's Theorems, namely
Every finitely generated group can be represented as a symmetry group of a
connected, directed, locally finite graph.
The proof basically begins by constructing something very similar to Cayley graph, then when it comes to proving connectedness it seems to me that the directedness of the graphs is just brushed over without consideration. So are Cayley graphs weakly connected, in the sense that they are connected only when we ignore direction, or are they strongly connected?
group-theory graph-theory algebraic-graph-theory cayley-graphs
asked Dec 28 '18 at 14:47
JayJay
61
add a comment |
I'm working my way through Meier's Groups, Graphs and Trees and I'm confused by the proof he gives for one of Cayley's Theorems, namely
Every finitely generated group can be represented as a symmetry group of a
connected, directed, locally finite graph.
The proof basically begins by constructing something very similar to Cayley graph, then when it comes to proving connectedness it seems to me that the directedness of the graphs is just brushed over without consideration. So are Cayley graphs weakly connected, in the sense that they are connected only when we ignore direction, or are they strongly connected?
group-theory graph-theory algebraic-graph-theory cayley-graphs
asked Dec 28 '18 at 14:47
JayJay
61
I'm working my way through Meier's Groups, Graphs and Trees and I'm confused by the proof he gives for one of Cayley's Theorems, namely
Every finitely generated group can be represented as a symmetry group of a
connected, directed, locally finite graph.
The proof basically begins by constructing something very similar to Cayley graph, then when it comes to proving connectedness it seems to me that the directedness of the graphs is just brushed over without consideration. So are Cayley graphs weakly connected, in the sense that they are connected only when we ignore direction, or are they strongly connected?
group-theory graph-theory algebraic-graph-theory cayley-graphs
group-theory graph-theory algebraic-graph-theory cayley-graphs
asked Dec 28 '18 at 14:47
JayJay
61
asked Dec 28 '18 at 14:47
JayJay
61
asked Dec 28 '18 at 14:47
JayJay
61
asked Dec 28 '18 at 14:47
JayJay
61
asked Dec 28 '18 at 14:47
JayJay
61
61
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
If your generators are finite order, then Cayley graphs are composed of cycles, so are strongly connected. If not, then indeed, they are only weakly connected: for example, in the Cayley graph of the free group on $n$ generators with respect to those free generators, there is no path to the vertex corresponding to the identity from the vertex corresponding to any one of those generators.
answered Dec 28 '18 at 14:55
user3482749user3482749
2,798414
2
That depends on your definition of the Cayley graph. If $a$ is a generator, then there is a path labelled $a^{-1}$ from the vertex labelled $a$ to the base point.
– Derek Holt
Dec 28 '18 at 16:01
1
Not by any definition that I've ever seen. $a^{-1}$ is not in our generating set, so we do not label edges by it. Certainly also not by the definition in use in the question, as allowing that makes the Cayley Graph (up to replacing each pair of directed edges running between the same vertices in opposite directions with an undirected edge) an undirected graph, which makes the question trivial.
– user3482749
Dec 28 '18 at 16:13
In the context of the proof from Meier's book, the vertex set of the graph is the elements of $langle S rangle = G$ and the edge set is defined by $(g,gs)$ (an ordered pair) for $g in G$ and $s in S$
– Jay
Dec 28 '18 at 17:06
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3054958%2fare-cayley-graphs-weakly-or-strongly-connected%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
If your generators are finite order, then Cayley graphs are composed of cycles, so are strongly connected. If not, then indeed, they are only weakly connected: for example, in the Cayley graph of the free group on $n$ generators with respect to those free generators, there is no path to the vertex corresponding to the identity from the vertex corresponding to any one of those generators.
answered Dec 28 '18 at 14:55
user3482749user3482749
2,798414
2
That depends on your definition of the Cayley graph. If $a$ is a generator, then there is a path labelled $a^{-1}$ from the vertex labelled $a$ to the base point.
– Derek Holt
Dec 28 '18 at 16:01
1
Not by any definition that I've ever seen. $a^{-1}$ is not in our generating set, so we do not label edges by it. Certainly also not by the definition in use in the question, as allowing that makes the Cayley Graph (up to replacing each pair of directed edges running between the same vertices in opposite directions with an undirected edge) an undirected graph, which makes the question trivial.
– user3482749
Dec 28 '18 at 16:13
In the context of the proof from Meier's book, the vertex set of the graph is the elements of $langle S rangle = G$ and the edge set is defined by $(g,gs)$ (an ordered pair) for $g in G$ and $s in S$
– Jay
Dec 28 '18 at 17:06
add a comment |
If your generators are finite order, then Cayley graphs are composed of cycles, so are strongly connected. If not, then indeed, they are only weakly connected: for example, in the Cayley graph of the free group on $n$ generators with respect to those free generators, there is no path to the vertex corresponding to the identity from the vertex corresponding to any one of those generators.
answered Dec 28 '18 at 14:55
user3482749user3482749
2,798414
2
That depends on your definition of the Cayley graph. If $a$ is a generator, then there is a path labelled $a^{-1}$ from the vertex labelled $a$ to the base point.
– Derek Holt
Dec 28 '18 at 16:01
1
Not by any definition that I've ever seen. $a^{-1}$ is not in our generating set, so we do not label edges by it. Certainly also not by the definition in use in the question, as allowing that makes the Cayley Graph (up to replacing each pair of directed edges running between the same vertices in opposite directions with an undirected edge) an undirected graph, which makes the question trivial.
– user3482749
Dec 28 '18 at 16:13
In the context of the proof from Meier's book, the vertex set of the graph is the elements of $langle S rangle = G$ and the edge set is defined by $(g,gs)$ (an ordered pair) for $g in G$ and $s in S$
– Jay
Dec 28 '18 at 17:06
add a comment |
If your generators are finite order, then Cayley graphs are composed of cycles, so are strongly connected. If not, then indeed, they are only weakly connected: for example, in the Cayley graph of the free group on $n$ generators with respect to those free generators, there is no path to the vertex corresponding to the identity from the vertex corresponding to any one of those generators.
answered Dec 28 '18 at 14:55
user3482749user3482749
2,798414
If your generators are finite order, then Cayley graphs are composed of cycles, so are strongly connected. If not, then indeed, they are only weakly connected: for example, in the Cayley graph of the free group on $n$ generators with respect to those free generators, there is no path to the vertex corresponding to the identity from the vertex corresponding to any one of those generators.
answered Dec 28 '18 at 14:55
user3482749user3482749
2,798414
answered Dec 28 '18 at 14:55
user3482749user3482749
2,798414
answered Dec 28 '18 at 14:55
user3482749user3482749
2,798414
answered Dec 28 '18 at 14:55
user3482749user3482749
2,798414
2,798414
2
That depends on your definition of the Cayley graph. If $a$ is a generator, then there is a path labelled $a^{-1}$ from the vertex labelled $a$ to the base point.
– Derek Holt
Dec 28 '18 at 16:01
1
Not by any definition that I've ever seen. $a^{-1}$ is not in our generating set, so we do not label edges by it. Certainly also not by the definition in use in the question, as allowing that makes the Cayley Graph (up to replacing each pair of directed edges running between the same vertices in opposite directions with an undirected edge) an undirected graph, which makes the question trivial.
– user3482749
Dec 28 '18 at 16:13
In the context of the proof from Meier's book, the vertex set of the graph is the elements of $langle S rangle = G$ and the edge set is defined by $(g,gs)$ (an ordered pair) for $g in G$ and $s in S$
– Jay
Dec 28 '18 at 17:06
add a comment |
2
That depends on your definition of the Cayley graph. If $a$ is a generator, then there is a path labelled $a^{-1}$ from the vertex labelled $a$ to the base point.
– Derek Holt
Dec 28 '18 at 16:01
1
Not by any definition that I've ever seen. $a^{-1}$ is not in our generating set, so we do not label edges by it. Certainly also not by the definition in use in the question, as allowing that makes the Cayley Graph (up to replacing each pair of directed edges running between the same vertices in opposite directions with an undirected edge) an undirected graph, which makes the question trivial.
– user3482749
Dec 28 '18 at 16:13
In the context of the proof from Meier's book, the vertex set of the graph is the elements of $langle S rangle = G$ and the edge set is defined by $(g,gs)$ (an ordered pair) for $g in G$ and $s in S$
– Jay
Dec 28 '18 at 17:06
2
2
That depends on your definition of the Cayley graph. If $a$ is a generator, then there is a path labelled $a^{-1}$ from the vertex labelled $a$ to the base point.
– Derek Holt
Dec 28 '18 at 16:01
That depends on your definition of the Cayley graph. If $a$ is a generator, then there is a path labelled $a^{-1}$ from the vertex labelled $a$ to the base point.
– Derek Holt
Dec 28 '18 at 16:01
1
1
Not by any definition that I've ever seen. $a^{-1}$ is not in our generating set, so we do not label edges by it. Certainly also not by the definition in use in the question, as allowing that makes the Cayley Graph (up to replacing each pair of directed edges running between the same vertices in opposite directions with an undirected edge) an undirected graph, which makes the question trivial.
– user3482749
Dec 28 '18 at 16:13
Not by any definition that I've ever seen. $a^{-1}$ is not in our generating set, so we do not label edges by it. Certainly also not by the definition in use in the question, as allowing that makes the Cayley Graph (up to replacing each pair of directed edges running between the same vertices in opposite directions with an undirected edge) an undirected graph, which makes the question trivial.
– user3482749
Dec 28 '18 at 16:13
In the context of the proof from Meier's book, the vertex set of the graph is the elements of $langle S rangle = G$ and the edge set is defined by $(g,gs)$ (an ordered pair) for $g in G$ and $s in S$
– Jay
Dec 28 '18 at 17:06
In the context of the proof from Meier's book, the vertex set of the graph is the elements of $langle S rangle = G$ and the edge set is defined by $(g,gs)$ (an ordered pair) for $g in G$ and $s in S$
– Jay
Dec 28 '18 at 17:06
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3054958%2fare-cayley-graphs-weakly-or-strongly-connected%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
