5
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ 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$? $\endgroup$
    – Uri Bader
    Commented Oct 13, 2018 at 18:19
  • $\begingroup$ 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. $\endgroup$
    – user3433489
    Commented Oct 13, 2018 at 19:16
  • 2
    $\begingroup$ 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. $\endgroup$
    – Uri Bader
    Commented Oct 13, 2018 at 19:23

2 Answers 2

Reset to default
10
$\begingroup$

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 $\mathbb{Z}$, 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}(\mathbb{Z})$ is one dimensional, as you might expect from your finite graph experience, while it is zero dimensional on $\ell^2(\mathbb{Z})$.

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – user3433489
    Commented Oct 13, 2018 at 19:29
  • 3
    $\begingroup$ Regarding your first question, by saying "the standard graph structure on $\mathbb{Z}$" 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. $\endgroup$
    – Uri Bader
    Commented Oct 13, 2018 at 19:35
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Has anyone explored what types of infinite graphs do give a relationship between the kernel of the Laplacian in $\ell^\infty(V)$ and the number of connected components? It seems like the finite result at least extends to the standard structure graph over $\mathbb{Z}$. When does it break down? $\endgroup$
    – user3433489
    Commented Oct 14, 2018 at 19:52
  • 2
    $\begingroup$ There is plenty of work on that too, this is the so-called "type problem" (at least for planar graphs) $\endgroup$
    – Igor Rivin
    Commented Oct 14, 2018 at 20:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .