We proceed by induction on \(k\).

Our base case is \(k=1\), then:

which matches the formula since the summation over zero indices just gives the term \(Y_{ij}\).

Our inductive step is to assume that the formula holds for some \(k \ge 1\), i.e.,

We must show that it holds for \(k + 1\). Note that:

Thus, the formula holds for \(k + 1\).

By induction, the result holds for all \(k \ge 1\).

We can use the result from Lemma 3.1.1 to compute the trace of \(Y^k\):

We see from definition \(\ref{def:graph_path}\) that the path is defined as:

if we use each each edge \(w \in w_{\mathbf{i}}\), due to symmetry, we can write the product:

as required.

Using lemma 3.1.7, we already have that \(Y_{\mathbf{i}} = \prod _{w \in w_{\mathbf{i}}} Y_{w}\). We consider the following cases for each \((i, j)\):

\((i, j) \notin w_{\mathbf{i}}\): In this case, the entry \(Y_{ij}^{w_{\mathbf{i}}(\{ i, j\} )} = 1\), making no contribution to the product.

\((i, j) \in w_{\mathbf{i}}\): In this case, the entry \(Y_{ij}^{w_{\mathbf{i}}(\{ i, j\} )}\) is equal to the number of times the unordered edge \(\{ i, j\} \) appears in the path \(w_{\mathbf{i}}\).

These two cover all possibilities, so putting them together we obtain

Indeed, if \((i,j)\notin w_{\mathbf i}\) then \(w_{\mathbf i}(\{ i,j\} )=0\) and the corresponding factor contributes \(Y_{ij}^{0}=1\), and if \((i,j)\in w_{\mathbf i}\) (hence also \((j,i)\) if \(j{\lt}i\)), the exponent \(w_{\mathbf i}(\{ i,j\} )\) counts exactly how many times the unordered edge \(\{ i,j\} \) appears in the walk, so the factor is \(Y_{ij}^{\, w_{\mathbf i}(\{ i,j\} )}\).

Because every unordered pair \(\{ i,j\} \) with \(1\le i\le j\le n\) is covered by one of these two cases and the product lists each edge exactly once.

Because each \(Y_{ij}\) is independent, we can write:

using lemma 3.1.8. Consider the following cases for each \((i, j)\) (we assume each \((i, j) \in w_{\mathbf{i}}\) since if they aren’t, then \(w_{\mathbf{i}}(i, j) = 0\) and this contributes nothing to the product):

\(\mathbf{i = j}\): in this case, we have \(Y_{ij} = Y_{ii}\), and therefore the edge \((i, i) \in E_{\mathbf{i}}^{s}\). Since each \(Y_{ii}\) is identically distributed for all \(i\), we have:

so the factor in the product above becomes \(\mathbb {E}(Y_{ij}^{w_{\mathbf{i}}(\{ i, j\} )}) = \mathbb {E}(Y_{11}^{w_{\mathbf{i}}(i, i)})\).

\(\mathbf{i {\lt} j}\): in this case, we have \(Y_{ij} \in E_{\mathbf{i}}^{c}\). Since each non diagonal entry \(Y_{ij}\) is identically distributed for all \(i \neq j\) (and by symmetry \(Y_{ij} = Y_{ji}\)), we have:

so the factor in the product above becomes \(\mathbb {E}(Y_{ij}^{w_{\mathbf{i}}(\{ i, j\} )}) = \mathbb {E}(Y_{12}^{w_{\mathbf{i}}(i, j)})\).

Plugging both of these cases into the earlier product over \(E_{\mathbf{i}}^{c}\) and \(E_{\mathbf{i}}^{s}\), we have:

as required.

