Dependencies

The dimension of the space of locally constant functions is the number of connected components of \(G\).

The spectrum of the adjacency operator is real.

Let \(V\) be a set. An operator \(a : V^{\mathbb {C}} \rightarrow V^{\mathbb {C}}\) is adjacency-like if it satisfies the following properties:

• for all \(x \in V\), \(a \mathbf{1}_{\{ x\} } \in \ell ^2(G)\);

• for all \(x, y \in V\), \(a_{x,y} := \langle a \mathbf{1}_{\{ x\} }, \mathbf{1}_{\{ y\} } \rangle \) is a non-negative integer;

• for all \(x, y \in V\), \(a_{x,y}=a_{y,x}\);

• for all \(x \in V\), \(a_{x,x}\) is even.

We define the adjacency operator \(a\) as the linear operator acting on the space of functions \(f : V(G) \rightarrow \mathbb {C}\) by

Let \(x \in V(G)\) and \(r \in \mathbb {N}\). We define the ball \(B_r(x)\) of radius \(r\) centered at \(x\) as the set of vertices \(y \in V(G)\) such that \(\mathrm{edist}(x,y)\leq r\).

The graph \(G\) is bipartite if there exists a partition \(U_1\), \(U_2\) of \(V(G)\) such that, for all \(e \in E(G)\), \(e\) links an element of \(U_1\) and an element of \(U_2\).

Let \(x \in V(G)\) and \(r \in \mathbb {N}\). We define the circle \(C_r(x)\) of radius \(r\) centered at \(x\) as the set of vertices \(y \in V(G)\) such that \(\mathrm{edist}(x,y) = r\).

The graph \(G\) is connected if it is preconnected and \(V(G)\) is not empty.

A connected component of \(G\) is an equivalence class of \(V(G)\) for the relation reachable.

For any vertex \(x\), we define \(\mathrm{cc}(x)\) to be the unique connected component of \(G\) containing \(x\).

A function \(V(G) \rightarrow \mathbb {C}\) is constant if, for all \(x, y \in V(G)\), \(f(x)=f(y)\).

The constant function equal to \(1\) is defined by

We define a set \(D(G)\) of darts on \(G\) with applications

• \(\mathrm{start}, \mathrm{end}: D(G) \rightarrow V(G)\);

• \(\mathrm{edge}: D(G) \rightarrow E(G)\);

• \(\mathrm{symm}: D(G) \rightarrow D(G)\);

such that:

• for all \(d \in D(G)\), \(\mathrm{edge}(d)\) links \(\mathrm{start}(d)\) and \(\mathrm{end}(d)\);

• \(\mathrm{edge}\circ \mathrm{symm}= \mathrm{edge}\);

• \(\mathrm{start}\circ \mathrm{symm}= \mathrm{end}\) and \(\mathrm{end}\circ \mathrm{symm}= \mathrm{start}\);

• for \(d \in D(G)\), \(\mathrm{start}(d) = \mathrm{end}(d)\) if and only if \(\mathrm{edge}(d)\) is a loop;

• \(\mathrm{edge}\) is surjective;

• for \(d, d' \in D(G)\), \(\mathrm{edge}(d) = \mathrm{edge}(d')\) iff \(d=d'\) or \(d=\mathrm{symm}(d')\);

• for all \(d \in D(G)\), \(\mathrm{symm}(d) \neq d\).

Let \(V\) be a set and \(D\), \(\mathrm{start}, \mathrm{end}, \mathrm{symm}\) be a dart-like structure. We define a relation on \(D\) by:

Let \(k \geq 1\) be an integer. To a family \(\vec{\pi } = (\pi _1, \ldots , \pi _k) \in \mathfrak {S}_{V}^k\) we associate a dart-like structure on \(V\) by taking:

• \(D = V \times \{ 1, \ldots , k\} \times \{ -1,+1\} \)

• for \((x,i,\epsilon ) \in D\), we let \(\mathrm{start}(x,i,\epsilon ) = x\), \(\mathrm{end}(x,i,\epsilon ) = \pi _i^\epsilon (x)\) and \(\mathrm{symm}(x,i,\epsilon ) = (\pi _i^\epsilon (x),i,-\epsilon )\).

Let \(V\) be a set. A dart-like structure on \(V\) is the data of a set of darts \(D\), together with maps \(\mathrm{start}, \mathrm{end}: D \rightarrow V\) and \(\mathrm{symm}: D \rightarrow D\) satisfying the following:

