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

A distribution \(\nu \in \mathcal{D}(\mathbb {R})\) is a compactly supported distribution if its support is compact.

Let \(w = (d_i)_{1 \leq i \leq m}\) be a dartwalk from \(x\) to \(y\) and \(w' = (d_i')_{1 \leq i \leq m'}\) be a dartwalk from \(y\) to \(z\). We define the concatenation \(w \cdot w'\) to be the dartwalk \((d_i'')_{1 \leq i \leq m+m'}\) where \(d_i''=d_i\) for \(i \leq m\) and \(d_{i-m}'\) for \(i {\gt} m\).

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

A graph \(G_2\) is a covering graph of a graph \(G_1\) if there exists a covering map \(\pi : G_2 \rightarrow G_1\).

A morphism \(f : G_1 \rightarrow G_2\) is a covering map if it is surjective and a local isomorphism.

A dart \(d\) in a graph \(G\) is an oriented edge, meaning it has a start point \(\mathrm{start}(d)\), and endpoint \(\mathrm{end}(d)\), is carried by an edge \(\mathrm{edge}(d)\), and, in the case where \(e\) is a loop, it has an additional information encoded in a boolean \(\in \{ 0, 1\} \) encoding an orientation.

We denote as \(D(G)\) the set of darts on \(G\).

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

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

• \(D = V \times \{ 1, \ldots , r\} \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{rev}(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{rev}: D \rightarrow D\) satisfying the following:

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

• \(\mathrm{rev}\) 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{rev}(x,y,i) := \begin{cases} \mathrm{rev}(y,x,i) & \text{if } x \neq y \\ \mathrm{rev}(x,y,-i) & \text{if } x = y. \end{cases}\end{equation*}

A dartwalk \((d_i)_{1 \leq i \leq m}\) is called a path if for all \(1 \leq i,j \leq m\), \(\mathrm{start}(d_i) = \mathrm{start}(d_j) \Rightarrow i=j\).

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 given by a finite list \((d_1, \ldots , d_m)\) of darts, satisfying the following:

• \(\mathrm{start}(d_1)=x\) and \(\mathrm{end}(d_m)=y\);

• for any \(i \in \{ 1, \ldots , m-1\} \), \(\mathrm{end}(d_{i+1}) = \mathrm{start}(d_i)\).

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\). The edegree of \(x\) is defined as \(\mathrm{edeg}(x) = \# \mathrm{dartSet}(x)\), which is an element of \(\mathbb {N} \cup \{ \infty \} \). The degree of \(x\) is the natural-number projection of the edegree.

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

Let \(A\) be a subset of \(\mathbb {R}\). We say \(\nu \in \mathcal{D}(\mathbb {R})\) vanishes on \(A\) if, for all \(h \in C_c^\infty (\mathbb {R})\), if \(\mathrm{supp} \, h \subseteq A\), then \(\nu (h)=0\).

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 dartwalk from \(x\) to \(y\) (with value in \(\mathbb {N}\cup \{ \infty \} \)).

A graph \(G\) is finite if \(V(G)\) and \(E(G)\) are both finite sets.

We denote as \(\mathbb {F}_r= \langle g_1, \ldots , g_r \rangle \) the free group with \(r\) generators.

A function \(f : G_1 \rightarrow G_2\) is a pair of functions \(f_V : V(G_1) \rightarrow V(G_2)\) and \(f_E : E(G_1) \rightarrow E(G_2)\). We will denote \(f_V(x)=f(x)\) for \(x \in V(G_1)\) and \(f_E(e)=f(e)\) for \(e \in E(G_1)\), i.e. view \(f\) as a function from \(V(G_1) \cup E(G_1)\) to \(V(G_2) \cup E(G_2)\) sending vertices on vertices and edges on edges.

Let \(q \geq 1\) be an integer. For \(1 \leq j \leq q-1\), we define \(r_{r,q,j} := \min (r, \lfloor q/(j+1) \rfloor )\) and we define the polynomial \(g_{r,q}(x) = \prod _{j=1}^{q-1} (1-j x)^{r_{r,q,j}}\).

A morphism \(f : G_1 \rightarrow G_2\) is an isomorphism if there exist a morphism \(g : G_2 \rightarrow G_1\) which is the inverse of \(f\). In this case we denote \(f^{-1}\) this inverse.

A morphism \(f : G_1 \rightarrow G_2\) is a function \(f : G_1 \rightarrow G_2\) such that for all \(x, y \in V(G_1)\), \(e \in E(G_1)\), if \(e\) links \(x\) and \(y\) in \(G_1\), then \(f(e)\) links \(f(x)\) and \(f(y)\) in \(G_2\).

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{rev}\) 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 \(r \geq 1\) be an integer. To a family \(\vec{\pi } \in \mathfrak {S}_{V}^r\) we associate a graph \(G_{\vec{\pi }}\) on \(V\) by taring the graph associated to the dart-like structure associated to \(\vec{\pi }\).

Let \(x, y \in V(G)\). Two dartwalks \(w = (d_i)_{1 \leq i \leq m}\) and \(w' = (d_i')_{1 \leq i \leq m'}\) from \(x\) to \(y\) are said to be homotopic if there exists a finite sequence \((w_j)_{1 \leq j \leq n}\) such that:

• for all \(1 \leq j \leq n\), \(w_j\) is a dartwalk from \(x\) to \(y\);

• \(w_1=w\) and \(w_n=w'\);

• for any \(1 \leq j {\lt} n\), either \(w_j\) is a reduction of \(w_{j+1}\) or \(w_{j+1}\) is a reduction of \(w_j\).

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

A morphism \(f : G_1 \rightarrow G_2\) is a local isomorphism if for all \(x \in V(G_1)\), the restriction of \(f\) to \(\mathrm{incidenceSet}(x)\) is a bijection onto \(\mathrm{incidenceSet}(f(x))\).

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

Let \(x \in V(G)\). We say \(G\) is locally finite at \(x\) if \(\mathrm{dartSet}(x)\) is finite. The graph \(G\) is locally finite if it is locally finite at every vertex.

We define the union \(H_1 \cup H_2\) of two subgraphs by taking the union of their respective vertex sets and edge sets, and the intersection \(H_1 \cap H_2\) by taking their intersection.

A dartwalk \((d_i)_{1 \leq i \leq m}\) is called non-backtracking if for all \(1 \leq i {\lt} m\), \(d_{i+1} \neq \mathrm{rev}(d_{i})\).

The normalised trace \(\mathrm{tr}_N: \mathcal{M}_N(\mathbb {C})\rightarrow \mathbb {C}\) is defined by \(\mathrm{tr}_N:= \frac{1}{N} \mathrm{Tr_N}\).

Let \(G\) be a group with neutral element \(\mathbf{1}\). To a family \((x_1, \ldots , x_r) \in G^r\) we associate a family \((x_0, \ldots , x_{2r}) \in G^{2r+1}\) by letting \(x_0= \mathbf{1}\) and for \(1 \leq i \leq r\), \(x_{r+i} := x_i^{-1}\).

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

Denote \(\mathfrak {d}= 2r\). Let \(\mathcal{G}_{\mathfrak {d},N}\) be the set of \(\mathfrak {d}\)-regular graphs with \(V(G) = [N]\), equiped with the power-set \(\sigma \)-algebra. We define a probability measure \(\mathrm{Prob}_{N,\mathfrak {d}}^{G}\) on \(\mathcal{G}_{\mathfrak {d},N}\) by pushing forward \(\mathrm{Prob}_{N,r}\) with the function \(\mathfrak {S}_{N}^r \rightarrow \mathcal{G}_{\mathfrak {d},N}\) defined in Definition 3.1.2.

We equip \(\mathfrak {S}_{N}^r\) with the uniform probability measure which we denote as \(\mathrm{Prob}_{N,r}\). We denote the corresponding expectation by \(\mathbb {E}_{N,r}\).

Let \(\nu \in \mathcal{D}(\mathbb {R})\) be a compactly supported distribution. We define

We define a binary relation on \(V(G)\) by: \(x \sim y\) if there exists a dartwalk 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 \(\mathfrak {d}\)-regular tree if it is a tree and regular of degree \(\mathfrak {d}\).

To each dart \(d\) we associate a reverse dart \(\mathrm{rev}(d)\) such that:

• \(\mathrm{start}(\mathrm{rev}(d)) = \mathrm{end}(d)\);

• \(\mathrm{end}(\mathrm{rev}(d)) = \mathrm{start}(d)\);

• \(\mathrm{edge}(\mathrm{rev}(d)) = \mathrm{edge}(d)\);

• if \(\mathrm{edge}(d)\) is a loop then the orientation of \(\mathrm{rev}(d)\) is the negation of the orientation of \(d\).

A rooted graph is a graph \(G\) with a distinguished vertex \(r\), its root.

Let \((G,r)\) be a rooted graph. A child of \(x \in V(G)\) is an adjacent vertice which is not a parent.

Let \((G,r)\) be a rooted graph. Let \(x \in V(G)\). A vertex \(y \in V(G)\) is a parent of \(x\) if \(y\) is adjacent to \(x\) and \(\mathrm{dist}(r,y) = \mathrm{dist}(r,x)-1\).

A rooted tree is a rooted graph \((G,r)\) which is a tree.

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

A subgraph \(H\) of \(G\) is a graph (of the 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\).

Let \(\nu \in \mathcal{D}(\mathbb {R})\). The support of \(\nu \) is the intersection of all closed sets \(A \subseteq \mathbb {R}\) such that \(\nu \) vanishes on the complement of \(A\). We denote it as \(\mathrm{supp} \, \nu \).

The graph \(G\) is a tree if, for all \(x\), \(y \in V(G)\), there exists a unique path 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}\),

We define the universal cover \(\hat{G}\) of \((G,r)\), which is a rooted graph, by letting:

• \(V(\hat G)\) be the set of non-backtracking dartwalks on \(G\) starting at \(r\);

• the dartset \(D(\hat{G})\) is defined as the set of pairs \((w,d)\) where \(w\) is a non-backtracking dartwalk (\(w \in V(\hat{G})\)) and \(d \in D(G)\) is a dart on \(G\) starting at the endpoint of \(w\);

• for \((w,d) \in D(\hat{G})\), \(\mathrm{start}_{\hat{G}}(w,d) = w\), \(\mathrm{end}_{\hat{G}}(d) = (w \cdot d)_{\mathrm{nb}}\) and \(\mathrm{rev}_{\hat{G}}(w,d) = ((w \cdot d)_{\mathrm{nb}},\mathrm{rev}_G(d))\);

• the root \(\hat{r}\) is the empty walk from \(r\) to \(r\).

Let \(w = (d_i)_{1 \leq i \leq m}\) be a dartwalk. We say \(w\) admits a reduction if there exists \(1 \leq j {\lt} m\) such that \(d_{j+1} = \mathrm{rev}(d_j)\). In this case, we call the dartwalk \(w'=(d_i')_{1 \leq i \leq m-2}\) obtained by letting \(d_i'=d_i\) for \(i{\lt}j\) and \(d_i'=d_{i+2}\) for \(i \geq j\) a reduction of \(w\).

