4 LoopWalks
Given a simple graph \(G\), a LoopWalk is a walk on \(G\) that is allowed to have consecutive visits to the same vertex (i.e. loops).
Note the general definition of a LoopWalk does not require it to be a closed walk. However, we will only need to work with closed LoopWalks in the proof of the semicircle law, so when we write LoopWalk we mean closed LoopWalk below.
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 closed LoopWalk on the complete graph \(K_n\) given by
Given a LoopWalk \(w_\mathbf {i}=((i_1, i_2),(i_2, i_3), \ldots ,(i_{k-1}, i_k),(i_k, i_1))\) on \(K_n\), let \(E_\mathbf {i}= \{ \{ i_1, i_2\} ,\{ i_2, i_3\} , \ldots ,\{ i_{k-1}, i_k\} , \{ i_k, i_1\} \} \) be the set of edges traversed by \(w_{\mathbf{i}}\) (this includes loops).
Given a LoopWalk \(w_\mathbf {i}=((i_1, i_2),(i_2, i_3), \ldots ,(i_{k-1}, i_k),(i_k, i_1))\) on \(K_n\), let \(V_\mathbf {i}= \{ i_1, i_2, \dots , i_k\} \) be the set of vertices visited by \(w_{\mathbf{i}}\).
Let \(w_{\mathbf{i}}\) be a LoopWalk. Then, \(|V_{\mathbf{i}}|\le |E_{\mathbf{i}}|+1\).
\(|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.
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\} \) of \(K_n\) traversed in \(w_{\mathbf{i}}\), we define the edge count \(w_{\mathbf{i}}(e)\) as the number of times edge \(e\) is traversed, and if \(\{ i, j\} \notin w_{\mathbf{i}}\), then \(w_{\mathbf{i}}(\{ i, j\} ) = 0\).
Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index with walk \(w_{\mathbf{i}}\) on \(K_n\). Define the self-edges \(E_{\mathbf{i}}^{s}\) as:
i.e the set of loops in \(w_{\mathbf{i}}\).
Let \(\mathbf{i} \in [n]^k\) be a \(k\)-index with walk \(w_{\mathbf{i}}\) on \(K_n\). Define the connecting-edges \(E_{\mathbf{i}}^{c}\) as:
Given a LoopWalk \(w_\mathbf {i}\) generated by some \(k\)-index \(\mathbf{i}\), we let \(|w_\mathbf {i}|\) denote the length of \(w_\mathbf {i}\).
For any \(k\)-index \(\mathbf{i}\), \(|V_\mathbf {i}| \leq k\) and
Foremost, since the number of vertices 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
Given two LoopWalks \(w_{\mathbf{j}} = ((j_1, j_2), \dots (j_{k-1}, j_k), (j_k, j_1))\) and \(w_{\mathbf{i}}=((i_1, i_2), \dots (i_{k-1}, i_k), (i_k, i_1))\) on \(K_n\), we say that \(w \sim v\) if there exists a permutation \(\sigma \in S_n\) such that \(w_{\sigma (\mathbf{j})} \equiv ((\sigma (j_1), \sigma (j_2)), \dots (\sigma (j_{k-1}), \sigma (j_k)), (\sigma (j_{k}), \sigma (j_1))) = w_{\mathbf{i}}\).
If \(w_{\mathbf{i}} \sim w_{\mathbf{j}}\), then \(|V_{\mathbf{i}}| = |V_{\mathbf{j}}|\).
If \(w_{\mathbf{i}} \sim w_{\mathbf{j}}\), then \(|E_{\mathbf{i}}| = |E_{\mathbf{j}}|\).
If \(w_{\mathbf{i}} \sim w_{\mathbf{j}}\), then the set of edge counts for \(w_{\mathbf{i}}\) is the same as \(w_{\mathbf{j}}\). In other words, \(\{ w_{\mathbf{i}}(i_1, i_2) , \dots , w_{\mathbf{i}}(i_{k-1}, i_k)\} = \{ w_{\mathbf{j}}(j_1, j_2) , \dots , w_{\mathbf{j}}(j_{k-1}, j_k)\} \) as sets.
Let \(\mathcal{G}_k\) denote the set of all equivalence classes under 4.0.11 of walks of length \(k\) on \(K_n\).
\(|\mathcal{G}_k|\) is finite.
Requires proof.
We will denote the equivalence classes in \(\mathcal{G}_k\) with \(w\), and particular representatives of the equivalence classes will be denoted \(w_{\mathbf{i}}\), where \(\mathbf{i}\) is the multi-index that induces \(w_\mathbf {i}\). We will use the notation that \(w_{\mathbf{i}} = w\) to denote that \(w_{\mathbf{i}}\) is an element of the equivalence class \(w\). We will similarly write \(|V_w|\) and \(|E_w|\) for the cardinality of the vertex and edge sets of an equivalence class. We will also define the multiset \(EC_w\), which contains the edge counts of every edge in \(w\).
Given a \(w \in \mathcal{G}_k\), we define \(|V_w|\) to be \(|V_{\mathbf{i}}|\), where \(w_{\mathbf{i}}\) is a LoopWalk in the equivalence class \(w\).
Given a \(w \in \mathcal{G}_k\), we define \(|E_w|\) to be \(|E_{\mathbf{i}}|\), where \(w_{\mathbf{i}}\) is a LoopWalk in the equivalence class \(w\).
Given \(w \in \mathcal{G}_k\), we define \(EC_w\) to be the multiset of edge counts of \(w\).
Given \(w \in \mathcal{G}_k\), we have
By the way the equivalence relation is defined in Definition 4.0.11, the fact that there are \(n (n - 1) \cdots (n -|V_w| + 1)\) ways to assign \(|V_w|\) distinct values from \([n]\) into the indices \(i_1,...,i_{|V_w|}\) completes the proof.
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, i.e. \(EC_w\) contains only elements 2 or larger.
Given a \(w \in \mathcal{G}_{k,w \geq 2}\), we must have \(|E_w| \leq k/2\).
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\).
Let \(G=(V,E)\) be a connected finite graph. Then, \(|G|=\# V=\# E+1\) if and only if \(G\) is a plane tree.
\(|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.
Let \(w \in \mathcal{G}_{k,w \geq 2}\). Then \(|V_w| \le k/2 + 1\).
Follows directly from earlier lemmas (replacing \(\# E\) with \(k/2\)).
Let \(w \in \mathcal{G}_{k,w \geq 2}\). Suppose \(k\) odd. Then, \(|V_w| \le \frac{k}{2} + \frac{1}{2}\).
If \(w \in \mathcal{G}_{k,w \geq 2}\), \(k\) is even, and there exists \(e\) such that \(w(e) \ge 3\), then \(|E_w| \le \frac{k-1}{2}\).
Let \(w\in \mathcal{G}_{k,w \geq 2}\), and suppose \(k\) is even. If there exists a loop in \(w\), then \(|V_w|\le k/2\).
Let \(w \in \mathcal{G}_{k,w \geq 2}\), and suppose \(k\) is even. If there exists \(e\in EC_w\) with \(e \ge 3\), then \(|V_w|\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 \(|V_w|=\# V \le k/2\).
Let \(\mathcal{G}^{k/2+1}_k\) to be the set of \(w\in \mathcal{G}_k\) where \(|V_w|=k/2+1\), contains no self-edges, and the walk \(w\) crosses every edge exactly \(2\) times, i.e. \(EC_w =\{ 2, \dots , 2\} \).
Elements of \(\mathcal{G}_k^{k/2+1}\) have \(|E_w| = k/2\).
Elements of \(\mathcal{G}_k^{k/2+1}\) have \(|V_w| = k/2 + 1\).
By definition.
Elements of \(\mathcal{G}_k^{k/2+1}\) are trees.
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 the \(x\)-axis.
Define a map \(\phi \) whose input is \(w \in \mathcal{G}^{k/2 + 1}_k\). Then for its output, define a sequence \(\mathbf{d}=\mathbf{d}(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}(w) = (d_1,\ldots ,d_k)\). Set \(\phi ((w)) = \mathbf{d}(w)\).
\(\phi (w) = \mathbf{d}(w) \in \mathcal{D}_k\), where \(\mathcal{D}_k\) denotes the set of Dyck path of order \(k\).
set \(P_0 = (0,0)\) and \(P_j = (j,d_1+\cdots +d_j)\) for \(1\le j\le k\); then the piecewise linear path connecting \(P_0,P_1,\ldots ,P_k\) is a lattice path. Since \((G,w)\in \mathcal{G}_k^2\), each edge appears exactly two times in \(w\), meaning that the \(\pm 1\)s come in pairs in \(\mathbf{d}(G,w)\). Hence \(d_1+\cdots +d_k=0\). What’s more, for any edge \(e\), the \(-1\) assigned to its second appearance in \(w\) comes after the \(+1\) corresponding to its first appearance; this means that the partial sums \(d_1+\cdots +d_j\) are all \(\ge 0\). That is: \(\mathbf{d}(G,w)\) is a Dyck path
Define a map \(\psi \) whose input is a Dyck path of order \(k\): \(\mathbf{d}_k \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.
\(\psi (\mathbf{d}_k) \in \mathcal{G}^{k/2 + 1}_k\)
Use induction on the order of Dyck path \(k\) which is an even number. Assume \(\phi (\mathbf{d}_{k-2}) \subseteq \mathcal{G}_{k-2}^{k/2 -1}\). In the case of \(k\), the last two steps appended to \(\mathbf{d}_{k-2}\) has to be \(1\) followed by \(-1\) in order for \(\mathbf{d}_k\) to be a Dyck path. By induction hypothesis, this generates a graph with one extra vertex from the parent node, whose walk traversed at the last two steps of the walk.
Apply \(\psi \) to a given Dyck path \(\mathbf{d}\) by definition, then apply \(\phi \) to get a new sequence \(\mathbf{d}'\) such that \(d_j' = 1\) for new vertex, \(-1\) otherwise. For the original Dyck path, the new vertex is the up step corresponding to \(1\). This implies \(\phi \) recovers the original Dyck path.
The map \(\psi \) recovers the graph walk structure of the input from its Dyck path by the definition.
Let \(k\) be even and let \(\mathcal{D}_k\) denote the set of Dyck paths of length \(k\)
Then \(w\mapsto {d}(w)\) is a bijection \(\mathcal{G}_k^{k/2+1}\to \mathcal{D}_k\).
obvious from the previous lemmas.
#{binary trees with \(\frac{k}{2}\) vertices} is given by Catalan number \(C_{k / 2}\)
where \(|\mathcal{D}_k|\) denotes the number of Dyck paths of length \(k\) while \(C_k\) is the \(k\)th Catalan number.
Given a binary tree with \(k\) nodes, perform preorder traversal: for each internal node visited, write an up-step \(U = (1,1)\). For each time return from a child, write a down-step \(D = (1,-1)\). Since every internal node has exactly two children, there are \(k/2\) \(U\)’s and \(k/2\) \(D\)’s, giving a Dyke path of length \(k\). Conversely, given a Dyck path, \(U\) is interpreted as adding new node while \(D\) is returning to the parent node.
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 \(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.0.46
\(w_{\mathbf{i}}\) is the closed walk defined by \(\mathbf{i}\) from definition 4.0.2
\(w_{\mathbf{i}}\) is the closed walk defined by \(\mathbf{j}\) from definition 4.0.2
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\).
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 ??.
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
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')\).
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
This follows from Lemma 5.1.9.
Given a graph \(G_{\mathbf{i} \# \mathbf{j}}\), let \(E^s_{\mathbf{i} \# \mathbf{j}}\) denote the set of self-edges.
Given a graph \(G_{\mathbf{i} \# \mathbf{j}}\), let \(E^c_{\mathbf{i} \# \mathbf{j}}\) denote the set of connecting edges.
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}\).
By construction of the paths \(w_\mathbf {i}\) and \(w_\mathbf {j}\),
By definition of the counting function \(w_{\mathbf{i} \# \mathbf{j}}(\cdot )\),
\((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\).
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)\).
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
In the set \(\mathcal{G}_{k,k,w+w'\ge 2}\), edge count is at most \(k\).
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.
\(G \in \mathcal{G}_{k, k}\). If \(|G| = k + 1\), then \(G\) has exactly \(k\) edges.
\(G \in \mathcal{G}_{k, k}\). If \(|G| = k + 1\), then \(G \in \mathcal{G}_{k, k}\) is a tree.
\(G_{\mathbf{i} \# \mathbf{j}}\) is a tree, then its subgraph \(G_{\mathbf{i}}\) and \(G_{\mathbf{j}}\) are also trees.
\((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.
Assume for contradiction there is one edge \(l\) such that \(w(l) + w'(l) {\gt} 2\), then \(\sum _{e \in G} w(e) + w'(e) {\gt} 2k\).
\((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\).
Each walk is a closed walk, which implies their edge needs to be traversed in even number.
\((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\) .
As a common edge, it is impossible that \(w'\) does not traverse it.
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 \).
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\)
\(\pi (G_{\mathbf{i}\# \mathbf{j}},w_\mathbf {i},w_\mathbf {j}) = \mathbb {E}(X_{\mathbf{i}}X_{\mathbf{j}}) - \mathbb {E}(X_{\mathbf{i}})\mathbb {E}(X_{\mathbf{j}}) = 0\)