• \(\mathrm{start}\circ \mathrm{symm}= \mathrm{end}\) and \(\mathrm{end}\circ \mathrm{symm}= \mathrm{start}\);

• \(\mathrm{symm}\) is an involution with no fixed point.

Let \(V\) be a set and \(a\) be an adjacency-like operator on \(V\). We define a dart-like structure on \(V\) by taking:

• \(D\) is the set of \((x,y,i)\) where \(x \in V\), \(y \in V\), and \(i\) is an integer such that

  • if \(x \neq y\) then \(1 \leq i \leq a_{x,y}\);

  • if \(x=y\) then \(1 \leq |i| \leq a_{x,x}\).

• for any \((x,y,i) \in D\), we let \(\mathrm{start}(x,y,i)=x\), \(\mathrm{end}(x,y,i)=y\) and

  \begin{equation*} \mathrm{symm}(x,y,i) := \begin{cases} \mathrm{symm}(y,x,i) & \text{if } x \neq y \\ \mathrm{symm}(x,y,-i) & \text{if } x = y. \end{cases}\end{equation*}

A dartwalk \((d_i)_{1 \leq i \leq k}\) is a dartpath if all vertices in its support are distinct.

Let \(x \in V(G)\). The dartset of \(x\) is the set

Let \(x\), \(y \in V(G)\). We define the dartset of \((x,y)\) as

Let \(x, y \in V(G)\). A dartwalk from \(x\) to \(y\) on \(G\) is a finite list of darts \((d_i)_{1 \leq i \leq m}\) where:

• \(\mathrm{start}(d_1)=x\);

• \(\mathrm{end}(d_m)=y\);

• for all \(1 \leq i {\lt} m\), \(\mathrm{end}(d_i)=\mathrm{start}(d_{i+1})\).

The support of the dartwalk \((d_i)_{1 \leq i \leq m}\) is the list \((x_i)_{0 \leq i \leq m}\) with \(x_0=\mathrm{start}(d_1)\) and \(x_i = \mathrm{end}(d_i)\) for \(1 \leq i \leq m\).