We denote as \(\mathbf{W}_r\) the set of finite words \(w = w_1 \ldots w_q\) in the letters \(\{ 0, \ldots 2r\} \). The length \(|w| = q\) of a word \(w\) is its number of letters.

Let \(w = w_1 \ldots w_q \in \mathbf{W}_r\) and \(G\) be a group with neutral element \(\mathbf{1}\). The word map \(w : G^r \rightarrow G\) is defined by letting, for each \((x_1, \ldots , x_r) \in G^r\), \(w(x_1, \ldots , x_r) = x_{w_1} \ldots x_{w_q}\) with the numbering convention from Definition 3.3.1.

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 \(\mathfrak {d}\) iff \(a \mathbf{1}= \mathfrak {d}\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 \(r \geq 1\) be an integer. For any family \(\vec{\pi } = (\pi _1, \ldots , \pi _r) \in \mathfrak {S}_{V}^r\), 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'\).

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

Let \(h \in \mathcal{P}_q\) and \((a_j)_{0 \leq j \leq q}\) be the coefficients from Lemma 4.2.1. Then,

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 \(h \in \mathcal{P}_q\), and \(f\) and \((a_j)_{0 \leq j \leq q}\) be as in Lemma 4.2.2. For any \(m \geq 0\), any \(\beta {\gt} 1\), if we denote \(1/\beta _* := 1 - 1/\beta \), we have

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

Let \(h \in \mathcal{P}_q\). There exists a unique family of real numbers \((a_j)_{0 \leq j \leq q}\) such that, for all \(x \in \mathbb {R}\),

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 \(\mathfrak {d}\) and \(V(G)\) is finite. Then \(\mathfrak {d}\) 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.

• For any dart \(d\), \(\mathrm{rev}(d) \neq d\).

• For any dart \(d\), \(\mathrm{rev}(\mathrm{rev}(d)) = d\).

• We have a map \(e \in E(G) \mapsto d_e \in D(G)\) such that, for all \(e\), if \(e\) links \(x\) and \(y\), then \(d_e\) is a dart from \(x\) to \(y\) carried by \(e\).

• For any \(d, d'\), if \(\mathrm{edge}(d)=\mathrm{edge}(d')\) then \(d=d'\) or \(d=\mathrm{rev}(d')\).

