Dependencies

Let \(\tau \) denote the constant function which assigns the value \(1\) on each vertex.

The adjacency matrix of a graph \(G\), denoted \(A\) is defined as follows,

The Cheeger constant of a graph \(G\), denoted \(h_G\), is defined as the minimum of \(h_G(S)\) for every set of vertices \(S\) with non-zero volume and co-volume:

A graph is connected if it is preconnected and contains at least one vertex.

In a graph G, let \(d_v\) denote the degree (number of incident edges) of vertex \(v\).

The Dirichlet sum of a graph \(G\) for a function \(f : \alpha \to \mathbb {R}\) is defined as

For a subset of vertices \(S \subseteq V\), the edge boundary \(\partial S\) consists of all edges with exactly one endpoint in \(S\) and the other in \(S^c\).

For two sets of vertices \(A\) and \(B\), \(E(A, B)\) denotes the set of edges with one endpoint in \(A\) and one endpoint in \(B\).

The volume of a graph is defined as the sum of the degrees of its vertices.

For a vertex set \(S\), we define \(h_G(S)\) as the ratio of the size of its edge boundary to the minimum volume of \(S\) and its complement:

A vertex v is said to be isolated if \(d_v = 0\).

For \(k \in \mathbb {N}\), a graph is said to be \(k\)-regular if every vertex \(v\) has degree \(d_v = k\).

Consider the matrix L, defined as follows

Following 19, the eigenvalues of \(\mathcal{L}\) are all real and non-negative.

Consider the matrix \(\mathcal{L}\), defined as follows

The Laplacian of a graph can be viewed as an operator on the space of functions \(g : V(G) \rightarrow \mathbb {R}\).

The Laplacian Operator satisfies

A graph is said to be nontrivial if it contains at least one edge.

A graph is preconnected if every pair of vertices is reachable from one another.

Two vertices \(u\) and \(v\) are said to be reachable if there is a walk between them.

Let \(S\) denote the matrix whose rows are indexed by the vertices and whose columns are indexed by the edges of G. Each column corresponding to an edge \(e = \{ u, v\} \) has an entry \(1/\sqrt{d_u}\) in the row corresponding to \(u\), an entry \(−1/\sqrt{d_v}\) in the row corresponding to \(v\), and has zero entries elsewhere.

We also define \(T^{-1/2}\) with the convention that \(T^{-1/2} = 0\) when \(d_v = 0\).

Let \(T\) denote the diagonal matrix with the \((u,v)\)-th entry having value \(d_v\).

A walk is a sequence of adjacent vertices. For vertices \(u, v \in V\), the walk between them is a sequence starting at \(u\) and ending at \(v\).

We extend the definition of a general graph to that of a weighted graph by defining a weight function over its edges.

with the condition that

We also add an arbitray orientation for undirected edges.

For any set of vertices \(S\) satisfying \(\operatorname {vol}(S) \le \operatorname {vol}(S^c)\) and \(0 {\lt} \min (\operatorname {vol}(S), \operatorname {vol}(S^c))\), we have:

A graph \(G\) is connected if and only if its Cheeger constant is strictly positive:

In a connected graph, every set of vertices \(S\) different from the empty set and the universal set (\(S \neq \emptyset \) and \(S \neq V\)) has a non-empty edge boundary, that is \(\partial S \neq \emptyset \).

For any set of vertices \(S\), the edge boundary of \(S\) is equal to the edge boundary of its complement:

In the previous lemma, the equality holds if and only if \(G\) has no isolated vertices.

The sum of the eigenvalues of the graph is at most its number of vertices, that is

The Matrix \(\mathcal{L}\) is hermitian.

For a general graph without isolated vertices, we have

When \(G\) is \(k\)-regular,

We note that \(\mathcal{L}\) can be written as

When \(n{\gt}1\), we obtain the following upper bound on the second eigenvalue:

The edge boundary of a set \(S\) is equal to the edge connection between \(S\) and \(S^c\):

We derive a simple upper bound for the first non-trivial eigenvalue \(\lambda _1\) in terms of the Cheeger constant of a connected graph:

If there is a walk going from a vertex \(u \in S\) to a vertex \(v \in S^c\), then there is at least one edge that goes from \(S\) to \(S^c\).

\(T^{1/2} * \tau \) is an eigenfunction of \(\mathcal{L}\) with eigenvalue \(0\).