Eigenvalues of the Laplacian of the directed De Bruijn graphDoes 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
Eigenvalues of the Laplacian of the directed De Bruijn graph
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
$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
edited Apr 23 at 17:50
Fedor Petrov
52.5k6123241
asked Apr 23 at 16:58
Serge the ToasterSerge the Toaster
592
$endgroup$
add a comment |
$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
edited Apr 23 at 17:50
Fedor Petrov
52.5k6123241
asked Apr 23 at 16:58
Serge the ToasterSerge the Toaster
592
$endgroup$
add a comment |
$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
edited Apr 23 at 17:50
Fedor Petrov
52.5k6123241
asked Apr 23 at 16:58
Serge the ToasterSerge the Toaster
592
$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
edited Apr 23 at 17:50
Fedor Petrov
52.5k6123241
asked Apr 23 at 16:58
Serge the ToasterSerge the Toaster
592
edited Apr 23 at 17:50
Fedor Petrov
52.5k6123241
asked Apr 23 at 16:58
Serge the ToasterSerge the Toaster
592
edited Apr 23 at 17:50
Fedor Petrov
52.5k6123241
edited Apr 23 at 17:50
Fedor Petrov
52.5k6123241
edited Apr 23 at 17:50
Fedor Petrov
52.5k6123241
52.5k6123241
asked Apr 23 at 16:58
Serge the ToasterSerge the Toaster
592
asked Apr 23 at 16:58
Serge the ToasterSerge the Toaster
592
asked Apr 23 at 16:58
Serge the ToasterSerge the Toaster
592
592
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$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).
answered Apr 23 at 17:36
Dima PasechnikDima Pasechnik
9,46311953
$endgroup$
add a comment |
$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$.
answered Apr 23 at 19:46
Richard StanleyRichard Stanley
29.4k9118191
$endgroup$
add a comment |
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
);
);
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%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
$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).
answered Apr 23 at 17:36
Dima PasechnikDima Pasechnik
9,46311953
$endgroup$
add a comment |
$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).
answered Apr 23 at 17:36
Dima PasechnikDima Pasechnik
9,46311953
$endgroup$
add a comment |
$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).
answered Apr 23 at 17:36
Dima PasechnikDima Pasechnik
9,46311953
$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).
answered Apr 23 at 17:36
Dima PasechnikDima Pasechnik
9,46311953
edited Apr 23 at 17:48
answered Apr 23 at 17:36
Dima PasechnikDima Pasechnik
9,46311953
answered Apr 23 at 17:36
Dima PasechnikDima Pasechnik
9,46311953
answered Apr 23 at 17:36
Dima PasechnikDima Pasechnik
9,46311953
9,46311953
add a comment |
add a comment |
$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$.
answered Apr 23 at 19:46
Richard StanleyRichard Stanley
29.4k9118191
$endgroup$
add a comment |
$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$.
answered Apr 23 at 19:46
Richard StanleyRichard Stanley
29.4k9118191
$endgroup$
add a comment |
$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$.
answered Apr 23 at 19:46
Richard StanleyRichard Stanley
29.4k9118191
$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$.
answered Apr 23 at 19:46
Richard StanleyRichard Stanley
29.4k9118191
answered Apr 23 at 19:46
Richard StanleyRichard Stanley
29.4k9118191
answered Apr 23 at 19:46
Richard StanleyRichard Stanley
29.4k9118191
answered Apr 23 at 19:46
Richard StanleyRichard Stanley
29.4k9118191
29.4k9118191
add a comment |
add a comment |
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.
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%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
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
