Eigenvalues of the Laplacian of the directed De Bruijn graph Planned maintenance scheduled...



Eigenvalues of the Laplacian of the directed De Bruijn graph



Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30 pm US/Eastern)
Announcing the arrival of Valued Associate #679: Cesar Manara
Unicorn Meta Zoo #1: Why another podcast?Does graph asymmetry imply all eigenvalues of the graph Laplacian are simple?Can the friendship graph be determind by its adjacency spectrum?Extreme Laplacian eigenvaluesConnection between eigenvalues of matrix and its Laplacian.Spectral Graph TheoryWhen does the normalized graph Laplacian have eigenvalue 1?Hashimoto Matrix (Non-backtracking operator) and the Graph LaplacianDirected graph Laplacian with exactly one negative eigenvalueSpectra of undirected $d$-regular graphsLocal-Global Principle in Graph Spectrum












5












$begingroup$


We will denote by $DB(n,k)$ the directed De Bruijn graph, which is a digraph whose vertices are elements of ${0,1,dots,k-1}^n$, and $sigma_1cdots sigma_n$ is connected to $tau_1cdots tau_{n}$ if and only if $sigma_i=tau_{i+1}$ for every $i=1,dots,n-1$.



We would like to calculate the spectrum of the Laplacian matrix of $DB(n,k)$. Note that since $DB(n,k)$ is $k$-regular, then $lambda in Spec(L_{DB(n,k)})$ if and only if $k-lambda in Spec(A_{DB(n,k)})$, so we can calculate the eigenvalues of the Laplacian matrix from the eigenvalues of the Adjacency matrix.



We found the following article on the subject, but it only calculates the spectrum of the underlining undirected graph of the De Bruijn graph:



https://core.ac.uk/download/pdf/82810454.pdf



Thanks!






co.combinatorics graph-theory spectral-graph-theory enumerative-combinatorics







share|cite|improve this question