• We have \(d_1 = d_2\) iff \(\mathrm{start}(d_1) = \mathrm{start}(d_2)\) and \(\mathrm{edge}(d_1) = \mathrm{edge}(d_2)\) (and same characterisation using the endpoints and edges).

The relation \(\sim \) on \(D\) is an equivalence relation, and all of its equivalence classes are of the form \(\{ d, \mathrm{rev}(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))\).

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

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

For any \(q \geq 1\), the degree of \(g_{r,q}\) is at most \(q(1+\log r)-1\).

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 dartwalk from \(x\) to \(y\).

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

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

has range \(\{ e \in E(G) : e \text{ links } x \text{ and } y\} \). It is \(2-1\) if \(x=y\) and \(1-1\) otherwise.

Let \((G,r)\) be a rooted graph. Assume \(G\) is connected. Any vertex \(x \in V(G)\) distinct from the root admits a parent.

Let \(\nu \in \mathcal{D}(\mathbb {R})\) be a compactly supported distribution. Then there is a unique continuous linear extension \(\nu : C^\infty (\mathbb {R}) \rightarrow \mathbb {R}\) of \(\nu \). Furthermore, there exist real numbers \(K \geq 0\), \(C{\gt}0\) and an integer \(m \geq 0\) such that

Let \(h \in \mathcal{P}_q\) and \((a_j)_{0 \leq j \leq q}\) be the coefficients from Lemma 4.2.1. Let \(f : \mathbb {T}\rightarrow \mathbb {R}\) be the function defined by \(f(\theta ) = h(K \cos \theta )\). Then, \(f\) is a trigonometric polynomial equal to

