Mixing
Laplacian of an infinite graph and connected components
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
For a finite graph with undirected, unweighted edges, a well-known result is that the dimension of the null space of the Laplacian matrix gives the number of connected components. Does this result apply to infinite graphs as well?
The infinite graphs I'm interested are locally finite. That is, the degree of each node is finite. In my case, the number of nodes is countably infinite, there are no self-edges, and the edges are undirected.
At least according to the PDF from this course:
http://www.maths.nuigalway.ie/~rquinlan/linearalgebra/section3-1.pdf
the connected components theorem does not assume anything about finite graphs. Can someone provide a reference (a paper or text) where this is explicitly discussed?
Thank You!
linear-algebra graph-theory
edited 14 mins ago
YCor
25.9k279122
asked 7 hours ago
user3433489
1615
add a comment |Â
up vote
1
down vote
favorite
For a finite graph with undirected, unweighted edges, a well-known result is that the dimension of the null space of the Laplacian matrix gives the number of connected components. Does this result apply to infinite graphs as well?
The infinite graphs I'm interested are locally finite. That is, the degree of each node is finite. In my case, the number of nodes is countably infinite, there are no self-edges, and the edges are undirected.
At least according to the PDF from this course:
http://www.maths.nuigalway.ie/~rquinlan/linearalgebra/section3-1.pdf
the connected components theorem does not assume anything about finite graphs. Can someone provide a reference (a paper or text) where this is explicitly discussed?
Thank You!
linear-algebra graph-theory
edited 14 mins ago
YCor
25.9k279122
asked 7 hours ago
user3433489
1615
1
It matters which is the function space on which your Laplacian operator acts. Is is all functions, or all bounded functions? or maybe it is $ell^2$ or $ell^1$?
– Uri Bader
6 hours ago
I’m not sure I understand about the function space. I’m thinking of the graph Laplacian D-A where D is the degree matrix and A is the adjacency matrix. D has finite entries and each row/col of A will have a finite number of nonzero entries.
– user3433489
5 hours ago
1
But your $A$ and $D$ are infinite matrices, right? and the null space you look for is in the vector space consisting of functions on the vertices of your graph, right? This is the function space alluded to in my comment. See my answer below for more details.
– Uri Bader
5 hours ago
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
For a finite graph with undirected, unweighted edges, a well-known result is that the dimension of the null space of the Laplacian matrix gives the number of connected components. Does this result apply to infinite graphs as well?
The infinite graphs I'm interested are locally finite. That is, the degree of each node is finite. In my case, the number of nodes is countably infinite, there are no self-edges, and the edges are undirected.
At least according to the PDF from this course:
http://www.maths.nuigalway.ie/~rquinlan/linearalgebra/section3-1.pdf
the connected components theorem does not assume anything about finite graphs. Can someone provide a reference (a paper or text) where this is explicitly discussed?
Thank You!
linear-algebra graph-theory
edited 14 mins ago
YCor
25.9k279122
asked 7 hours ago
user3433489
1615
For a finite graph with undirected, unweighted edges, a well-known result is that the dimension of the null space of the Laplacian matrix gives the number of connected components. Does this result apply to infinite graphs as well?
The infinite graphs I'm interested are locally finite. That is, the degree of each node is finite. In my case, the number of nodes is countably infinite, there are no self-edges, and the edges are undirected.
At least according to the PDF from this course:
http://www.maths.nuigalway.ie/~rquinlan/linearalgebra/section3-1.pdf
the connected components theorem does not assume anything about finite graphs. Can someone provide a reference (a paper or text) where this is explicitly discussed?
Thank You!
linear-algebra graph-theory
linear-algebra graph-theory
edited 14 mins ago
YCor
25.9k279122
asked 7 hours ago
user3433489
1615
edited 14 mins ago
YCor
25.9k279122
asked 7 hours ago
user3433489
1615
edited 14 mins ago
YCor
25.9k279122
edited 14 mins ago
YCor
25.9k279122
edited 14 mins ago
YCor
25.9k279122
25.9k279122
asked 7 hours ago
user3433489
1615
asked 7 hours ago
user3433489
1615
asked 7 hours ago
user3433489
1615
1615
1
It matters which is the function space on which your Laplacian operator acts. Is is all functions, or all bounded functions? or maybe it is $ell^2$ or $ell^1$?
– Uri Bader
6 hours ago
I’m not sure I understand about the function space. I’m thinking of the graph Laplacian D-A where D is the degree matrix and A is the adjacency matrix. D has finite entries and each row/col of A will have a finite number of nonzero entries.
– user3433489
5 hours ago
1
But your $A$ and $D$ are infinite matrices, right? and the null space you look for is in the vector space consisting of functions on the vertices of your graph, right? This is the function space alluded to in my comment. See my answer below for more details.
– Uri Bader
5 hours ago
add a comment |Â
1
It matters which is the function space on which your Laplacian operator acts. Is is all functions, or all bounded functions? or maybe it is $ell^2$ or $ell^1$?
– Uri Bader
6 hours ago
I’m not sure I understand about the function space. I’m thinking of the graph Laplacian D-A where D is the degree matrix and A is the adjacency matrix. D has finite entries and each row/col of A will have a finite number of nonzero entries.
– user3433489
5 hours ago
1
But your $A$ and $D$ are infinite matrices, right? and the null space you look for is in the vector space consisting of functions on the vertices of your graph, right? This is the function space alluded to in my comment. See my answer below for more details.
– Uri Bader
5 hours ago
1
1
It matters which is the function space on which your Laplacian operator acts. Is is all functions, or all bounded functions? or maybe it is $ell^2$ or $ell^1$?
– Uri Bader
6 hours ago
It matters which is the function space on which your Laplacian operator acts. Is is all functions, or all bounded functions? or maybe it is $ell^2$ or $ell^1$?
– Uri Bader
6 hours ago
I’m not sure I understand about the function space. I’m thinking of the graph Laplacian D-A where D is the degree matrix and A is the adjacency matrix. D has finite entries and each row/col of A will have a finite number of nonzero entries.
– user3433489
5 hours ago
I’m not sure I understand about the function space. I’m thinking of the graph Laplacian D-A where D is the degree matrix and A is the adjacency matrix. D has finite entries and each row/col of A will have a finite number of nonzero entries.
– user3433489
5 hours ago
1
1
But your $A$ and $D$ are infinite matrices, right? and the null space you look for is in the vector space consisting of functions on the vertices of your graph, right? This is the function space alluded to in my comment. See my answer below for more details.
– Uri Bader
5 hours ago
But your $A$ and $D$ are infinite matrices, right? and the null space you look for is in the vector space consisting of functions on the vertices of your graph, right? This is the function space alluded to in my comment. See my answer below for more details.
– Uri Bader
5 hours ago
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
6
down vote
accepted
For infinite (locally finite) graphs it is not true in general that the dimension of the kernel of the Laplacian is the number of connected components.
The simplest example to have in mind is the standard graph structure on $mathbbZ$, which is connected, where the kernel of the Laplacian consists exactly of all arithmetic progressions - a two dimensional space.
Here we view the Laplacian as an operator on the space of all functions on the graph.
In view of this example and related phenomena, it makes sense to restrict the attention to smaller function spaces, e.g the space $ell^infty(V)$ consisting of all bounded function or the space $ell^2(V)$ consisting of all square summable functions on the set of vertices of our graph, $V$.
For these spaces the kernel of the Laplacian on $ell^infty(mathbbZ)$ is one dimensional, as you might expect from your finite graph experience, while it is zero dimensional on $ell^2(mathbbZ)$.
But the story gets more complicated for more complicated graphs and the dimension of the Laplacian might get infinite even for $ell^infty(V)$ when the graph is connected, eg when it is an infinite tree.
There is a vast literature on the subject. Google up "harmonic functions on graphs" (note that elements in the kernel of the Laplacian are called harmonic functions).
answered 5 hours ago
Uri Bader
6,13411532
Forgive me, but what do you mean by the standard graph structure on the integers? Why can’t the finite linear algebra approach be applied to an infinite, locally finite graph?
– user3433489
5 hours ago
2
Regarding your first question, by saying "the standard graph structure on $mathbbZ$" I meant to consider the graph which vertices are the integers and an edge is drawn between each pair of consecutive ones. Your second question is of more philosophical nature and I am not qualified to answer it.
– Uri Bader
5 hours ago
Thank you for explaining!
– user3433489
46 mins ago
add a comment |Â
up vote
2
down vote
As Uri Bader points out, the infinite tree has an infinitely dimensional space of harmonic functions, so this is an answer to the philosophical part of the question: The way you prove that all harmonic functions on a finite graph are constant is by using a maximum principle (the value of a function at a vertex is the average over the neighbors, so if there is a vertex where the value of the function is maximal, the function must assume the same value on all the neighbors, etc. However, a function on an infinite set need not assume its supremum, which is where the argument breaks down.
answered 3 hours ago
Igor Rivin
78.2k8111304
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
accepted
For infinite (locally finite) graphs it is not true in general that the dimension of the kernel of the Laplacian is the number of connected components.
The simplest example to have in mind is the standard graph structure on $mathbbZ$, which is connected, where the kernel of the Laplacian consists exactly of all arithmetic progressions - a two dimensional space.
Here we view the Laplacian as an operator on the space of all functions on the graph.
In view of this example and related phenomena, it makes sense to restrict the attention to smaller function spaces, e.g the space $ell^infty(V)$ consisting of all bounded function or the space $ell^2(V)$ consisting of all square summable functions on the set of vertices of our graph, $V$.
For these spaces the kernel of the Laplacian on $ell^infty(mathbbZ)$ is one dimensional, as you might expect from your finite graph experience, while it is zero dimensional on $ell^2(mathbbZ)$.
But the story gets more complicated for more complicated graphs and the dimension of the Laplacian might get infinite even for $ell^infty(V)$ when the graph is connected, eg when it is an infinite tree.
There is a vast literature on the subject. Google up "harmonic functions on graphs" (note that elements in the kernel of the Laplacian are called harmonic functions).
answered 5 hours ago
Uri Bader
6,13411532
Forgive me, but what do you mean by the standard graph structure on the integers? Why can’t the finite linear algebra approach be applied to an infinite, locally finite graph?
– user3433489
5 hours ago
2
Regarding your first question, by saying "the standard graph structure on $mathbbZ$" I meant to consider the graph which vertices are the integers and an edge is drawn between each pair of consecutive ones. Your second question is of more philosophical nature and I am not qualified to answer it.
– Uri Bader
5 hours ago
Thank you for explaining!
– user3433489
46 mins ago
add a comment |Â
up vote
6
down vote
accepted
For infinite (locally finite) graphs it is not true in general that the dimension of the kernel of the Laplacian is the number of connected components.
The simplest example to have in mind is the standard graph structure on $mathbbZ$, which is connected, where the kernel of the Laplacian consists exactly of all arithmetic progressions - a two dimensional space.
Here we view the Laplacian as an operator on the space of all functions on the graph.
In view of this example and related phenomena, it makes sense to restrict the attention to smaller function spaces, e.g the space $ell^infty(V)$ consisting of all bounded function or the space $ell^2(V)$ consisting of all square summable functions on the set of vertices of our graph, $V$.
For these spaces the kernel of the Laplacian on $ell^infty(mathbbZ)$ is one dimensional, as you might expect from your finite graph experience, while it is zero dimensional on $ell^2(mathbbZ)$.
But the story gets more complicated for more complicated graphs and the dimension of the Laplacian might get infinite even for $ell^infty(V)$ when the graph is connected, eg when it is an infinite tree.
There is a vast literature on the subject. Google up "harmonic functions on graphs" (note that elements in the kernel of the Laplacian are called harmonic functions).
answered 5 hours ago
Uri Bader
6,13411532
Forgive me, but what do you mean by the standard graph structure on the integers? Why can’t the finite linear algebra approach be applied to an infinite, locally finite graph?
– user3433489
5 hours ago
2
Regarding your first question, by saying "the standard graph structure on $mathbbZ$" I meant to consider the graph which vertices are the integers and an edge is drawn between each pair of consecutive ones. Your second question is of more philosophical nature and I am not qualified to answer it.
– Uri Bader
5 hours ago
Thank you for explaining!
– user3433489
46 mins ago
add a comment |Â
up vote
6
down vote
accepted
up vote
6
down vote
accepted
For infinite (locally finite) graphs it is not true in general that the dimension of the kernel of the Laplacian is the number of connected components.
The simplest example to have in mind is the standard graph structure on $mathbbZ$, which is connected, where the kernel of the Laplacian consists exactly of all arithmetic progressions - a two dimensional space.
Here we view the Laplacian as an operator on the space of all functions on the graph.
In view of this example and related phenomena, it makes sense to restrict the attention to smaller function spaces, e.g the space $ell^infty(V)$ consisting of all bounded function or the space $ell^2(V)$ consisting of all square summable functions on the set of vertices of our graph, $V$.
For these spaces the kernel of the Laplacian on $ell^infty(mathbbZ)$ is one dimensional, as you might expect from your finite graph experience, while it is zero dimensional on $ell^2(mathbbZ)$.
But the story gets more complicated for more complicated graphs and the dimension of the Laplacian might get infinite even for $ell^infty(V)$ when the graph is connected, eg when it is an infinite tree.
There is a vast literature on the subject. Google up "harmonic functions on graphs" (note that elements in the kernel of the Laplacian are called harmonic functions).
answered 5 hours ago
Uri Bader
6,13411532
For infinite (locally finite) graphs it is not true in general that the dimension of the kernel of the Laplacian is the number of connected components.
The simplest example to have in mind is the standard graph structure on $mathbbZ$, which is connected, where the kernel of the Laplacian consists exactly of all arithmetic progressions - a two dimensional space.
Here we view the Laplacian as an operator on the space of all functions on the graph.
In view of this example and related phenomena, it makes sense to restrict the attention to smaller function spaces, e.g the space $ell^infty(V)$ consisting of all bounded function or the space $ell^2(V)$ consisting of all square summable functions on the set of vertices of our graph, $V$.
For these spaces the kernel of the Laplacian on $ell^infty(mathbbZ)$ is one dimensional, as you might expect from your finite graph experience, while it is zero dimensional on $ell^2(mathbbZ)$.
But the story gets more complicated for more complicated graphs and the dimension of the Laplacian might get infinite even for $ell^infty(V)$ when the graph is connected, eg when it is an infinite tree.
There is a vast literature on the subject. Google up "harmonic functions on graphs" (note that elements in the kernel of the Laplacian are called harmonic functions).
answered 5 hours ago
Uri Bader
6,13411532
edited 5 hours ago
answered 5 hours ago
Uri Bader
6,13411532
answered 5 hours ago
Uri Bader
6,13411532
answered 5 hours ago
Uri Bader
6,13411532
6,13411532
Forgive me, but what do you mean by the standard graph structure on the integers? Why can’t the finite linear algebra approach be applied to an infinite, locally finite graph?
– user3433489
5 hours ago
2
Regarding your first question, by saying "the standard graph structure on $mathbbZ$" I meant to consider the graph which vertices are the integers and an edge is drawn between each pair of consecutive ones. Your second question is of more philosophical nature and I am not qualified to answer it.
– Uri Bader
5 hours ago
Thank you for explaining!
– user3433489
46 mins ago
add a comment |Â
Forgive me, but what do you mean by the standard graph structure on the integers? Why can’t the finite linear algebra approach be applied to an infinite, locally finite graph?
– user3433489
5 hours ago
2
Regarding your first question, by saying "the standard graph structure on $mathbbZ$" I meant to consider the graph which vertices are the integers and an edge is drawn between each pair of consecutive ones. Your second question is of more philosophical nature and I am not qualified to answer it.
– Uri Bader
5 hours ago
Thank you for explaining!
– user3433489
46 mins ago
Forgive me, but what do you mean by the standard graph structure on the integers? Why can’t the finite linear algebra approach be applied to an infinite, locally finite graph?
– user3433489
5 hours ago
Forgive me, but what do you mean by the standard graph structure on the integers? Why can’t the finite linear algebra approach be applied to an infinite, locally finite graph?
– user3433489
5 hours ago
2
2
Regarding your first question, by saying "the standard graph structure on $mathbbZ$" I meant to consider the graph which vertices are the integers and an edge is drawn between each pair of consecutive ones. Your second question is of more philosophical nature and I am not qualified to answer it.
– Uri Bader
5 hours ago
Regarding your first question, by saying "the standard graph structure on $mathbbZ$" I meant to consider the graph which vertices are the integers and an edge is drawn between each pair of consecutive ones. Your second question is of more philosophical nature and I am not qualified to answer it.
– Uri Bader
5 hours ago
Thank you for explaining!
– user3433489
46 mins ago
Thank you for explaining!
– user3433489
46 mins ago
add a comment |Â
up vote
2
down vote
As Uri Bader points out, the infinite tree has an infinitely dimensional space of harmonic functions, so this is an answer to the philosophical part of the question: The way you prove that all harmonic functions on a finite graph are constant is by using a maximum principle (the value of a function at a vertex is the average over the neighbors, so if there is a vertex where the value of the function is maximal, the function must assume the same value on all the neighbors, etc. However, a function on an infinite set need not assume its supremum, which is where the argument breaks down.
answered 3 hours ago
Igor Rivin
78.2k8111304
add a comment |Â
up vote
2
down vote
As Uri Bader points out, the infinite tree has an infinitely dimensional space of harmonic functions, so this is an answer to the philosophical part of the question: The way you prove that all harmonic functions on a finite graph are constant is by using a maximum principle (the value of a function at a vertex is the average over the neighbors, so if there is a vertex where the value of the function is maximal, the function must assume the same value on all the neighbors, etc. However, a function on an infinite set need not assume its supremum, which is where the argument breaks down.
answered 3 hours ago
Igor Rivin
78.2k8111304
add a comment |Â
up vote
2
down vote
up vote
2
down vote
As Uri Bader points out, the infinite tree has an infinitely dimensional space of harmonic functions, so this is an answer to the philosophical part of the question: The way you prove that all harmonic functions on a finite graph are constant is by using a maximum principle (the value of a function at a vertex is the average over the neighbors, so if there is a vertex where the value of the function is maximal, the function must assume the same value on all the neighbors, etc. However, a function on an infinite set need not assume its supremum, which is where the argument breaks down.
answered 3 hours ago
Igor Rivin
78.2k8111304
As Uri Bader points out, the infinite tree has an infinitely dimensional space of harmonic functions, so this is an answer to the philosophical part of the question: The way you prove that all harmonic functions on a finite graph are constant is by using a maximum principle (the value of a function at a vertex is the average over the neighbors, so if there is a vertex where the value of the function is maximal, the function must assume the same value on all the neighbors, etc. However, a function on an infinite set need not assume its supremum, which is where the argument breaks down.
answered 3 hours ago
Igor Rivin
78.2k8111304
answered 3 hours ago
Igor Rivin
78.2k8111304
answered 3 hours ago
Igor Rivin
78.2k8111304
answered 3 hours ago
Igor Rivin
78.2k8111304
78.2k8111304
add a comment |Â
add a comment |Â
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f312759%2flaplacian-of-an-infinite-graph-and-connected-components%23new-answer', 'question_page');
);
Post as a guest
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
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
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
1
It matters which is the function space on which your Laplacian operator acts. Is is all functions, or all bounded functions? or maybe it is $ell^2$ or $ell^1$?
– Uri Bader
6 hours ago
I’m not sure I understand about the function space. I’m thinking of the graph Laplacian D-A where D is the degree matrix and A is the adjacency matrix. D has finite entries and each row/col of A will have a finite number of nonzero entries.
– user3433489
5 hours ago
1
But your $A$ and $D$ are infinite matrices, right? and the null space you look for is in the vector space consisting of functions on the vertices of your graph, right? This is the function space alluded to in my comment. See my answer below for more details.
– Uri Bader
5 hours ago