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 4.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 4.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 4.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 4.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 4.1.12 using the equivalence relation defined in Definition 4.1.20.

This follows from re-indexing the sum of Lemma 4.1.24 by using Lemma 4.1.21 and Lemma 4.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 4.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 4.1.11, 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 4.1.29 to Lemma 4.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.

Expanding the variance by definition, we get:

use the linearity of expectation to factor out \(\frac{1}{n^{k+2}}\) from both expectations:

using 4.1.12, we can expand and square:

This follows a similar reasoning as in Lemma 4.1.21.

This follows from Lemma 4.1.21.

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

This follows from re-indexing the sum of Lemma 4.2.11 using Lemma 4.2.10.

This follows from Lemma 4.1.11 and the independency of random variables.

By construction of the paths \(w_\mathbf {i}\) and \(w_\mathbf {j}\),

By definition of the counting function \(w_{\mathbf{i} \# \mathbf{j}}(\cdot )\),

Let \((G_{\mathbf{i}\# \mathbf{j}},w_\mathbf {i},w_\mathbf {j})\) be the ordered triple generated by the two \(k\)-indexes \(\mathbf{i}\) and \(\mathbf{j}\). By construction, there are finite number of edges \(e \in E_{\mathbf{i} \# \mathbf{j}}\). Moreover, there are finite number of integer values the counting function \(w_{\mathbf{i} \# \mathbf{j}}(\cdot )\) can take over \(E_{\mathbf{i} \# \mathbf{j}}\). This implies we can choose the maximum element of the set

and therefore \(\lambda \in \mathbb {N}\) so that \(\mathbb {E}(Y_{11}^\lambda ) = \max \mathscr {E}\). Using the fact that \(\mathbb {E}(Z) \leq \mathbb {E}(|Z|)\) for any random variable \(Z\),

This follows an identical reasoning as in Lemma 4.2.19.

By Lemma 4.2.17, we have

By Lemma 4.2.19, there exists \(\lambda _1 \in \mathbb {N}\) so that \(\mathbb {E} (Y_{11}^{w_{\mathbf{i} \# \mathbf{j} (e)}}) \leq r_n\) for every \(e \in E_{\mathbf{i} \# \mathbf{j}}\). On the other hand, by Lemma 4.2.20, there exists \(\lambda _2 \in \mathbb {N}\) so that \(\mathbb {E} (Y_{12}^{w_{\mathbf{i} \# \mathbf{j} (e)}}) \leq r_m\) for every \(e \in E_{\mathbf{i} \# \mathbf{j}}\). Then

Setting \(M_1 := 2k \cdot \max \{ r_{\lambda _1},r_{\lambda _2}\} \) satisfies the problem.

This follows a similar reasoning as in Lemma 4.2.19 with the counting function \(w_\mathbf {i}(\cdot )\).

This follows a similar reasoning as in Lemma 4.2.19 with the counting function \(w_\mathbf {i}(\cdot )\).

This follows an identical reasoning as in Lemma 4.2.19.

Combining the result of Lemma 4.2.21 and Lemma 4.2.24 gives

where \(M_2^{(\mathbf{i})}\) and \(M_2^{(\mathbf{j})}\) are the upper bounds acquired by Lemma 4.2.24 with repsect to \(\mathbf{i}\) and \(\mathbf{j}\), repsectively. Setting \(M_{2k} := \max \{ M_1, M_2^{(\mathbf{i})} \cdot M_2^{(\mathbf{j})} \} \) satisfies the problem.

By construction, every edge in the joined graph \(G_{{i}\# {j}}\) is traversed at least once by the union of the two paths \(w_{i}\) and \(w_{j}\). Suppose that \(e\) is an edge that is traversed only once. This means that \(w_{{i}\# {j}}(e) = 1\), and so it follows that the two values \(w_{i}(e),w_{j}(e)\) are \(\{ 0,1\} \). Hence, the above expansion and the fact that \(\mathbb {E}(Y_{11})=\mathbb {E}(Y_{12})=0\) show that \(\pi (G_{{i}\# {j}},w_{i},w_{j}) = 0\) in this case.

The enumeration of the number of \(2k\)-tuples yielding a certain graph with two walks is the same as in the previous proposition: the structure \((G,w,w')\) specifies the \(2k\)-tuple precisely once we select the \(|G|\) distinct indices for the vertices. So, as before, this ratio becomes

Follows directly.

Now, we have the condition \(w+w'\ge 2\), meaning every edge is traversed at least twice. Since there are \(k\) steps in each of the two paths, this means there are at most \(k\) edges.

Appealing again to 4.1.32, it follows that \(|G|\le k+1\). Hence, \(n(n-1)\cdots (n-|G|+1) \le n^{|G|} \le n^{k+1}\)

The (potentially enormous) number \(B_k=2M_{2k}\cdot \# \mathcal{G}_{k,k}\) is independent of \(n\), and so we have already proved that the variance is \(=O_k(1/n)\).