$endgroup$

















    5












    $begingroup$


    We will denote by $DB(n,k)$ the directed De Bruijn graph, which is a digraph whose vertices are elements of ${0,1,dots,k-1}^n$, and $sigma_1cdots sigma_n$ is connected to $tau_1cdots tau_{n}$ if and only if $sigma_i=tau_{i+1}$ for every $i=1,dots,n-1$.



    We would like to calculate the spectrum of the Laplacian matrix of $DB(n,k)$. Note that since $DB(n,k)$ is $k$-regular, then $lambda in Spec(L_{DB(n,k)})$ if and only if $k-lambda in Spec(A_{DB(n,k)})$, so we can calculate the eigenvalues of the Laplacian matrix from the eigenvalues of the Adjacency matrix.



    We found the following article on the subject, but it only calculates the spectrum of the underlining undirected graph of the De Bruijn graph:



    https://core.ac.uk/download/pdf/82810454.pdf



    Thanks!






    co.combinatorics graph-theory spectral-graph-theory enumerative-combinatorics







    share|cite|improve this question











    $endgroup$















      5












      5








      5





      $begingroup$


      We will denote by $DB(n,k)$ the directed De Bruijn graph, which is a digraph whose vertices are elements of ${0,1,dots,k-1}^n$, and $sigma_1cdots sigma_n$ is connected to $tau_1cdots tau_{n}$ if and only if $sigma_i=tau_{i+1}$ for every $i=1,dots,n-1$.



      We would like to calculate the spectrum of the Laplacian matrix of $DB(n,k)$. Note that since $DB(n,k)$ is $k$-regular, then $lambda in Spec(L_{DB(n,k)})$ if and only if $k-lambda in Spec(A_{DB(n,k)})$, so we can calculate the eigenvalues of the Laplacian matrix from the eigenvalues of the Adjacency matrix.



      We found the following article on the subject, but it only calculates the spectrum of the underlining undirected graph of the De Bruijn graph:



      https://core.ac.uk/download/pdf/82810454.pdf



      Thanks!






      co.combinatorics graph-theory spectral-graph-theory enumerative-combinatorics







      share|cite|improve this question











      $endgroup$




      We will denote by $DB(n,k)$ the directed De Bruijn graph, which is a digraph whose vertices are elements of ${0,1,dots,k-1}^n$, and $sigma_1cdots sigma_n$ is connected to $tau_1cdots tau_{n}$ if and only if $sigma_i=tau_{i+1}$ for every $i=1,dots,n-1$.



      We would like to calculate the spectrum of the Laplacian matrix of $DB(n,k)$. Note that since $DB(n,k)$ is $k$-regular, then $lambda in Spec(L_{DB(n,k)})$ if and only if $k-lambda in Spec(A_{DB(n,k)})$, so we can calculate the eigenvalues of the Laplacian matrix from the eigenvalues of the Adjacency matrix.



      We found the following article on the subject, but it only calculates the spectrum of the underlining undirected graph of the De Bruijn graph:



      https://core.ac.uk/download/pdf/82810454.pdf



      Thanks!






      co.combinatorics graph-theory spectral-graph-theory enumerative-combinatorics




      co.combinatorics graph-theory spectral-graph-theory enumerative-combinatorics






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited 4 hours ago









      Fedor Petrov

      52.5k6123241




      52.5k6123241










      asked 5 hours ago









      Serge the ToasterSerge the Toaster

      592




      592






















          2 Answers
          2






          active

          oldest

          votes


















          3












          $begingroup$

          The computation for $k=2$ appears (among other places) on pp. 158--159 of my book Algebraic Combinatorics, second edition. The computation for arbitrary $k$ is completely analogous. Dima Pasechnik is correct that there is one eigenvalue equal to 0, and all the others are equal to $k$.






          share|cite|improve this answer









          $endgroup$





















            2












            $begingroup$

            I believe that for $p$ prime $DB(m,p)$ has one 0 eigenvalue (this is easy to check), and the other eigenvalues are all equal to $p$. This is something that we observed while working on https://arxiv.org/abs/1405.0113, but didn't try to prove (should not be too hard I guess, using a decription of $DB(m,p)$ as the line graph of $DB(m-1,p)$, and then induction).






            share|cite|improve this answer











            $endgroup$














              Your Answer








              StackExchange.ready(function() {
              var channelOptions = {
              tags: "".split(" "),
              id: "504"
              };
              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%2fmathoverflow.net%2fquestions%2f328770%2feigenvalues-of-the-laplacian-of-the-directed-de-bruijn-graph%23new-answer', 'question_page');
              }
              );

              Post as a guest















              Required, but never shown

























              2 Answers
              2






              active

              oldest

              votes








              2 Answers
              2






              active

              oldest

              votes









              active

              oldest

              votes






              active

              oldest

              votes









              3












              $begingroup$

              The computation for $k=2$ appears (among other places) on pp. 158--159 of my book Algebraic Combinatorics, second edition. The computation for arbitrary $k$ is completely analogous. Dima Pasechnik is correct that there is one eigenvalue equal to 0, and all the others are equal to $k$.






              share|cite|improve this answer









              $endgroup$


















                3












                $begingroup$

                The computation for $k=2$ appears (among other places) on pp. 158--159 of my book Algebraic Combinatorics, second edition. The computation for arbitrary $k$ is completely analogous. Dima Pasechnik is correct that there is one eigenvalue equal to 0, and all the others are equal to $k$.






                share|cite|improve this answer









                $endgroup$
















                  3












                  3








                  3





                  $begingroup$

                  The computation for $k=2$ appears (among other places) on pp. 158--159 of my book Algebraic Combinatorics, second edition. The computation for arbitrary $k$ is completely analogous. Dima Pasechnik is correct that there is one eigenvalue equal to 0, and all the others are equal to $k$.






                  share|cite|improve this answer









                  $endgroup$



                  The computation for $k=2$ appears (among other places) on pp. 158--159 of my book Algebraic Combinatorics, second edition. The computation for arbitrary $k$ is completely analogous. Dima Pasechnik is correct that there is one eigenvalue equal to 0, and all the others are equal to $k$.







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered 2 hours ago









                  Richard StanleyRichard Stanley

                  29.4k9118191




                  29.4k9118191























                      2












                      $begingroup$

                      I believe that for $p$ prime $DB(m,p)$ has one 0 eigenvalue (this is easy to check), and the other eigenvalues are all equal to $p$. This is something that we observed while working on https://arxiv.org/abs/1405.0113, but didn't try to prove (should not be too hard I guess, using a decription of $DB(m,p)$ as the line graph of $DB(m-1,p)$, and then induction).






                      share|cite|improve this answer











                      $endgroup$


















                        2












                        $begingroup$

                        I believe that for $p$ prime $DB(m,p)$ has one 0 eigenvalue (this is easy to check), and the other eigenvalues are all equal to $p$. This is something that we observed while working on https://arxiv.org/abs/1405.0113, but didn't try to prove (should not be too hard I guess, using a decription of $DB(m,p)$ as the line graph of $DB(m-1,p)$, and then induction).






                        share|cite|improve this answer











                        $endgroup$
















                          2












                          2








                          2





                          $begingroup$

                          I believe that for $p$ prime $DB(m,p)$ has one 0 eigenvalue (this is easy to check), and the other eigenvalues are all equal to $p$. This is something that we observed while working on https://arxiv.org/abs/1405.0113, but didn't try to prove (should not be too hard I guess, using a decription of $DB(m,p)$ as the line graph of $DB(m-1,p)$, and then induction).






                          share|cite|improve this answer











                          $endgroup$



                          I believe that for $p$ prime $DB(m,p)$ has one 0 eigenvalue (this is easy to check), and the other eigenvalues are all equal to $p$. This is something that we observed while working on https://arxiv.org/abs/1405.0113, but didn't try to prove (should not be too hard I guess, using a decription of $DB(m,p)$ as the line graph of $DB(m-1,p)$, and then induction).







                          share|cite|improve this answer














                          share|cite|improve this answer



                          share|cite|improve this answer








                          edited 4 hours ago

























                          answered 5 hours ago









                          Dima PasechnikDima Pasechnik

                          9,44311952




                          9,44311952






























                              draft saved

                              draft discarded




















































                              Thanks for contributing an answer to MathOverflow!


                              • 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.




                              draft saved


                              draft discarded














                              StackExchange.ready(
                              function () {
                              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f328770%2feigenvalues-of-the-laplacian-of-the-directed-de-bruijn-graph%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

                              El tren de la libertad Índice Antecedentes "Porque yo decido" Desarrollo de la...

                              Image
                              Feminismo en EspañaAborto en EspañaManifestaciones y protestas en EspañaManifestaciones y protestas en 2014España en 2014Historia de las mujeres en España movimiento socialfeministaderechos sexuales y reproductivosmujeresLey del aborto en España1 de febrero2014MadridAlberto Ruíz Gallardónla ley del aborto vigente del 2010AsturiasTertulia Feminista Les ComadresCongreso de DiputadosAlicia MiyaresAna MatoAlberto Ruiz GallardónEdimburgoRomaParísLuxemburgoBuenos AiresGracia QuerejetaÁngeles González-SindeMabel LozanoIcíar BollaínIsabel CoixetGeorgina CisquellaTeresa FontVirginia Yagüe2010José Luis Rodríguez ZapateroCongreso de Diputados19 de diciembre20095 de julio2010Partido PopularTribunal Constitucional201120 de diciembre2013Partido PopularMariano RajoyGijónTertulia Feminista Les ComadresBegoña PiñeroRenfeAlicia MiyaresTertulia Feminista Les Comadres1 de febrero2014Congreso de DiputadosMariano RajoyAlberto Ruiz GallardónAna MatoAsturiasAndalucíaCanariasCataluñaComunidad ValencianaCasti...
                              Read more

                              Castillo d'Acher Características Menú de navegación

                              Image
                              Montañas de los Pirineos de AragónMontañas de la provincia de Huesca msnmSelva de OzaPirineo aragonésEspañabosque Este artículo o sección necesita referencias que aparezcan en una publicación acreditada. Este aviso fue puesto el 11 de agosto de 2011. El pico desde Selva de Oza. El Castillo d' Acher es una cima de 2.384msnm en la zona de la Selva de Oza en la parte occidental del Pirineo aragonés, en España. Debe su nombre a su aspecto de fortaleza que presenta hacia todas sus vertientes. Características En orden ascendente, la cima pasa de un bosque frondoso de tonalidades verde-amarillenta a laderas rojizas. Su cima, que suele presentarse mucha nieve, es un pequeño valle rectangular rodeado en sus cuatro caras por una muralla que le da un aspecto de fortaleza. This page is only for reference, If you need detailed information, please check here
                              Read more

                              Connecting two nodes from the same mother node horizontallyTikZ: What EXACTLY does the the |- notation for...

                              Image
                              Pigeonhole Principle Problem Was Hulk present at this event? Attending a conference where my ex-supervisor and his collaborator are present, should I attend? How did Arya manage to disguise herself? What is the word which sounds like "shtrass"? Does higher resolution in an image imply more bits per pixel? What was the state of the German rail system in 1944? Packet sniffer for MacOS Mojave and above Pressure to defend the relevance of one's area of mathematics Why are there synthetic chemicals in our bodies? Where do they come from? Does the Darkness spell dispel the Color Spray ...
                              Read more