Are Cayley Graphs weakly or strongly connected?












1














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?










share|cite|improve this question



























    1














    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?










    share|cite|improve this question

























      1












      1








      1


      1





      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?










      share|cite|improve this question













      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






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Dec 28 '18 at 14:47









      JayJay

      61




      61






















          1 Answer
          1






          active

          oldest

          votes


















          1














          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.






          share|cite|improve this answer

















          • 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













          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
          });


          }
          });














          draft saved

          draft discarded


















          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









          1














          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.






          share|cite|improve this answer

















          • 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


















          1














          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.






          share|cite|improve this answer

















          • 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
















          1












          1








          1






          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.






          share|cite|improve this answer












          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.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          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
















          • 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




















          draft saved

          draft discarded




















































          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.




          draft saved


          draft discarded














          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





















































          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







          Popular posts from this blog

          Human spaceflight

          Can not write log (Is /dev/pts mounted?) - openpty in Ubuntu-on-Windows?

          張江高科駅