Foremost, since the number of vertices of the graph \(G_\mathbf {i}\) are the number of distinct elements of the \(k\)-index \(\mathbf{i}\), it clearly follows that \(\# V_\mathbf {i} \leq k\). On the other hand, recall that each \(w_i(e)\) denotes the number of times the edge \(e \in E_\mathbf {i}\) is traversed by the path \(w_\mathbf {i}\). Since \(|w_\mathbf {i}| = k\) by the construction of \(w_\mathbf {i}\), it follows that

There is at least one way and at most two ways to express \(w\) in the form of Equation ??. This follows from the fact that detemining the first entry \(j_1\) (for which we have two choices of \(i_1\) or \(i_2\)) of a path completely determines the remaining entries \(j_2,j_3,...,j_k\). Note that this also implies that we can not express express \(w\) in two ‘distinct’ forms of Equation ?? by starting with the same choice of \(j_1\).

Given \(Y_\mathbf {i} = Y_{i_1 i_2}Y_{i_2 i_3} \cdots Y_{i_{k-1} i_k}Y_{i_k i_1}\), we have

Observe that \(\{ i_{\lambda _l},i_{\lambda _{l+1}} \} \) is a singleton and only if \(\{ \varphi (i_{\lambda _l}),\varphi (i_{\lambda _{l+1}}) \} \) is a singleton. The fact that \(\{ i_{\lambda _l},i_{\lambda _{l+1}} \} = \{ i_{\lambda _\mu },i_{\lambda _{\mu +1}} \} \) if and only if \(\{ \varphi (i_{\lambda _l}),\varphi (i_{\lambda _{l+1}}) \} = \{ \varphi (i_{\lambda _\mu }),\varphi (i_{\lambda _{\mu +1}}) \} \) completes the proof.

By the way the equivalence relation is defined in Definition 3.1.17, the fact that there are \(n (n - 1) \cdots (n -|G| + 1)\) ways to assign \(|G|\) distinct values from \([n]\) into the indices \(i_1,...,i_{|G|}\) completes the proof.

This follows from ‘partitioning’ the summation appearing in Lemma 3.1.12 using the equivalence relation defined in Definition 3.1.20.

This follows from re-indexing the sum of Lemma 3.1.24 by using Lemma 3.1.21 and Lemma 3.1.23.

Combining with the renormalization factor \(n^{-1}\) of Proposition ?? gives

Substituting the term \(\mathbb {E}\operatorname{Tr}(\mathbf{Y}_\mathbf {i}^k)\) with the expression in Equation 3.1.26 gives

Let \((G,w) \in \mathcal{G}_k\) and let \(\mathbf{j}\) be the \(k\)-index generated by \((G,w)\). Suppose there exists an edge \(e \in E_\mathbf {j}\) such that \(w_\mathbf {j}(e) = 1\). This means, in Lemma ??, a singleton term \(\mathbb {E}(Y_{ij}^{w_\mathbf {j}(e)}) = \mathbb {E}(Y_{ij})\) appears. The rest of the proof follows from the assumption of Proposition ?? that \(\mathbb {E}(Y_{ij}) = 0\) for every \(i\) and \(j\).

This follows from applying the result of Lemma 3.1.29 to Lemma 3.1.27.

Since \(|w| = k\), if each edge in \(G\) is traversed at least twice, then by construction of \(w\) the number of edges is at most \(k/2\).

\(|G|= \# V\le \# E+1\): proof by induction on \(\# V\). Base case \(\# V = 1\) is obvious. For each additional vertex, the number of edges must increase by at least one for the graph to remain connected.

\(|G|=\# V=\# E+1\) if \(G\) is a plane tree is already in Lean: SimpleGraph.IsTree.card_edgeFinset.

\(G\) is a plane tree if \(|G|=\# V=\# E+1\): proof by induction on \(\# V\). Base case \(\# V = 1\) has no edges. Assume \(\# V = \# E + 1\) for \(\# V = k\). Now, consider a tree with \(\# V = k+1\) nodes. Removing a leaf node leaves us with a tree with \(\# V = k\) nodes. By IH, there are \(k - 1\) edges. So including the leaf node gives us \(k\) edges.

Follows directly from earlier lemmas (replacing \(\# E\) with \(k/2\)).

Use Nat.ascFactorial_eq_div. Or prove directly.

The only part that depends on \(n\) is the big fraction. Since we only care about \(w \ge 2\), \(|G| \le k/2 + 1\). Use the fact that the product \(n(n-1)\cdots (n-|G|+1)\) is asymptotically equal to \(n^{|G|}\) to conclude that the fraction is bounded and doesn’t explode.

Since \(|G|\le \# E+1 \le k/2+1\) and \(|G|\) is an integer, it follows that \(|G|\le (k-1)/2+1 = k/2 + 1/2\). Hence, in this case, all the terms in the (finite \(n\)-independent) sum in Equation 4.8 are \(O(n^{-1/2})\)

Since the graph \(G = (V,E)\) contains a loop, it is not a tree; it follows from Exercise ?? that \(\# V {\lt} \# E+1\). But \(w\ge 2\) implies that \(\# E\le k/2\), and so \(\# V {\lt} k/2+1\), and so \(|G| = \# V \le k/2\).

The sum of \(w\) over all edges \(E\) in \(G\) is \(k\). Hence, the sum of \(w\) over \(E\setminus \{ e\} \) is \(\le k-3\). Since \(w\ge 2\), this means that the number of edges excepting \(e\) is \(\le (k-3)/2\); hence, \(\# E \le (k-3)/2+1 = (k-1)/2\). By the result of a previous lemma, this means that \(\# V \le (k-1)/2+1 = (k+1)/2\). Since \(k\) is even, it follows that \(|G|=\# V \le k/2\).

Follows from definition.

If \(|G| {\lt} k/2 + 1\), then there is at least one more \(n\) in the denominator than the numerator.

some lower bound stuff + other stuff?

Proof: use the fact that \(|G|=k/2+1\) and \(n(n-1)\cdots (n-k/2+1) \sim n^{k/2+1}\). Limit as n approaches infinity of \(O(n^{-1/2})\) is 0.

Follows directly.

Follows directly.

Follows directly.

Follows directly.

Proof slightly outdated.

Let \((G,w)\in \mathcal{G}^{k/2+1}_k\). Since \(w\) traverses each edge exactly twice, the number of edges in \(G\) is \(k/2\). Since the number of vertices is \(k/2+1\), Exercise (Prop) 4.3.1 shows that \(G\) is a tree. In particular there are no self-edges (as we saw already in Proposition 4.4).

1st equality: definition right after equation 4.4 in notes 2nd equality: proposition 4.4 (w < 3) and previous lemma (w = 1 –> 0) 3nd equality: definition (from main proposition) 4th equality: number of edges is k/2.

Follows directly from 4.7.5 and 4.8.