Let \(x\) be a vertex of \(G\). We assume \(G\) is locally finite at \(x\). The degree of \(x\) is defined as \(\mathrm{deg}(x) = \# \mathrm{dartSet}(x)\).

The diameter of \(G\) is \(\mathrm{diam}(G) = \mathrm{ediam}(G).\mathrm{toNat}\).

The distance between \(x\) and \(y\) is \(\mathrm{dist}(x,y) = \mathrm{edist}(x,y).\mathrm{toNat}\).

The extended diameter of a graph \(G\) is \(\mathrm{ediam}(G) := \sup _{x,y \in V(G)} \mathrm{edist}(x,y)\).

Let \(x, y \in V(G)\). The extended distance \(\mathrm{edist}(x,y)\) between \(x\) and \(y\) is the length of the shortest walk from \(x\) to \(y\) (with value in \(\mathbb {N}\cup \{ \infty \} \)).

We define a dartlike structure on \(V_\delta \) by letting:

• \(D_\delta = V_\delta \times [\delta ]\);

• for \(d=(w,i) \in D_\delta \), we define:

  • \(\mathrm{start}(d)=w\);

  • \(\mathrm{end}(d) = \pi (wi)\) to be the reduced version of the word \(wi\);

  • \(\mathrm{symm}(d)=(\pi (wi),i)\).

The model \(\delta \)-reguar tree \(\mathbb {T}_\delta \) is defined as the graph induced by the dartlike structure defined in Definition 123, where \(V(\mathbb {T}_\delta ) = V_\delta \), \(D(\mathbb {T}_\delta )=D_\delta \) and \(E(\mathbb {T}_\delta )=D(\mathbb {T}_\delta )\diagup \mathrm{symm}\).

Let us define the projection map \(\Pi _\delta ^{\mathrm{dw}}\) from the set of all dartwalks to \(W_\delta \) defined by

Let \(a\) be a adjacency-like operator on \(V\). We define the graph associated to \(a\) by taking the graph associated to the dartlike structure associated to \(a\).

Let \(V\) be a set and \(D\), \(\mathrm{start}, \mathrm{end}, \mathrm{symm}\) be a dart-like structure. We define a graph \(G\) associated to this structure by taking:

• \(V(G) := V\) as the vertex set;

• \(E(G) := D(G) \diagup \sim \) as the edge set;

• for \(e \in E(G)\), if \(d \in D(G)\) is a representant of \(e\), then \(e\) links \(\mathrm{start}(d)\) and \(\mathrm{end}(d)\).

Let \(k \geq 1\) be an integer. To a family \(\vec{\pi } \in \mathfrak {S}_{V}^k\) we associate a graph \(G_{\vec{\pi }}\) on \(V\) by taking the graph associated to the dart-like structure associated to \(\vec{\pi }\).

Let \(U\) be a subset of \(V(G)\). We define the indicator function \(\mathbf{1}_U : V(G) \rightarrow \mathbb {C}\) by

Let \(U\) be a subset of \(V(G)\). Then we define a subgraph \(H\) induced by \(U\) by letting:

• \(V(H) := U\);

• \(E(H) := \{ e \in E(G) : \text{ both endpoints of }e \text{ lie in } U\} \).

A subgraph \(H\) of \(G\) is induced if, for any \(x, y \in V(H)\), for any \(e \in E(G)\), if \(e\) links \(x\) and \(y\) in \(G\), then \(e \in E(H)\).

The length of a walk is its number of edges.

We say \(G\) is locally bounded if it is locally finite and there exists a constant \(D\) such that, for all \(x \in V(G)\), \(\deg (x) \leq D\).

A function \(f : V(G) \rightarrow \mathbb {C}\) is said to be locally constant if, for all \(x,y \in V(G)\), if \(x\) is adjacent to \(y\), then \(f(x)=f(y)\).

\(G\) is said to be locally finite if, for all \(x \in V(G)\), \(G\) is locally finite at \(x\).

Let \(x\) be a vertex of \(G\). We say \(G\) is locally finite at \(x\) if \(\mathrm{dartSet}(x)\) is finite.

We define the union, resp. intersection of two subgraphs by taking the union of their respective vertex sets and edge sets.

Let \(x, y \in V(G)\). A path from \(x\) to \(y\) on \(G\) is a walk \((v_i)_{0 \leq i \leq m}\), \((e_i)_{1 \leq i \leq m}\) such that, for all \(i \neq j\), \(v_i \neq v_j\).

A graph is preconnected if any pair of vertices is reachable.

Let \(k, n \geq 1\) be integers. A random permutation graph of degree \(2k\) with \(n\) vertices is the graph associated to a family \(\vec{\pi } = (\pi _1, \ldots , \pi _k) \in \mathfrak {S}_{n}\) of \(k\) i.i.d. uniform elements of \(\mathfrak {S}_{n}\). We denote by \(\mathrm{Prob}_{n,\delta }\) the corresponding probability measure on the space of \(\delta \) regular graphs with vertex set \([n]\).

We define a binary relation on \(V(G)\) by: \(x \sim y\) if there exists a walk from \(x\) to \(y\) on \(G\). We then say \(x\) and \(y\) are reachable.

Let \(\delta \) be a non-negative integer. We say \(G\) is regular of degree \(\delta \) if it is not empty, locally finite and, for every \(x \in V(G)\), \(\deg (x) = \delta \).

A graph \(G\) is a \(\delta \)-regular tree if it is a tree and regular of degree \(\delta \).

We denote as \(\mathrm{ConnComp}(G)\) the set of connected components of \(G\).

A subgraph \(H\) of \(G\) is a graph (ofthe same type as \(G\)) defined by:

• a vertex set \(V(H)\) included in the vextex set of \(G\)

• an edge set \(E(H)\) included in the edge set of \(H\)

• the same \(\mathrm{IsLink}\) relation, i.e. if \(e\) links \(x\) and \(y\) in \(H\) then it also links \(x\) and \(y\) in \(G\).

The graph \(G\) is a tree if, for all \(x\), \(y \in V(G)\), there exists a unique dartpath from \(x\) to \(y\).

For \(\pi \in \mathfrak {S}_{V}\), we define an operator \(u_\pi : V^{\mathbb {C}} \rightarrow V^{\mathbb {C}}\) by letting, for \(f : V \rightarrow \mathbb {C}\),

Let \(x, y \in V(G)\). A walk from \(x\) to \(y\) on \(G\) is given by two finite lists:

• a list \((v_i)_{0 \leq i \leq m}\) of vertices in \(V(G)\);

• a list \((e_i)_{1 \leq i \leq m}\) of edges in \(E(G)\);

satisfying the following:

• \(v_0=x\) and \(v_m=y\);

• for any \(i \in \{ 1, \ldots , m\} \), \(e_i\) links \(v_{i-1}\) and \(v_i\).

Let \(x\), \(y\) in \(V(G)\). If \(x\) and \(y\) are adjacent then \(x\) and \(y\) are reachable.

Let \(f\) be a locally constant function. Then, for all \(x \in V(G)\), \(af(x) = \deg (x) f(x)\).

For any \(x \in V(G)\), \(a \mathbf{1}(x) = \deg (x)\).

Assume \(G\) is not empty and locally finite. Then \(G\) is regular of degree \(\delta \) iff \(a \mathbf{1}= \delta \mathbf{1}\).

Let \(a\) be a adjacency-like operator on \(V\). Then the graph \(G\) associated to \(a\) is a graph, of vertex set \(V\), and adjacency operator \(a\).

Let \(k \geq 1\) be an integer. For any family \(\vec{\pi } = (\pi _1, \ldots , \pi _k) \in \mathfrak {S}_{V}^k\), the adjacency operator \(a_{\vec{\pi }}\) of \(G_{\vec{\pi }}\) can be written as

Let \(x, y \in V(G)\). The following are equivalent:

1. \(x\) and \(y\) are adjacent;

2. there exists \(d \in \mathrm{dartSet}(x)\) such that \(\mathrm{end}(d)=y\);

3. \(\mathrm{dartSet}(x,y)\) is not empty.

Let \(V\) be a set. The space of adjacency-like operators on \(V\) is stable by addition, i.e. if \(a\), \(a'\) are adjacency-like, so is \(a+a'\).

For any \(x \in V(G)\), \(B_0(x) = C_0(x) = \{ x\} \).

Assume \(G\) is preconnected and \(E(G)\) is non-empty. Then \(G\) is bipartite iff there exists a non-zero function \(f : V(G) \rightarrow \mathbb {C}\) such that, for all \(x, y \in V(G)\), if \(x\) and \(y\) are adjacent, then \(f(x)=-f(y)\).

For any function \(f : V(G) \rightarrow \mathbb {C}\), any vertex \(x \in V(G)\),

Furthermore, this is an equality if and only if for any \(y, z\) adjacent to \(x\), \(f(y) = f(z)\).

Assume \(G\) is locally bounded. Then, for any \(f \in \ell ^2(G)\), \(a f \in \ell ^2(G)\) and

Furthermore, the equality occurs if and only if \(G\) is regular of degree \(\delta \) for some non-negative integer \(\delta \) and, for any \(x \in V(G)\), for any \(y\) and \(z\) adjacent to \(x\), \(f(y)=f(z)\).

If \(V(G)\) is finite, then \(\mathrm{ConnComp}(G)\) is finite and \(\# V(G) \leq \# \mathrm{ConnComp}(G)\).

Let \(x, y \in V(G)\). Then \(\mathrm{cc}(x) = \mathrm{cc}(y)\) iff \(x\) and \(y\) are reachable.

Let \(x \in V(G)\) and \(r \in \mathbb {N}\). For any \(y \in C_{r+1}(x)\), there exists \(z \in C_r(x)\) such that \(y\) and \(z\) are adjacent.

For any \(x \in V(G)\), \(r \in \mathbb {N}\), \(C_r(x) \subseteq B_r(x)\) and if \(r \geq 1\) then \(C_r(x) = B_r(x) - B_{r-1}(x)\).

Let \(x, y \in V(G)\). Then

For any \(x, y \in V(G)\), \(\langle a \mathbf{1}_{\{ x\} }, \mathbf{1}_{\{ y\} } \rangle \) is a non-negative integer, which is even as soon as \(x=y\).

Assume \(V(G)\) is finite and non-empty. Then \(\mathrm{diam}(G) \neq 0\) if and only if \(G\) is connected.

The graph \(G\) is connected if and only if there exists \(x \in V(G)\) such that, for all \(y \in V(G)\), \(x\) and \(y\) are reachable.

Assume \(G\) is regular of degree \(\delta \) and \(V(G)\) is finite. Then \(\delta \) is an eigenvalue of the adjacency operator with associated eigenfunction the constant function \(\mathbf{1}\).

The space of constant functions is included in \(\ell ^2(G)\) if and only if \(V(G)\) is finite.

If \(G\) is locally finite at \(x \in V(G)\), then \(\# \mathrm{dartSet}(x,x)\) is an even number.

The relation \(\sim \) on \(D\) is an equivalence relation, and all of its equivalence classes are of the form \(\{ d, \mathrm{symm}(d)\} \) (the two of which are distinct).

Let \(f : V(G) \rightarrow \mathbb {C}\). The following are equivalent:

1. \(f\) is locally constant;

2. for every \(x \in V(G)\), for every \(d \in \mathrm{dartSet}(x)\), \(f(x)=f(\mathrm{end}(d))\).

3. for every \(d \in D(G)\), \(f(\mathrm{start}(d))=f(\mathrm{end}(d))\).

For any \(d \in D(G)\), \(\mathrm{symm}(\mathrm{symm}(d))=d\).

Let \(k \geq 1\) be an integer and take \(\vec{\pi } = (\pi _1, \ldots , \pi _k) \in \mathfrak {S}_{V}^k\). Then, for any \(x, y \in V\),

Let \(k \geq 1\) be an integer and take \(\vec{\pi } = (\pi _1, \ldots , \pi _k) \in \mathfrak {S}_{V}^k\). Then, for any \(x \in V\),

Let \(x \in V(G)\). \(G\) is locally finite at \(x\) iff \(\mathrm{incidenceSet}(x)\) is finite, and in this case,

Let \(x, y \in V(G)\). \(\mathrm{dist}(x,y) \neq 0\) iff \(x \neq y\) and there exists a walk from \(x\) to \(y\).

Let \(x, y \in V(G)\), we assume \(\mathrm{dist}(x,y) \neq 0\). Then there exists a walk of length \(\mathrm{dist}(x,y)\) from \(x\) to \(y\).

For any \(e \in E(G)\), there exists \(d \in D(G)\) such that \(\mathrm{edge}^{-1}(\{ e\} ) = \{ d, \mathrm{symm}(d)\} \).

Let \(x,y \in V(G)\). The range of the restriction of the function \(\mathrm{edge}\) to \(\mathrm{dartSet}(x,y)\) is exactly the set \(\{ e \in E(G) : e \text{ links } x, y\} \). Furthermore, this map is \(1\)-to-\(1\) if \(x \neq y\) and \(2\)-to-\(1\) if \(x=y\).

Let \(x, y \in V(G)\).

• \(\mathrm{edist}(x,y) = 0\) iff \(x = y\);

• \(\mathrm{edist}(x,y) \neq \infty \) iff there exists a walk from \(x\) to \(y\).

A dartwalk is closed (i.e. starts and ends at the same vertex) iff its image by \(\Pi _\delta ^{\mathrm{dw}}\) reduces to the trivial word.

Let \((d_k)_{1 \leq k \leq m}\) be a dartwalk on \(\mathbb {T}_\delta \) from \(w\) to \(w'\). Then \(w' = \pi (w i_1 \ldots i_m)\).

A dartwalk \((d_i)_{1 \leq i \leq m}\) is a path iff its image by \(\Pi _\delta ^{\mathrm{dw}}\) is reduced.

\(\mathbb {T}_\delta \) is regular of degree \(\delta \).

Let \(w, w' \in V(\mathbb {T}_\delta )\). The restriction of \(\Pi _\delta ^{\mathrm{dw}}\) to the set of dartwalks from \(w\) to \(w'\) is a bijection onto the set of words \(w''\) such that \(w' = \pi (w w'')\).

The graph \(G_{\vec{\pi }}\) is regular of degree \(2k\).

The indicator function of a connected component is locally constant.

The indicator function of a set \(U\) is in \(\ell ^2(G)\) iff \(U\) is finite.

A subgraph is induced iff it is induced from as subset of \(V(G)\).

A locally constant function on a preconnected graph is constant.

The restriction of a locally constant function to a subgraph is locally constant on that subgraph.

Let \(f : V(G) \rightarrow \mathbb {C}\) be a locally constant function. For any \(x, y \in V(G)\), if \(x\) and \(y\) are reachable, then \(f(x)=f(y)\).

Assume \(G\) is regular of degree \(\delta \) and \(V(G)\) is finite. Then there exists \(\lambda \in \mathbb {R}\) and a non-zero function \(f : V(G) \rightarrow \mathbb {C}\) such that \(af=\lambda f\), \(\sum _{x \in V(G)}f(x)=0\) and \(|\lambda | = \| a|_{\mathbf{1}^\perp }\| \).

Assume \(V(G)\) is not empty. Then \(\mathbf{1}\neq 0\).

Assume \(V(G)\) is non-empty and finite. Then, the orthogonal of the space of constant functions is

Let \((\pi _U)_{U \in I}\) be a partition of \(V(G)\). Then \(\mathbf{1}= \sum _{U \in I} \mathbf{1}_U\).

Assume \(G\) is regular of degree \(\delta \) and \(V(G)\) is finite. Then the operator \(a\) induces a bounded self-adjoint operator \(a|_{\mathbf{1}^\perp }\) on the orthogonal of \(\mathbf{1}\) in \(\ell ^2(G)\), and \(\| a|_{\mathbf{1}^\perp }\| \leq d\).

The graph \(G\) is regular of degree \(0\) iff \(E(G)=\emptyset \).

For any \(f\), \(g\) in \(\ell ^2(G)\),

If \(V(G)\) is finite, then the spectrum of the adjacency operator is a family of \(\# V(G)\) eigenvalues.

The spectrum of \(a\) is included in the segment \([-D,D]\) where \(D = \sup _{x \in V(G)} \deg (x)\).

Let \(H\) be a subgraph of \(G\). For any \(x\), \(y\) in \(V(H)\), if \(x\) and \(y\) are adjacent for \(H\), then they are adjacent for \(G\).

For \(\pi \in \mathfrak {S}_{V}\), the operator \(u_\pi \) is a unitary operator on \(\ell ^2(V)\) and \(u_\pi ^*=u_\pi ^{-1}=u_{\pi ^{-1}}\).

Assume \(G\) is a graph of finite diameter. For any \(x \in V(G)\), \(V(G)\) is included in the ball of radius \(\mathrm{diam}(G)\) centered at \(x\).

The adjacency operator is selfadjoint.

Let \(G\) be a regular graph of degree \(\delta \). Assume \(V(G)\) is finite and not empty. Then

Let \(G\) be a \(\delta \)-regular tree. Then, for any \(f \in \ell ^2(G)\), \(|\langle af, f \rangle | \leq 2 \sqrt{\delta -1} \| f \| ^2\).

\(\mathrm{ConnComp}(G)\) is a partition of \(V(G)\).

Assume \(G\) regular of degree \(\delta \geq 1\) and \(V(G)\) is finite. Then \(-\delta \) is an eigenvalue of \(a\) if and only if \(G\) has a bipartite connected component.

\(\mathbb {T}_\delta \) is a tree.

Assume \(G\) is regular of degree \(\delta \) and \(V(G)\) is finite. Then, \(\| a|_{\mathbf{1}^\perp }\| = d\) iff \(G\) is disconnected or bipartite.

Assume \(G\) is locally bounded and let \(D = \sup _{x \in V(G)} \deg (x)\). Then, for any \(x \in V(G)\), any \(r \in \mathbb {N}\), \(\# B_r(x) \leq D^r\).

If \(G\) is regular of degree \(\delta \) and \(V(G)\) is finite, then \(\| a\| =\delta \).

Let \(\delta \geq 4\) be an even integer. Then,

and

The reachability relation is an equivalence relation on \(V(G)\).

Assume \(G\) is regular of degree \(\delta \) and \(V(G)\) is finite. Then the multiplicity of the eigenvalue \(\delta \) is exactly the number of connected components of \(G\).

Let \(G\) be a regular graph of degree \(\delta \) with a finite diameter. Then,

Let \(C\) be a connected component of \(G\). Then the subgraph induced by \(C\) is connected.

The graph constructed in Definition 11 is a graph, and \(D(G) := D\), \(\mathrm{start}\), \(\mathrm{end}\), \(\mathrm{symm}\) are darts of this graph, with the projection edge map \(\mathrm{edge}: D(G) \rightarrow E(G)\).

Let \(\delta \geq 4\) be an even integer. For any \(\epsilon {\gt} 0\),

The space of locally constant functions is a vectorial subspace of the space of functions \(V(G) \rightarrow \mathbb {C}\), and the \(\{ \mathbf{1}_C, C \in \mathrm{ConnComp}(G)\} \) are a basis of this space.

A function \(f\) is locally constant if and only if its restriction to each connected component is a constant function.

Assume \(G\) is locally bounded. Then the adjacency operator is a bounded operator on \(\ell ^2(G)\) and its norm satisfies \(\| a\| \leq \sup _{x \in V(G)} \deg (x)\).

Let \(G\) be a \(\delta \)-regular tree. Then \(\| a\| = 2 \sqrt{\delta -1}\).

Assume \(V(G)\) is not empty. Then the space of constant functions is a vectorial subspace of \(\mathbb {C}^{V(G)}\), of dimension \(1\), generated by \(\mathbf{1}\).