Dependencies

Given an ordered pair \((G,w) \in \mathcal{G}_k\), we define \(|G|\) to be the number of distinct vertices in the graph \(G\).

Given \((G,w,w')\), let \((\mathbf{i},\mathbf{j})\) be an ordered pair of \(k\)-indexes generated by \(w\) and \(w'\). We define

Given an ordered triple \((G_{\mathbf{i}\# \mathbf{j}},w_\mathbf {i},w_\mathbf {j})\) generated by two \(k\)-indexes \(\mathbf{i}\) and \(\mathbf{j}\), we define

A Dyck path of length \(k\) is a sequence \((d_1,...,d_k) \in \{ \pm 1\} ^k\) such that their partial sum \(\sum _{i=1}^j d_i \geq 0\) and total sum \(\sum _{i = 1}^{k}d_i = 0\). More intuitively, consider a diagonal lattice path from \((0,0)\) to \((k, 0)\) consisting of \(\frac{k}{2}\) ups and \(\frac{k}{2}\) downs such that the path never goes below thw \(x\)-axis.

Define a map \(\psi \) whose input is a Dyck path of order \(k\): \(\mathbf{d} \in \{ \pm 1\} ^k\). Then the output is viewing this Dyck path as a contour reversal of a tree where an up (\(d_i = 1\)) corresponds to visiting a child node and a down (\(d_i = -1\)) corresponds to returning to parent node.

Given a graph \(G_{\mathbf{i} \# \mathbf{j}}\), let \(w_{\mathbf{i} \# \mathbf{j}}(e)\) denote the number of times the edge \(e\) is traversed by either of the two paths \(w_\mathbf {i}\) and \(w_\mathbf {j}\).

Let \(S\) be a multiset of elements in \(\mathcal{X}\) with finite cardinality. Then the associated empirical distribution is the probability measure on \(\mathcal{X}\) defined by

Let \(\mathcal{G}_k\) denote the set of all ordered pairs \((G,w)\) where \(G = (V,E)\) is a connected graph with at most \(k\) vertices, and \(w\) is a closed path covering \(G\) satisfying \(|w| = k\).

Let \((G_\mathbf {i},w_\mathbf {i})\) be an ordered pair generated by some \(k\)-index \(\mathbf{i}\) and \((G,w) \in \mathcal{G}_k\). We say \((G_\mathbf {i},w_\mathbf {i}) = (G,w)\) if and only if there exists a bijection \(\varphi \) from the set of entries \(\mathbf{i}\) onto the set of entries \(\mathbf{j}\) such that

where \(\mathbf{j}\) is a \(k\)-index generated by \((G,w)\).

Let \(\mathcal{G}_{k,w \geq 2}\) be a subset of \(\mathcal{G}_k\) in which the walk \(w\) traverses each edge at least twice.

Given \((G,w) \in \mathcal{G}_k\), we denote \(\mathbf{j}\) as the \(k\)-index generated by \((G,w)\) in the following way. The path \(w\) can be uniquely expressed under the condition of Lemma 4.1.18:

We define \(\mathbf{j} = (j_1,j_2,...,j_{k-1},j_k)\).

Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index. Given graph \(G_{\mathbf{i}}\), define the connecting-edges \(E_{\mathbf{i}}^{c}\) as:

Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index, \(\mathbf{i}=\left(i_1, i_2, \ldots , i_k\right)\). For any edge \(e=\{ i,j\} \) from \(E_{\mathbf{i}}\), we define the edge count \(w_{\mathbf{i}}(e)\) as the number of times each edge \(e\) is traversed, and if \((i, j) \notin E_{\mathbf{i}}\), then \(w_{\mathbf{i}}(\{ i, j\} ) = 0\).

Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index, \(\mathbf{i}=\left(i_1, i_2, \ldots , i_k\right)\). A graph \(G_{\mathbf{i}}\) is defined as follows: the vertices \(V_{\mathbf{i}}\) are the distinct elements of

and the edges \(E_{\mathbf{i}}\) are the distinct pairs among

Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index, \(\mathbf{i}=\left(i_1, i_2, \ldots , i_k\right)\). the path \(w_{\mathbf{i}}\) is the sequence

of edges from \(E_{\mathbf{i}}\)

Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index. Given graph \(G_{\mathbf{i}}\), define the self-edges \(E_{\mathbf{i}}^{s}\) as:

the set of edges where both vertices are the same.

Define a map \(\phi \) whose input is \((G, w) \in \mathcal{G}^{k/2 + 1}_k\). Then for its output, define a sequence \(\mathbf{d}=\mathbf{d}(G,w)\in \{ +1,-1\} ^k\) recursively as follows. Let \(d_1=+1\). For \(1{\lt}j\le k\), if \(w_j\notin \{ w_1,\ldots ,w_{j-1}\} \), set \(d_j=+1\); otherwise, set \(d_j=-1\); then \(\mathbf{d}(G,w) = (d_1,\ldots ,d_k)\). \(\phi ((G,w)) = \mathbf{d}(G,w)\)

Given \(k\)-indices \(\mathbf{i} = (i_1, i_2, \cdots , i_{k}), \mathbf{j} = (j_1, j_2, \cdots , j_{k}) \in [n]^{k}\), and Graphs \(G_{\mathbf{i}}, G_{\mathbf{j}}\), we define the graph union \(G_{\mathbf{i} \# \mathbf{j}}\) as follows:

Given a graph \(G_{\mathbf{i} \# \mathbf{j}}\), let \(E^c_{\mathbf{i} \# \mathbf{j}}\) denote the set of connecting edges.

Let \((G_{\mathbf{i} \# \mathbf{j}},w_\mathbf {i},w_\mathbf {j})\) be an ordered triple generated by two \(k\)-indexes \(\mathbf{i}\) and \(\mathbf{j}\), and let \((G,w,w') \in \mathcal{G}_{k,k}\). We say \((G_{\mathbf{i} \# \mathbf{j}},w_\mathbf {i},w_\mathbf {j}) = (G,w,w')\) if and only \((\mathbf{i},\mathbf{j}) = (\mathbf{i}^*,\mathbf{j}^*)\), where \((\mathbf{i}^*,\mathbf{j}^*)\) is an ordered pair of \(k\)-indexes generated by \((G,w,w')\).

We define \(\mathcal{G}_{k,k}\) to be the set of connected graphs \(G\) with \(\leq 2k\) vertices, together with two paths each of length \(k\) whose union covers \(G\).

\((G,w,w')\in \mathcal{G}_{k,k,w+w'\ge 2}\) if \((G,w,w') \in \mathcal{G}_{k,k}\) and \(w + w' \ge 2\).

Given a graph \(G_{\mathbf{i} \# \mathbf{j}}\), let \(E^s_{\mathbf{i} \# \mathbf{j}}\) denote the set of self-edges.

Given \((G,w,w') \in \mathcal{G}_{k,k}\), we say \((\mathbf{i},\mathbf{j})\) is an ordered pair of \(k\)-indexes generated by \((G,w,w')\) if \(\mathbf{i}\) and \(\mathbf{j}\) are, repsectively, \(k\)-indexes generated by \(w\) and \(w'\) as in Definition 4.1.19.

Let \(\mathbf{i}_\lambda \) and \(\mathbf{j}_\lambda \) be \(k\)-indexes for each \(\lambda =1,2\). We say \((\mathbf{i}_1,\mathbf{j}_1) = (\mathbf{i}_2,\mathbf{j}_2)\) if and only if there exists a bijection \(\varphi _1\) from the set of entries \(\mathbf{i}_1\) onto the set of entries \(\mathbf{i}_2\), and a bijection \(\varphi _2\) from the set of entries \(\mathbf{j}_1\) onto the set of entries \(\mathbf{j}_2\) such that

and

Given any graph \(G=(V,E)\) and a path \(w\), we let \(|w|\) denote the length of \(w\).

Given a path \(w_\mathbf {i}\) generated by some \(k\)-index \(\mathbf{i}\), we let \(|w_\mathbf {i}|\) denote the length of \(w_\mathbf {i}\).

Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index, \(\mathbf{i}=\left(i_1, i_2, \ldots , i_k\right)\). Let \(Y\) be a symmetric matrix. The matrix multi index \(Y_{\mathbf{i}}\) is defined as:

Given \(k\)-indices \(\mathbf{i} = (i_1, i_2, \cdots , i_{k}), \mathbf{j} = (j_1, j_2, \cdots , j_{k}) \in [n]^{k}\), we define the ordered triple \((G_{\mathbf{i} \# \mathbf{j}}, w_{\mathbf{i}}, w_{\mathbf{j}})\) as follows:

• \(G_{\mathbf{i} \# \mathbf{j}}\) is the graph union of the graphs defined by \(\mathbf{i}\) and \(\mathbf{j}\) from definition 4.2.2

• \(w_{\mathbf{i}}\) is the closed walk defined by \(\mathbf{i}\) from definition 4.1.4

• \(w_{\mathbf{i}}\) is the closed walk defined by \(\mathbf{j}\) from definition 4.1.4

Given an ordered pair \((G,w) \in \mathcal{G}_k\), let \(\mathbf{j}\) be the \(k\)-index generated by \((G,w)\). We define

Let \(\mathbf{i} \in [n]^{k}\) be a \(k\)-index, \(\mathbf{i} = (i_1, i_2, \ldots , i_{k})\). Let \(Y\) be a symmetric matrix and let \(\{ Y_{ij}\} _{1\le i\le j}\) be independent random variables, with \(\{ Y_{ii}\} _{i\ge 1}\) identically distributed and \(\{ Y_{ij}\} _{1\le i{\lt}j}\) identically distributed. We define \(\Pi (G_{\mathbf{i}}), w_{\mathbf{i}}\) as follows:

We define \(\nu \) to be the random measure \(\nu (dx) = |x|^k \mu _{\mathbf{X}_n}(dx)\).

Let \(f : \mathbb {R} \times \mathbb {R}_{\geq 0} \times \mathbb {R} \to \mathbb {R}\) denote the real-valued semicircle density defined in Definition 3.1.1. Define the function \(h: \mathbb {R} \to \mathbb {R} \cup \{ \infty \} \) as follows:

Then we define the function \( g : \mathbb {R} \times \mathbb {R}_{\geq 0} \times \mathbb {R} \to [0,\infty ] \subseteq \overline{\mathbb {R}}_{\ge 0}\) by:

The function \(\mathrm{sc} : \mathbb {R} \times \mathbb {R}_{\geq 0} \times \mathbb {R} \rightarrow \mathbb {R}\) defined by

is called the probability density function (pdf) of the semicircle distribution.

The semicircle distribution with mean \(\mu \) and variance \(v\), denoted \(\sigma (\mu , v)\), is the Dirac delta at μ if v = 0; otherwise, it’s the measure with density with respect to the Lebesgue measure given by the semicircle pdf.

Let \(\mathcal{G}^{k/2+1}_k\) to be the set of pairs \((G,w)\in \mathcal{G}_k\) where \(G\) has \(k/2+1\) vertices, contains no self-edges, and the walk \(w\) crosses every edge exactly \(2\) times.

For any \(k\)-indexes \(\mathbf{i}\) and \(\mathbf{j}\), there exists \(M_{2k} \in \mathbb {R}_{\geq 0}\) such that

For any \(k\)-index \(\mathbf{i}\), the connected graph \(G_\mathbf {i} = (V_\mathbf {i},E_\mathbf {i})\) has at most \(k\) vertices. Furthermore

for any sequence \((a_{k})_{k=1}^{\infty } \in \mathbb {R}\), if \(a_{k}\) has:

1. for all \(k \in \mathbb {N}\), \(a_{k} \geq 0\) (nonnegative sequence)

2. for all \(k \in \mathbb {N}\), we have \(a_{k+1} \geq a_{k}\) (strictly increasing sequence)

3. \(\lim _{k\to \infty } a_{k} = 0\)

   then for all \(k \in \mathbb {N}\), we have \(a_{k} = 0\)

\(n(n-1)\cdots (n-|G|+1) \le n^{|G|}\).

#{binary trees with \(\frac{k}{2}\) vertices} is given by Catalan number \(C_{k / 2}\)

Let \(\{ Y_{ij}\} _{1 \leq i \leq j}\) be independent random variables, with \(\{ Y_{ii}\} _{i\geq 1}\) identically distributed and \(\{ Y_{ij}\} _{1 \leq i {\lt} j}\) identically distributed. Suppose that \(r_k = \max \{ \mathbb {E}(|Y_{11}|^k),\mathbb {E}(|Y_{12}|^k)\} {\lt} \infty \) for each \(k\in \mathbb {N}\). Suppose further than \(\mathbb {E}(Y_{ij})=0\) for all \(i,j\). If \(i{\gt}j\), define \(Y_{ij} \equiv Y_{ji}\), and let \(\mathbf{Y}_n\) be the \(n\times n\) matrix with \([\mathbf{Y}_n]_{ij} = Y_{ij}\) for \(1\le i,j\le n\). Let \(\mathbf{X}_n = n^{-1/2}\mathbf{Y}_n\) be the corresponding Wigner matrix. Then, we have:

The sequence \(n\mapsto \frac1n\mathbb {E}\operatorname{Tr}(X_n^k)\) is bounded.

Let \(C_{k}\) be the Catalan number. Then, for all \(k \in \mathbb {N}\), we have:

\(\mathbb {E}[(X - \mu )^{2n + 1}] = 0 \)

\(\mathbb {E}[(X - \mu )^{2n}] = v^n C_n \)

\(\mathbb {E}[(X - \mu )^{2n + 1}] = 0 \)

\(\mathbb {E}[(X - \mu )^{2n}] = v^n C_n \)

Let \(\mathbf{i}_\lambda \) and \(\mathbf{j}_\lambda \) be \(k\)-indexes for each \(\lambda =1,2\) such that \((\mathbf{i}_1,\mathbf{j}_1) = (\mathbf{i}_2,\mathbf{j}_2)\). Then \(\mathbb {E}(Y_{\mathbf{i}_1}Y_{\mathbf{j}_1}) = \mathbb {E}(Y_{\mathbf{i}_1}Y_{\mathbf{j}_2})\).

Let \((G_{\mathbf{i}_1 \# \mathbf{j}_1},w_{\mathbf{i}_1},w_{\mathbf{j}_1})\) and \((G_{\mathbf{i}_2 \# \mathbf{j}_2},w_{\mathbf{i}_2},w_{\mathbf{j}_2})\) be ordered triples generated by their respective ordered pair of \(k\)-indexes, and \((G,w,w') \in \mathcal{G}_{k,k}\), If \((G_{\mathbf{i}_1 \# \mathbf{j}_1},w_{\mathbf{i}_1},w_{\mathbf{j}_2}) = (G,w,w')\) and \((G_{\mathbf{i}_1 \# \mathbf{j}_2},w_{\mathbf{i}_2},w_{\mathbf{j}_2}) = (G,w,w')\), then

let \(k \in \mathbb {N}\) and \(\epsilon {\gt} 0\). Then for any \(b {\gt} 4\),

for \(x {\gt} b {\gt} 4 {\gt} 1 \in \mathbb {R}\), we have \(k \mapsto \frac{1}{\epsilon }(\frac{4}{b})^{k}\) is decreasing to \(0\) as \(k\to \infty \).

\(\mathbb {E}(Y_{12}^2) = t^{\# E}\)

The only graph walks \((G,w,w')\in \mathcal{G}_{k,k}\) with \(|G|=k+1\) must have the edge sets covered by \(w\) and \(w'\) distinct. In other words, if \((G_{\mathbf{i}\# \mathbf{j}},w_\mathbf {i},w_\mathbf {j}) = (G,w,w')\), then the edge sets do not intersect: \(\{ \{ i_1,i_2\} ,\ldots ,\{ i_k,i_1\} \} \cap \{ \{ j_1,j_2\} ,\ldots ,\{ j_k,j_1\} \} =\emptyset \).

\(\psi (\mathbf{d}_k) \subseteq \mathcal{G}^{k/2 + 1}_k\)

\(t^{\# E} = t^{k/2}\)

If \(k\) is even and there exists \(e\) such that \(w(e) \ge 3\), then \(\# E \le \frac{k-1}{2}\).

Given an ordered pair \((G,w) \in \mathcal{G}_{k,w \geq 2}\), we must have \(\# E \leq k/2\).

Given two \(k\)-indexes \(\mathbf{i} = (i_1,...,i_k)\) and \(\mathbf{j} = (j_1,...,j_k)\), suppose there exists a bijection \(\varphi \) from the set of entries of \(\mathbf{i}\) onto the set of entries of \(\mathbf{j}\) such that

Then \(\mathbb {E}(Y_\mathbf {i}) = \mathbb {E}(Y_{\mathbf{j}})\).

Let \(f \in C_{b}(\mathbb {R})\), fix \(\epsilon {\gt} 0\), and \(b {\gt} 4\), and let \(P_{\epsilon }\) be the polynomial from lemma 5.0.19. Then, we have:

\(G \in \mathcal{G}_{k, k}\). If \(|G| = k + 1\), then \(G\) has exactly \(k\) edges.

For any \(k\)-indexes \(\mathbf{i}\), there exists \(M_2 \in \mathbb {R}\) such that

For any \(k\)-indexes \(\mathbf{i}\) and \(\mathbf{j}\), there exists \(M_1 \in \mathbb {R}\) such that

For any \(k\)-index \(\mathbf{i}\), there exists \(\lambda \in \mathbb {N}\) such that

for every \(e \in E_{\mathbf{i} \# \mathbf{j}}\).

For any \(k\)-index \(\mathbf{i}\), there exists \(\lambda \in \mathbb {N}\) such that

for every \(e \in E_\mathbf {i}\).

For any \(k\)-indexes \(\mathbf{i}\) and \(\mathbf{j}\), there exists \(\lambda \in \mathbb {N}\) such that

for every \(e \in E_{\mathbf{i} \# \mathbf{j}}\).

For any \(k\)-indexes \(\mathbf{i}\) and \(\mathbf{j}\), there exists \(\lambda \in \mathbb {N}\) such that

for every \(e \in E_{\mathbf{i} \# \mathbf{j}}\).

Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index, \(\mathbf{i}=\left(i_1, i_2, \ldots , i_k\right)\). Let \(Y\) be a symmetric matrix and let \(\{ Y_{ij}\} _{1\le i\le j}\) be independent random variables, with \(\{ Y_{ii}\} _{i\ge 1}\) identically distributed and \(\{ Y_{ij}\} _{1\le i{\lt}j}\) identically distributed. Then, we have the following:

If \(\left|\int f\, d\mu _{X_n} - \int P_\epsilon \, d\mu _{X_n}\right|{\gt}\epsilon /3\), then \(\int |f-P_\epsilon |\mathbb {1}_{|x|\le b}\, d\mu _{X_n}{\gt}\epsilon /6\) or \(\int |f-P_\epsilon |\mathbb {1}_{|x|{\gt} b}\, d\mu _{X_n}{\gt}\epsilon /6\).

If \(\left|\int f\, d\mu _{X_n} - \int f\, d\sigma _1\right|{\gt}\epsilon \), then \(\left|\int f\, d\mu _{X_n} - \int P_\epsilon \, d\mu _{X_n}\right|{\gt}\epsilon /3, \left|\int P_\epsilon \, d\mu _{X_n} - \int P_\epsilon \, d\sigma _1\right| {\gt}\epsilon /3,\) or \(\left|\int P_\epsilon \, d\sigma _1 - \int f\, d\sigma _1\right|{\gt}\epsilon /3\).

\(\mathbb {P}\left( \left|\int f\, d\mu _{X_n} - \int f\, d\sigma _1\right|{\gt}\epsilon \right) \le \mathbb {P}\left(\left|\int f\, d\mu _{X_n} - \int P_\epsilon \, d\mu _{X_n}\right|{\gt}\epsilon /3\right) + \mathbb {P}\left(\left|\int P_\epsilon \, d\mu _{X_n} - \int P_\epsilon \, d\sigma _1\right| {\gt}\epsilon /3\right) + \mathbb {P}\left(\left|\int P_\epsilon \, d\sigma _1 - \int f\, d\sigma _1\right|{\gt}\epsilon /3\right)\)

\(\mathbb {P}\left( \left|\int f\, d\mu _{\mathrm{X}_n} - \int f\, d\sigma _1\right|{\gt}\epsilon \right) \leq \mathbb {P}\left(\int |f-P_\epsilon |\mathbb {1}_{|x|{\gt} b}\, d\mu _{\mathrm{X}_n}{\gt}\epsilon /6\right)\)

\( \limsup _{n\to \infty } \left(\mathbb {P}\left(\int |f-P_\epsilon |\mathbb {1}_{|x|\le b}\, d\mu _{\mathrm{X}_n}{\gt}\epsilon /6\right) \right) = 0\)

\(\limsup _{n \to \infty }\mathbb {P}\left(\int c|x|^k\mathbb {1}_{|x|\ge b}\, \mu _{\mathrm{X}_n}(dx) {\gt} \epsilon /6\right) = 0 \)

\(\limsup _{n \to \infty } \mathbb {P}\left(\int |f-P_\epsilon | \mathbb {1}_{|x|\ge b}\, d\mu _{\mathrm{X}_n} {\gt} \epsilon /6\right) = 0\)

\(\lim _{n\to \infty }\frac{n^{k/2}}{n(n-1)\cdots (n-k/2+1)} = 1\).

Fix a bounded, continuous function \(f \in C_{b}(\mathbb {R})\), fix \(\epsilon {\gt} 0\), fix \(b {\gt} 4\). Then, there exists a polynomial \(P_{\epsilon }\) such that:

\(G \in \mathcal{G}_{k, k}\). If \(|G| = k + 1\), then \(G \in \mathcal{G}_{k, k}\) is a tree.

In the set \(\mathcal{G}_{k,k,w+w'\ge 2}\), edge count is at most \(k\).

For any \((G_{\mathbf{i}\# \mathbf{j}},w_\mathbf {i},w_\mathbf {j}) \in \mathcal{G}_{k,k}\), with \(k + 1\) vertices, \(\pi (G_{\mathbf{i}\# \mathbf{j}},w_\mathbf {i},w_\mathbf {j}) = 0\)

For \((G, w, w') \in \mathcal{G}_{k,k,w+w'\ge 2}\), \(\# \left\{ (i,{j})\in [n]^{2k}\colon (G_{i\# j},w_{i},w_{j}) = (G,w,w')\right\} = n(n-1)\cdots (n-|G|+1)\).

\(\phi ((G,w)) = \mathbf{d}(G,w) \subseteq \mathcal{D}_k\), where \(\mathcal{D}_k\) denotes the set of Dyck path of order \(k\).

\(|G_k|\) is finite.

Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index, \(\mathbf{i}=\left(i_1, i_2, \ldots , i_k\right)\). Let \(Y\) be a symmetric matrix. Then, we have the following:

\((G, w, w') \in \mathcal{G}_{k, k}\) and \(|G| = k + 1\), then for a common edge it is impossible that \(w(e) = w'(e) = 1\).

for \(x {\gt} b {\gt} 4 {\gt} 1 \in \mathbb {R}\), we have \(k \mapsto \lim \sup _{n\to \infty }\mathbb {P} (\int _{|x| {\gt} b}|x|^{k}\mu \mathbf{x}_{n} (dx))\) is increasing with \(k\).

for \(x {\gt} b {\gt} 4 {\gt} 1 \in \mathbb {R}\), we have \(k \mapsto \mathbb {P} (\int _{|x| {\gt} b}|x|^{k}\mu \mathbf{x}_{n} (dx))\) is increasing with \(k\).

for \(x {\gt} b {\gt} 4 {\gt} 1 \in \mathbb {R}\), we have \(k \mapsto |x|^{k}\) is increasing with \(k\).

For all \(\mu \in \mathbb {R}\) and \(v \in \mathbb {R}_{\ge 0}\), semicircleReal is a probability measure.

Given a mean \(\mu \in \mathbb {R}\) and a variance \(v \in \mathbb {R}_{\geq 0}\), the pdf \(\mathrm{sc} : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution with mean \(\mu \) and variance \(v\) is integrable.

If \(X \sim \sigma (\mu , v)\), then its expectation

Given a mean \(\mu \in \mathbb {R}\) and a nonzero variance \(v \in \mathbb {R}_{{\gt} 0}\), the integral of the pdf \(\mathrm{sc} : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution with mean \(\mu \) and variance \(v\) equals \(1\).

Let \( f : \mathbb {R} \to E \) be a function where \( E \) is a normed vector space over \(\mathbb {R}\). For the semicircle distribution with mean \(\mu \in \mathbb {R}\) and variance \( v {\gt} 0 \), we have:

Given \((G,w) \in \mathcal{G}_k\), we have

for \(x {\gt} b {\gt} 4 {\gt} 1 \in \mathbb {R}\), the sequence \(k \mapsto \lim \sup _{n\to \infty }\mathbb {P} (\int _{|x| {\gt} b}|x|^{k}\mu \mathbf{x}_{n} (dx))\) has:

If \(v {\gt} 0\), then the total integral of \(\bar{sc}\) with respect to Lebesgue measure is 1:

Given a mean \(\mu \in \mathbb {R}\) and a nonzero variance \(v \in \mathbb {R}_{{\gt} 0}\), the lower Lebesgue integral of the p.d.f. \(\mathrm{sc} : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution with mean \(\mu \) and variance \(v\) equals \(1\).

Let \(Y\) be an \(n\times n\) matrix and \(k \in \mathbb {N}\). Then, for each \((i, j)\)-th entry of \(Y^{k}\), we have:

Let \(Y\) be an \(n\times n\) matrix and \(k \in \mathbb {N}\). Then, the trace of \(Y^{k}\) is given by:

The function \( x \mapsto \bar{sc}(\mu ,v,x) \) is measurable for all \( \mu \in \mathbb {R} \), \( v \in \mathbb {R}_{\ge 0} \).

Given a mean \(\mu \in \mathbb {R}\) and a variance \(v \in \mathbb {R}_{\geq 0}\), the pdf \(\mathrm{sc} : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution with mean \(\mu \) and variance \(v\) is measurable.

All the moments of a real semicircle distribution are finite. That is, the identity is in \(L_p\) for all finite \(p\)

Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index, \(\mathbf{i}=\left(i_1, i_2, \ldots , i_k\right)\). Let \(Y\) be a symmetric matrix. Then, we have the following:

let \(k \in \mathbb {N}\) and \(\epsilon {\gt} 0\). then for any \(b {\gt} 4\),

\((G, w, w') \in \mathcal{G}_{k, k}\) and \(|G| = k + 1\). Then two walks have no shared edges \(e\) which they have traversed.

If \(v {\gt} 0\), then the semicircle distribution has no atoms.

for \(x {\gt} b {\gt} 4 {\gt} 1 \in \mathbb {R}\), we have \(k \mapsto \lim \sup _{n\to \infty }\mathbb {P} (\int _{|x| {\gt} b}|x|^{k}\mu \mathbf{x}_{n} (dx)) \geq 0\) for all \(k \in \mathbb {N}\).

Suppose \(k\) odd. Then, \(\frac{n(n-1)\cdots (n-|G|+1)}{n^{k/2+1}} \le \frac{1}{\sqrt{n}}\).

Suppose \(k\) odd. Then, \(|G| \le \frac{k}{2} + \frac{1}{2}\).

\((G, w, w') \in \mathcal{G}_{k, k}\) and \(|G| = k + 1\), then it can only be the case that \(w(e) = 2, w'(e) = 0\), or \(w(e) = 0, w'(e) = 2\) .

\(\mathbb {P}\left(\left|\int P_\epsilon \, d\sigma _1 - \int f\, d\sigma _1\right|{\gt}\epsilon /3\right)\) is identically zero.

Given an ordered pair \((G,w) \in \mathcal{G}_k\), suppose there exists an edge \(e \in E\) in which it is traversed only once in the walk \(w\). Then

\( \mathbb {P}\left(\int |f-P_\epsilon | \mathbb {1}_{|x|\ge b}\, d\mu _{\mathrm{X}_n} {\gt} \epsilon /6\right) \le \mathbb {P}\left(\int c|x|^k\mathbb {1}_{|x|\ge b}\, \mu _{\mathrm{X}_n}(dx) {\gt} \epsilon /6\right) \)

\(\Pi (G,w) = \prod _{e_c\in E^c} \mathbb {E}(Y_{12}^{w(e_c)})\)

The Radon–Nikodym derivative of the semicircle measure \(\sigma (\mu , v)\) with respect to the Lebesgue measure is almost everywhere equal to the semicircle probability density function \(SC(\mu \), \(v)\).

\( \limsup _{n \to \infty } \left(\mathbb {P}\left(\left|\int P_\epsilon \, d\mu _{\mathrm{X}_n} - \int P_\epsilon \, d\sigma _1\right| {\gt}\epsilon /3\right) \right) = 0 \)

For all \(\mu \in \mathbb {R} , v \in \mathbb {R}_{\geq 0}\), the extended pdf. \( \bar{sc} : \mathbb {R} \to [0,\infty ]\) satisfies:

For all \(\mu , x \in \mathbb {R}\), and \(v \in \mathbb {R}_{\ge 0}\), we have:

For all \( \mu , x \in \mathbb {R} \), and \( v \in \mathbb {R}_{\ge 0} \), the extended pdf is finite:

If \(v {\gt} 0\), then for all \(\mu , x \in \mathbb {R}\), the extended pdf is nonnegative:

If the variance \(v\) is zero, then the extended pdf. is identically zero:

For any pdf \(\mathrm{sc} : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution, the following relation is satisfied:

for any \(\mu \in \mathbb {R}\), \(v \in \mathbb {R}_{\geq 0}\), and \(x,y \in \mathbb {R}\).

Given a mean \(\mu \in \mathbb {R}\) and a variance \(v \in \mathbb {R}_{\geq 0}\), the pdf \(\mathrm{sc} : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution with mean \(\mu \) and variance \(v\) is given by

For any pdf \(\mathrm{sc} : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution, the following relation is satisfied:

for any \(\mu \in \mathbb {R}\), \(v \in \mathbb {R}_{\geq 0}\), \(x \in \mathbb {R}\), and nonzero \(c \in \mathbb {R}\).

For any pdf \(\mathrm{sc} : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution, the following relation is satisfied:

for any \(\mu \in \mathbb {R}\), \(v \in \mathbb {R}_{\geq 0}\), \(x \in \mathbb {R}\), and nonzero \(c \in \mathbb {R}\).

The pdf of the semicircle distribution is always nonnegative.

For any pdf \(\mathrm{sc} : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution, the following relation is satisfied:

for any \(\mu \in \mathbb {R}\), \(v \in \mathbb {R}_{\geq 0}\), and \(x,y \in \mathbb {R}\).

If the variance \(v\) is given to be zero, then the pdf of the semicircle distribution is the function that is identically zero.

For a semicircle distribution with mean \(\mu \) and variance \(v {\gt} 0\), the measure \(\sigma (\mu , v)\) is absolutely continuous with respect to the Lebesgue measure.

Given a real random variable \(X \sim \sigma (\mu , v)\) then for a constant \(y \in \mathbb {R}\), \(X + y \sim \sigma (\mu + y, v)\)

For a semicircle measure with mean \(\mu \) and variance \(v {\gt} 0\), the measure of any measurable set \(s\) equals the Lebesgue integral over \(s\) of the semicircle probability density function at x.

For any mean \(\mu \in \mathbb {R}\), any variance \(v {\gt} 0\), and any measurable set \(s\) of real numbers, the semicircle distribution measure of the set \(s\) equals the extended nonnegative real number version (ENNReal.ofReal) of the integral of the semicircle probability density function over s.

Given a real random variable \(X \sim \sigma (\mu , v)\) then for a constant \(y \in \mathbb {R}\), \(y + X \sim \sigma (\mu + y, v)\)

Given a real random variable \(X \sim \sigma (\mu , v)\), then for a constant \(c \in \mathbb {R}\), \(cX \sim \sigma (c\mu , c^2v)\)

Given semicircular measure \(\sigma (\mu , v)\) with mean \(\mu \) and variance \(v\), then for any constant \(y \in \mathbb {R}\), the pushforward of \(\sigma (\mu , v)\) under the map \(x \mapsto x + y\) is again a semicircular measure \(\sigma (\mu + y, v)\).

Given semicircular measure \(\sigma (\mu , v)\) with mean \(\mu \) and variance \(v\), then for any constant \(y \in \mathbb {R}\), the pushforward of \(\sigma (\mu , v)\) under the map \(x \mapsto y + x\) is again a semicircular measure \(\sigma (\mu + y, v)\).

Given semicircular measure \(\sigma (\mu , v)\) with mean \(\mu \) and variance \(v\), then for any constant \(c \in \mathbb {R}\), the pushforward of \(\sigma (\mu , v)\) under the map \(x \mapsto c * x\) is again a semicircular measure \(\sigma (c\mu , c^2v)\).

Given semicircular measure \(\sigma (\mu , v)\) with mean \(\mu \) and variance \(v\), then for any constant \(y \in \mathbb {R}\), the pushforward of \(\sigma (\mu , v)\) under the map \(x \mapsto y - x\) is again a semicircular measure \(\sigma (y - \mu , v)\).

Given semicircular measure \(\sigma \) with mean \(\mu \) and variance \(v\), then for any constant \(c \in \mathbb {R}\), the pushforward of \(\sigma (\mu , v)\) under the map \(x \mapsto x * c\) is again a semicircular measure \(\sigma (c\mu , c^2v)\).

Given semicircular measure \(\sigma (\mu , v)\) with mean \(\mu \) and variance \(v\), the pushforward of \(\sigma (\mu , v)\) under the map \(x \mapsto -x\) is again a semicircular measure \(\sigma (- \mu , v)\).

Given semicircular measure \(\sigma (\mu , v)\) with mean \(\mu \) and variance \(v\), then for any constant \(y \in \mathbb {R}\), the pushforward of \(\sigma (\mu , v)\) under the map \(x \mapsto x - y\) is again a semicircular measure \(\sigma ( \mu - y, v)\).

Given a real random variable \(X \sim \sigma (\mu , v)\), then for a constant \(c \in \mathbb {R}\), \(Xc \sim \sigma (c \mu , c^2v)\)

If \(v \neq 0\), then the definition the semicircle distribution is defined as the measure with density with respect to the Lebesgue measure given by the semicircle pdf.

If the variance is 0, then the semicircle distribution is exactly the Dirac measure at \(\mu \).

Elements of \(G_k^{k/2+1}\) have \(|E| = k/2\).

Elements of \(G_k^{k/2+1}\) are trees.

Given a mean \(\mu \in \mathbb {R}\) and a variance \(v \in \mathbb {R}_{\geq 0}\), the pdf \(\mathrm{sc} : \mathbb {R} \rightarrow \mathbb {R}\) of the semicircle distribution with mean \(\mu \) and variance \(v\) is strongly measurable.

\(G_{\mathbf{i} \# \mathbf{j}}\) is a tree, then its subgraph \(G_{\mathbf{i}}\) and \(G_{\mathbf{j}}\) are also trees.

Let \( \mu \in \mathbb {R} \) and \( v \in \mathbb {R}_{{\gt} 0} \). Then the support of the extended pdf is

Let \( \mu \in \mathbb {R} , v \in \mathbb {R}_{\ge 0}\), and \(x \in \mathbb {R} \). Then the real value recovered from the extended semicircle PDF satisfies:

Let \(\mathbf{Y}_{n}\) be an \(n \times n\) symmetric matrix with independent entries, where \(\{ Y_{ij}\} _{1\le i\le j}\) are independent random variables, with \(\{ Y_{ii}\} _{i\ge 1}\) identically distributed and \(\{ Y_{ij}\} _{1\le i{\lt}j}\) identically distributed. Then, for any \(k\)-index \(\mathbf{i} \in [n]^k\), we have:

\((G, w, w') \in \mathcal{G}_{k, k}\). If \(|G| = k + 1\), then for a common edge \(e\) between the two walks, \(w(e) + w'(e) =2\). In other words, every edge is traversed exactly twice.

Let \(\mathbf{Y}_{n}\) be an \(n \times n\) symmetric matrix with independent entries, where \(\{ Y_{ij}\} _{1\le i\le j}\) are independent random variables, with \(\{ Y_{ii}\} _{i\ge 1}\) identically distributed and \(\{ Y_{ij}\} _{1\le i{\lt}j}\) identically distributed, and let \(\mathbf{X}_{n} = n^{-1 / 2}\mathbf{Y}_{n}\) be the corresponding Wigner matrix. Then:

If \(X \sim \sigma (\mu , v)\), then its variance \(Var(X) = v\)

The variance of a real semicircle distribution with parameter \((\mu , v)\) is its variance parameter \(v\)

For any graph \(G = (V, E)\) appearing in the sum in Equation 4.8, \(|G| \le k/2 + 1\).

\(\prod _{e_c\in E^c} \mathbb {E}(Y_{12}^{w(e_c)}) = \prod _{e_c\in E^c} \mathbb {E}(Y_{12}^2)\)

Given \((G,w) \in \mathcal{G}_k\), let us denote the path \(w\) by

Then we can choose the smallest integer appearing in \(\{ i_1,i_2\} \cap \{ i_{2k-1},i_{2k}\} \) such that \(w\) takes the form

Let \(k\) be even and let \(\mathcal{D}_k\) denote the set of Dyck paths of length \(k\)

Then \((G,w)\mapsto {d}(G,w)\) is a bijection \(\mathcal{G}_k^{k/2+1}\to \mathcal{D}_k\).

Let \(k \in \mathbb {N}\) and \(\epsilon {\gt} 0\). Then for any \(b {\gt} 4\),

where \(|\mathcal{D}_k|\) denotes the number of Dyke paths of length \(k\) while \(C_k\) is the \(k\)th Catalan number.

Let \((G,w)\in \mathcal{G}_k\) with \(w\ge 2\), and suppose \(k\) is even. If there exists an edge \(e\) in \(G\) with \(w(e)\ge 3\), then \(|G|\le k/2\).

Let \((G,w)\in \mathcal{G}_k\) with \(w\ge 2\), and suppose \(k\) is even. If there exists a self-edge \(e\in E_s\) in \(G\), then \(|G|\le k/2\).

\(|\sum _{\mathcal{G}_{k}, w \ge 2} - \sum _{\mathcal{G}_k^{k/2+1}}| \le |\mathcal{G}_k|/n\).

Let \(\{ Y_{ij}\} _{1\le i\le j}\) be independent random variables, with \(\{ Y_{ii}\} _{i\ge 1}\) identically distributed and \(\{ Y_{ij}\} _{1\le i{\lt}j}\) identically distributed. Suppose that \(r_k = \max \{ \mathbb {E}(|Y_{11}|^k),\mathbb {E}(|Y_{12}|^k)\} {\lt}\infty \) for each \(k\in \mathbb {N}\). Suppose further than \(\mathbb {E}(Y_{ij})=0\) for all \(i,j\) and set \(t=\mathbb {E}(Y_{12}^2)\). If \(i{\gt}j\), define \(Y_{ij} \equiv Y_{ji}\), and let \(\mathbf{Y}_n\) be the \(n\times n\) matrix with \([\mathbf{Y}_n]_{ij} = Y_{ij}\) for \(1\le i,j\le n\). Let \(\mathbf{X}_n = n^{-1/2}\mathbf{Y}_n\) be the corresponding Wigner matrix. Then

Let \(\{ Y_{ij}\} _{1 \leq i \leq j}\) be independent random variables, with \(\{ Y_{ii}\} _{i\geq 1}\) identically distributed and \(\{ Y_{ij}\} _{1 \leq i {\lt} j}\) identically distributed. Suppose that \(r_k = \max \{ \mathbb {E}(|Y_{11}|^k),\mathbb {E}(|Y_{12}|^k)\} {\lt} \infty \) for each \(k\in \mathbb {N}\). Suppose further than \(\mathbb {E}(Y_{ij})=0\) for all \(i,j\). If \(i{\gt}j\), define \(Y_{ij} \equiv Y_{ji}\), and let \(\mathbf{Y}_n\) be the \(n\times n\) matrix with \([\mathbf{Y}_n]_{ij} = Y_{ij}\) for \(1\le i,j\le n\). Let \(\mathbf{X}_n = n^{-1/2}\mathbf{Y}_n\) be the corresponding Wigner matrix. Then

Suppose \(k\) odd. Then, \(\lim _{n\to \infty } \frac{1}{n}\mathbb {E}\operatorname{Tr}(X_n^k) = 0\).

\(\Pi (G,w) = t^{k/2}\).

\(\lim _{n\to \infty }\mathbb {E}\operatorname{Tr}(X_n^k) = \sum _{(G,w)\in \mathcal{G}^{k/2+1}_k} \Pi (G,w)\)

\(\lim _{n\to \infty } \mathbb {E}\operatorname{Tr}(X_n^k) = t^{k/2}\cdot \# \mathcal{G}_k^{k/2+1}\)

\(\frac1n\mathbb {E}\operatorname{Tr}(X_n^k) = \sum _{(G,w)\in \mathcal{G}^{k/2+1}_k} \Pi (G,w) \cdot \frac{n(n-1)\cdots (n-|G|+1)}{n^{k/2+1}} + O_k(n^{-1})\)

Let \(G=(V,E)\) be a connected finite graph. Then, \(|G|=\# V\le \# E+1\).

Let \(G=(V,E)\) be a connected finite graph. Then, \(|G|=\# V=\# E+1\) if and only if \(G\) is a plane tree.

Let \(\mathrm{X}_n=n^{-1/2}\mathrm{Y}_n\) be a sequence of Wigner matrices, with entries satisfying \(\mathbb {E}(Y_{ij})=0\) for all \(i,j\) and \(\mathbb {E}(Y_{12}^2)=t\). Then the empirical law of eigenvalues \(\mu _{\mathrm{X}_n}\) converges in probability to \(\sigma _t\) as \(n\to \infty \). Precisely: for any \(f\in C_b(\mathbb {R})\) (continuous bounded functions) and each \(\epsilon {\gt}0\),

Theorem 2.4. (Unsure if it goes in this doc.)