For any function \(F : \mathfrak {S}_{N}^r \rightarrow \mathbb {C}\),

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

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

The length of the concatenation of two dartwalks is the sum of their lengths.

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 \(\mathfrak {d}\) 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 \(\mathfrak {d}\) 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\).

Let \(\nu \in \mathcal{D}(\mathbb {R})\) be a compactly supported distribution. Then \(\rho (\nu ) {\lt} \infty \).

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

The root of a rooted graph has no parent.

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

Let \(\nu \in \mathcal{D}(\mathbb {R})\) be a compactly supported distribution. Let \(\nu \in \mathcal{D}(\mathbb {R})\) be a compactly supported distribution. Then \(\mathrm{supp} \, \nu \subseteq [-\rho (\nu ), \rho (\nu )]\).

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

Let \(\beta {\gt} 1\) and \(1/\beta _* = 1-1/\beta \). Let \(f \in L^1(\mathbb {T})\) of Fourier coefficients \((c_j)_{j \in \mathbb {Z}}\). Assume \(f' \in L^\beta (\mathbb {T})\). Then,

The adjacency operator is selfadjoint.

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

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

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

Assume \(G\) is regular of degree \(\mathfrak {d}\) and \(V(G)\) is finite. Then, \(\| a|_{\mathbf{1}^\perp }\| = \mathfrak {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\).

The homotopy relation is an equivalence relation.

If \(G\) is regular of degree \(\mathfrak {d}\) and \(V(G)\) is finite, then \(\| a\| =\mathfrak {d}\).

Let \(r \geq 2\) be an integer and \(\mathfrak {d}= 2r\). Then,

and

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

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

Let \((G,r)\) be a rooted tree. Any vertex \(x \in V(G)\) distinct from the root admits a unique parent.

Let \(G\) be a regular graph of degree \(\mathfrak {d}\) with a finite diameter. Then,

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

The graph \(G\) constructed in Definition 1.1.11 is a graph, and \(D(G) = D\).

Let \(q \geq 1\). Let \(w \in \mathbf{W}_r\) be a word of length at most \(q\). There exists a polynomial \(f_w\), of degree at most \(q(1+\log r)\), such that for any \(N \geq q\),

Let \(r \geq 2\) be a integer and \(\mathfrak {d}= 2r\). For any \(\epsilon {\gt} 0\),

Let \(1 {\lt} \beta \leq 2\) and \(1/\beta _* = 1 - 1/\beta \). Let \(f \in L^\beta (\mathbb {T})\) of Fourier coefficients \((c_j)_{j \in \mathbb {Z}}\). Then,

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 \(\mathfrak {d}\)-regular tree. Then \(\| a\| = 2 \sqrt{\mathfrak {d}-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}\).

Let \(x, y \in V(G)\). Any dartwalk from \(x\) to \(y\) is homotopic to a unique nonbacktracking dartwalk, which we denote by \(w_{\mathrm{nb}}\).

The projection map \(\pi : \hat{G} \rightarrow G\) which is defined by \(\pi (w)=\mathrm{end}(w)\) for \(w \in V(\hat G)\) and \(\pi (w,d)=d\) for \((w,d) \in D(\hat G)\) is a covering map.

The universal cover \((\hat{G}, \hat{r})\) of \((G,r)\) is a rooted tree.