Even closed walks and traversal multiplicities

PDF p. 34: Proof of Proposition 6.3, first paragraph

Let $V$ be a nonempty finite set and let $\mathrm{\ell }\ge 1$ be an integer. For $u=(u_1,\dots ,u_{2\mathrm{\ell }})\in V^{2\mathrm{\ell }}$ set $u_{2\mathrm{\ell }+1}=u_1$. When $u_i\mathrm{\ne }{u}_{i+1}$ for every $i$, its $i$th traversed edge is the unordered pair $e_i=\{u_i,u_{i+1}\}$. These are edges of the complete loopless graph on $V$, whose edges are all two-element subsets of $V$; they need not be edges of a particular realization of a random graph.

For each such unordered pair $e$, define its traversal multiplicity by $m_e(u)=\mathrm{\mid }\{i\in \{1,\dots ,2\mathrm{\ell }\}:e_i=e\}\mathrm{\mid }$. Let ${\mathcal{C}}_{2\mathrm{\ell }}$ be the set of those tuples $u$ for which $u_i\mathrm{\ne }{u}_{i+1}$ for every cyclic index and $m_e(u)$ is even for every edge $e$ traversed by $u$. For each integer $k\ge 1$ and $u\in {\mathcal{C}}_{2\mathrm{\ell }}$, let $n_k(u)=\mathrm{\mid }\{e:m_e(u)=k\}\mathrm{\mid }$. Thus $n_k(u)$ counts distinct unordered edges traversed exactly $k$ times.

The article calls members of ${\mathcal{C}}_{2\mathrm{\ell }}$ “even cycles.” They are closed walks of length $2\mathrm{\ell }$ and may repeat vertices and edges. The tuple retains its first position and direction: rotations and reversals are not identified unless they are equal as tuples.

The finite vertex set $V$ together with the set of all its two-element subsets forms a finite simple graph by A finite simple graph is a finite vertex set together with a set of two-element vertex subsets.

The appended endpoint $u_{2\mathrm{\ell }+1}=u_1$ makes $(u_1,\dots ,u_{2\mathrm{\ell }},u_1)$ a closed walk of length $2\mathrm{\ell }$ in the complete loopless graph whenever consecutive entries differ, in the sense of Walks, closed walks, trails, paths and cycles, with length equal to the number of traversed edges. The walk expansion in Trace powers, closed walks and independent edge moments likewise treats a closed walk as an ordered vertex sequence and groups traversals by unordered endpoint pairs. Each $m_e(u)$ is the cardinality of a subset of the finite index set $\{1,\dots ,2\mathrm{\ell }\}$, so it is a well-defined nonnegative integer independent of the order in which the endpoints of $e$ are written. Only finitely many edges are traversed, so each $n_k(u)$ is well defined. The definition imposes even multiplicity on traversed edges and no distinctness condition on vertices or successive edges beyond the exclusion of loops; it therefore does not require a cycle in the distinct-vertex sense of the cited graph definition.

The terminology ${\mathcal{C}}_{2\mathrm{\ell }}$ and $n_k(u)$ and the phrase “even cycles” are attributed to Expander graphs are globally synchronizing, PDF p. 34, first paragraph of the proof of Proposition 6.3. The complete graph describes possible off-diagonal matrix indices in that argument.