on $G_p$. Finally, $C_G|_p$ is the restriction to $G_p$ of the matrix $C_G := \lim_{z \to 1/\lambda^{-}} (\mathrm{Id} - P_\lambda)\mathrm{R}(z)$, with $P_\lambda$ the projector onto the eigenspace associated with the dominant eigenvalue.

Remarks and illustrations are in order before we sketch the proof of this theorem:

* The error terms generated by the sieve on infinite graphs are given in the full publication [61] and omitted here owing to length concerns.

* The lattice constant $\alpha$ relates the densities of walks and of hikes on the infinite lattice $G$. On the square lattice, $\alpha = \frac{1}{4}e^{\frac{4C}{\pi}} \simeq 0.8025...$ with $C$ Catalan's constant.

* The matrix $C_G$ is easy to obtain on regular graphs because its entries obey the same recursion relations as the graph resolvent. More precisely, let $(C_G)_{m,n}$ designate the entry of the matrix corresponding to jumping from vertex $m$ to vertex $n$. Then $\lambda(C_G)_{m,n} = \sum_{i \in \mathcal{N}(n)} (C_G)_{m,i} + \sum_{j \in \mathcal{N}(m)} (C_G)_{j,n}$, where $\mathcal{N}(n)$ and $\mathcal{N}(m)$ designate the set of vertices that are neighbours to $n$ and $m$ on $G$, respectively. On the square lattice this implies that $C_G$ has the following explicit expression:

$$ (C_G)_{ij} = -\frac{1}{\pi} \int_{0}^{\infty} \frac{1}{\tau} \left( 1 - \left( \frac{\tau - i}{\tau + i} \right)^{x_{ij} - y_{ij}} \left( \frac{\tau - 1}{\tau + 1} \right)^{x_{ij} + y_{ij}} \right) d\tau $$

where $i^2 = -1$, $x_{ij}$ and $y_{ij}$ are the distance along $x$ and $y$ between vertices $i$ and $j$ of $G_p$, respectively. In particular if $x_{ij} = y_{ij} = m$ then

$$ (C_G)_{ij} = -\frac{4}{\pi} \sum_{k=1}^{m-1} \frac{1}{2k+1} = -\frac{2}{\pi} \left( H_{m-\frac{1}{2}} + \log(4) \right), $$

with $H_m$ the $m$th harmonic number. Explicit expressions for $C_G$ have already been determined on many more lattices owing to its relation with lattice Green's functions and the resistor problem [9, 41].

Thanks to the last remark, the infinite sieve theorem gives the following corollary on the fraction of closed walk multiples of any SAP on certain vertex-transitive lattices:

**Corollary 6.1.1.** Let $G$ be an infinite vertex-transitive lattice of degree $\lambda$. Let $p$ be a self-avoiding polygon on $G$ and let $F_p$ be the fraction of all closed walks which are walk multiples of $p$.

- If $G$ is a $d$-dimensional hypercubic lattice, then $F_p \in \mathbb{Q}[1/\pi^{d-1}]$.

- If $G$ is the triangular, hexagonal or Kagomé lattice, then $F_p \in \mathbb{Q}[\sqrt{3}/\pi]$.

## Illustrations on the square lattice

We illustrate the infinite sieve theorem with a few examples on the square lattice.

* The fraction of closed walks which are multiples of a given edge $e$ is

$$ \frac{F_e}{4^2} = \frac{1}{8} = 0.125. $$

Since a point is connected to 4 edges, this means that $1/2$ of all closed walks on the square lattice are multiples of an edge. In other terms, an edge is the last erased loop of $1/2$ of all closed walks on the square lattice.

* The fraction of closed walks which are multiples of a $1 \times 1$ square is

$$ \frac{F_{1 \times 1}}{4^4} = \frac{128(\pi - 2)}{4^4 \pi^3} \approx 0.0184. \qquad (6.1.2) $$

See Fig. (6.1) for an illustration of the convergence of the fraction of closed walks on the infinite square lattice which are multiples of a $1 \times 1$ square to the above number. Here the extension of Viennot's lemma to infinite graphs yields the ordinary generating function of closed walks multiple of a $1 \times 1$ square as

$$ \begin{aligned} R_{1 \times 1}(z) &= \frac{1}{256 \pi^4 z^4} \left( (16z^2 - 1) K(16z^2) + E(16z^2) \right)^2 \times \\ & \quad \left( (1 - 16z^2) K(16z^2)^2 + 2K(16z^2) (8\pi z^2 - E(16z^2)) - 4\pi^2 z^2 + E(16z^2)^2 \right), \\ &= z^4 + 12z^6 + 144z^8 + 1804z^{10} + 23464z^{12} + \dots, \end{aligned} \qquad (6.1.3) $$
<figure><img src="image_16.png" /><figcaption>Figure 6.1: Exact fraction of closed walks of length $\ell$ on the infinite square lattice which are multiples of a $1 \times 1$ square as a function of the length of these walks. The exact fraction was obtained from the extension of Viennot’s lemma to infinite graphs and Eq. (6.1.3). The exact fraction converges to its asymptotic value proportionally with the inverse of the walk length, as dictated by an analysis of the error terms associated with the infinite sieve theorem.</figcaption></figure>

where $K(x) := \int_{0}^{\pi/2} (1-x\sin^2(\theta))^{-1/2} d\theta$ and $E(x) := \int_{0}^{\pi/2} (1-x\sin^2(\theta))^{1/2} d\theta$ are the complete elliptic integrals of the first and second kind, respectively. Here Eq. (6.1.2) establishes that asymptotically

$$R_{1 \times 1}(z)[2n] \sim \frac{128(\pi - 2)}{4^4 \pi^3} \binom{2n}{n}^2, \text{ as } n \to \infty.$$

► The fraction of closed walks which are multiples of a $1 \times 2$ rectangle is

$$\frac{F_{1 \times 2}}{4^6} = \frac{32(\pi - 8)(\pi - 4)(3\pi - 8)(3\pi - 4)}{4^6 \pi^4} \approx 0.002585.$$

► The fraction of closed walks which are multiples of a $1 \times 3$ rectangle is

$$\frac{F_{1 \times 3}}{4^8} = \frac{1024(16 - 3\pi)(64 + 3(\pi - 12)\pi)(64 + 27(\pi - 4)\pi)(128 + \pi(27\pi - 124))}{4^8 \times 81\pi^7} \approx 0.00035499.$$

► The fraction of closed walks which are multiples of a $2 \times 2$ square is

$$\frac{F_{2 \times 2}}{4^8} = \frac{32768(\pi - 8)^2(\pi - 4)(3\pi - 8)^3(9\pi - 32)}{4^8 \times 81\pi^7} \approx 0.00044623.$$

► Consider the following SAP $p$:

<figure><img src="image_17.png" /></figure>

Then the fraction of all closed walks which are multiples of this SAP is

$$\begin{align*}
\frac{F_p}{4^{18}} &= \frac{8388608}{4^{18} \times 8303765625 \pi^{12}} \left( \begin{aligned}[t]
& 1721510367131231944781594624 \\
& - 6733029120634416611029155840\pi + 12001725045126647537146527744\pi^2 \\
& - 12895675745638007921939841024\pi^3 + 9303982639359984674575220736\pi^4 \\
& - 4748903115679537036020154368\pi^5 + 1758418560456019196044640256\pi^6 \\
& - 475910723284488375970037760\pi^7 + 93430267561362281294131200\pi^8 \\
& - 12973459941155225172708000\pi^9 + 1209211981439562793530000\pi^{10} \\
& - 67906363349663583525000\pi^{11} + 1736896666805181140625\pi^{12} \end{aligned} \right), \\
& \approx 7.7644 \times 10^{-9}.
\end{align*}$$
This result is well beyond what has been achievable when computing $F_p$ from conformally invariant measures via Abelian sandpile models. Overall, thanks to computer codes by J. Fromentin we computed the fractions $F_p/\lambda^{\ell(p)}$ for over 100,700,000 SAPs analytically, and for more than 3,480,000,000 SAPs numerically on the square lattice. Values of $F_p$ of much longer SAPs are easily obtained numerically, costing no more than $O(\ell(p)^3)$ to compute as outlined earlier. For example, the fraction of closed walks which are multiples of the $70 \times 70$ square is

$$ \frac{F_{70 \times 70}}{4^{280}} \approx 1.5236 \times 10^{-108}. \qquad (6.1.4) $$

Analytically speaking these fractions become very involved very quickly as a function of SAP length and there is no reason to believe that there exists a simpler expression for them than that given by Eq. (6.1.1) of the infinite sieve theorem. For example, the analytical expression for the fraction of closed walks which are multiples of the $6 \times 6$ square already involves sums and products of up to 16-digits prime integers. In fully expanded form this fraction involves a 67-digits prime integer (!).

## 6.2 Proof of the infinite sieve theorem

### Asymptotic enumeration on finite graphs

We begin by wielding the sieving tools offered by number theory to asymptotically count hikes satisfying certain properties on finite graphs. The main results here will be the Finite Sieve Theorem and its length corollary. Before we state these results, there is an important precedent to be found in Viennot's work [195, 196], which provides the ordinary generating functions of hikes which are closed walk multiples of any chosen prime $p$, i.e. whose last erased loop is the SAP $p$. Since this result is conceptually important for the following we start with it:

**Viennot's lemma** [196]. Let $G$ be a finite graph. Let $p$ be a prime on this graph and let $\Sigma_p := \sum_{w:p|_r w} w$ be the formal series of closed walks whose unique right prime divisor is $p$. Then

$$ \Sigma_p = \frac{\det (\mathrm{Id} - W_{G\setminus p})}{\det (\mathrm{Id} - W_G)} p. $$

where $W_{G\setminus p}$ and $W_G$ designate the labelled adjacency matrices of $G\setminus p$ and $G$, respectively.

The semi-commutative extension of the Eratosthenes-Legendre sieve provides the asymptotic expansion of Viennot's result on $\Sigma_p$:

**Finite sieve theorem.** Let $G$ be a finite (weighted di)graph with adjacency matrix $A$. Let $H$ be an induced subgraph of $G$ and let $\mathcal{P}_H$ be the set of primes on $H$. Let $\rho: \mathcal{H} \mapsto \mathbb{R}$ be a rank function on hikes such that $|\mathcal{H}_\rho| = \lambda^\rho f(\rho)$ with $\lambda$ a real constant and $f(.)$ a bounded function such that $\lim_{\rho \to \infty} f(\rho)$ exists. Then the number (weight)$^1 S(\mathcal{H}_\rho, \mathcal{P}_H)$ of hikes of rank $\rho$ which are not multiples of primes on $H$ is asymptotically given by

$$ \frac{S(\mathcal{H}_\rho, \mathcal{P}_H)}{|\mathcal{H}_\rho|} \sim \sum_{d \in \mathcal{P}_H^{s,a}} \mu(d) \lambda^{-\rho(d)}, \quad \text{as } \rho \to \infty. $$

The finite sieve theorem's most important application here will be with the length rank-function and sieving subgraph $H = G\setminus p$ for $p$ a prime.

**Length corollary.** Let $G$ be a finite (weighted di)graph with adjacency matrix $A$ and dominant eigenvalue $\lambda$, which we assume to be unique.<fnref n="2" /> Let $p$ be a simple cycle or a simple path on $G$ of length $\ell(p)$ and let $S(\mathcal{H}_\ell, \mathcal{P}_{G\setminus p})$ be defined as in the finite sieve theorem. Then $S(\mathcal{H}_\ell, \mathcal{P}_{G\setminus p})$ is equal to the number (weight) of closed walks of length $\ell$ on $G$ whose unique right prime divisor is $p$ and is asymptotically given by

$$ \frac{S(\mathcal{H}_\ell, \mathcal{P}_{G\setminus p})}{|\mathcal{H}_\ell|} \sim \frac{1}{\lambda^{\ell(p)}} \det \left( \mathrm{Id} - \frac{1}{\lambda} \mathcal{A}_{G\setminus p} \right) \quad \text{as } \ell \to \infty. $$

Let $\mathrm{Err}(\mathcal{H}_\ell, \mathcal{P}_{G\setminus p})$ be the difference between the two terms above. Let $f(\ell) := \zeta(z/\lambda)[\ell]$ be the coefficient of $z^\ell$ in the expansion of $\zeta(z/\lambda)$. Then $f$ is bounded, $\lim_{\ell \to \infty} f(\ell)$ exists, and

$$ \mathrm{Err}(\mathcal{H}_\ell, \mathcal{P}_{G\setminus p}) = \frac{1}{\lambda^{\ell(p)}} \sum_{k \ge 0}^{\infty} \left( \frac{\nabla^k [f](\ell - \ell(p))}{f(\ell) \lambda^k k!} - \delta_{k,0} \right) \det^{(k)} \left( \mathrm{Id} - \frac{1}{\lambda} \mathcal{A}_{G\setminus p} \right). $$

with $\delta_{k,0}$ the Kronecker delta. Here, $\det^{(k)}(\mathrm{Id} - \frac{1}{\lambda} \mathcal{A}_{G\setminus p})$ stands for the $k$th derivative of $\det(\mathrm{Id} - z \mathcal{A}_{G\setminus p})$ evaluated in $z = 1/\lambda$.

<footnote n="1">¹The notation $S(\mathcal{H}_\rho, \mathcal{P}_H)$ for this quantity is employed in keeping with conventions from sieve theory.</footnote>

<footnote n="2">²The theorem extends if $\lambda$ is not unique upon replacing $\lambda^{-1}$ by $\lambda^{-g}$ with $g$ its multiplicity.</footnote>
*Proof of the finite sieve theorem.* The proof relies on an inclusion-exclusion principle in the poset of the hikes ordered by right-divisibility. As such it is a limpid example of the usability of number-theoretic techniques in the context of hike monoids. For this reason we have kept most of the proof in this report.

Let $\mathcal{P} \subsetneq \mathcal{H}$ be a set of primes and $\mathcal{P}^{\text{s.a.}}$ the set of all self-avoiding hikes constructible from $\mathcal{P}$. Let $S(\mathcal{H}_{\rho}, \mathcal{P})$ be the number (weight) of hikes in $\mathcal{H}_{\rho}$ which are not right-divisible by any prime of $\mathcal{P}$. The inclusion-exclusion principle–here the extension to hikes of the sieve of Erathostenes-Legendre–yields

$$S(\mathcal{H}_{\ell}, \mathcal{P}) = \sum_{d \in \mathcal{P}^{\text{s.a.}}} \mu(d) |\mathcal{M}_d|,$$

with $|\mathcal{M}_d|$ the number of multiples of $d$ in $\mathcal{H}_{\rho}$ and $\mu(d)$ is the Möbius function on hikes.

In order to progress, we seek a multiplicative function $\text{prob}(\cdot)$ such that $|\mathcal{M}_d| = \text{prob}(d)|\mathcal{H}_{\rho}| + r(d)$. In this expression, $\text{prob}(d)$ approximates the probability that a hike taken uniformly at random in $\mathcal{H}_{\rho}$ is right-divisible by $d$. If edge-weights are present, the hikes are not all uniformly probable but follow a distribution dependent on these weights. No knowledge of this distribution is required here. Similarly, $m(d) = \text{prob}(d)|\mathcal{H}_{\rho}|$ is the expected number of multiples of $d$ in $\mathcal{H}_{\rho}$. Finally, $r(d)$ is the associated error term, arising from the fact that $|\mathcal{M}_d|$ is not truly multiplicative. Supposing that we can identify the $m(\cdot)$ function, we would obtain

$$S(\mathcal{H}_{\rho}, \mathcal{P}) = \sum_{d \in \mathcal{P}^{\text{s.a.}}} \mu(d)m(d) + \sum_{d \in \mathcal{P}^{\text{s.a.}}} \mu(d)r(d).$$

Contrary to number theory, the first term does not admit any simpler form without further assumptions on $\mathcal{P}$. This is because of the possible lack of commutativity between some elements of $\mathcal{P}$. We note however that since $\mu(d)$ is non-zero if and only if $d$ is self-avoiding, and since we have required that $m(\cdot)$ be multiplicative,<fnref n="3" /> then it follows that the first term is determined solely from the values of $m(\cdot)$ over the primes of $\mathcal{P}$.

We therefore turn to determining $m(p)$ for $p$ prime. The set of left-multiples of $p$ in $\mathcal{H}$ is $\mathcal{M}_p := \{hp, h \in \mathcal{H}\}$, hence in bijection with the set $\mathcal{H}$. Thus, the number of left-multiples of $p$ in $\mathcal{H}_{\rho}$, is exactly $|\mathcal{H}_{\rho-\rho(p)}|$. Then

$$\text{prob}(p) + \frac{r(p)}{|\mathcal{H}_{\rho}|} = \frac{|\mathcal{H}_{\rho-\rho(p)}|}{|\mathcal{H}_{\rho}|}.$$

Seeking the best possible probability function $\text{prob}(\rho)$, let us suppose that we can choose this function such that the error term of the above equation vanishes in the limit $\rho \to \infty$. If this is true, then we obtain

$$\text{prob}(\rho) = \lim_{\rho \to \infty} \frac{|\mathcal{H}_{\rho-\rho(p)}|}{|\mathcal{H}_{\rho}|}.$$

In order to progress, we have to make an important assumption regarding the cardinality of the set $\mathcal{H}_{\rho}$:

**Assumption 1.** There exists a scaling constant $\lambda$ and bounded function $f: \mathbb{R} \mapsto \mathbb{R}$ such that $\lim_{\rho \to \infty} f(\rho)$ exists and for $\rho \in \mathbb{N}^*$

$$|\mathcal{H}_{\rho}| = \lambda^{\rho} f(\rho).$$

In the case of the length function, this assumption is actually a proposition:

**Proposition 6.2.1.** Let $G$ be a finite (weighted di)graph with dominant eigenvalue $\lambda$ of multiplicity $g$. Let $\mathcal{H}_{\ell} := \{h \in \mathcal{H} : \ell(h) = \ell\}$ be set of all hikes on $G$ of length $\ell$. Then, there exists a bounded function $f: \mathbb{N} \mapsto \mathbb{R}$ such that $\lim_{\ell \to \infty} f(\ell)$ exists and for $\ell \in \mathbb{N}^*$ we have exactly

$$|\mathcal{H}_{\ell}| = \lambda^{g\ell} f(\ell).$$

This follows from expanding the ordinary zeta function on hikes $\zeta(z) = \det(|d - zA|)^{-1}$ on the spectrum of $G$. Proceeding with Assumption 1. or Proposition 6.2.1, the existence of the limit for $f$ gives

$$\text{prob}(p) = \lim_{\rho \to \infty} \frac{\lambda^{\rho-\rho(p)} f(\rho-\rho(p))}{\lambda^{\rho} f(\rho)} = \lambda^{-\rho(p)}.$$

The $\text{prob}(\cdot)$ function is multiplicative over the primes as desired and yields $m(p) = |\mathcal{H}_{\rho}|\lambda^{-\rho(p)}$. The associated error term is

$$r(\rho) = |\mathcal{H}_{\rho-\rho(p)}| - |\mathcal{H}_{\rho}|\lambda^{-\rho(p)} = \lambda^{\rho-\rho(p)} (f(\rho-\rho(p)) - f(\rho)).$$

<footnote n="3">³But not necessarily totally multiplicative.</footnote>
To establish the validity of these results, we need only verify that they are consistent with our initial supposition concerning the error term, namely that $r(p)/|\mathcal{H}_\rho|$ vanishes in the limit $\rho \to \infty$. The existence of the limit of $f$ implies $\lim_{\rho \to \infty} |f(\rho - \rho(p)) - f(\rho)| = 0$ and therefore that

$$ \lim_{\rho \to \infty} \frac{r(p)}{|\mathcal{H}_\rho|} = \lim_{\rho \to \infty} \lambda^{-\rho(p)} (f(\rho - \rho(p)) - f(\rho)) = 0, $$

as required.

We are now ready to proceed with general self-avoiding hikes. Let $d = p_1 \cdots p_{\Omega(d)}$ be self-avoiding. Since $m$ is multiplicative and the rank function is totally additive over $\mathcal{H}$, $m(d) = \prod_i m(p_i) = \lambda^{-\sum_i \rho(p_i)} = \lambda^{-\rho(d)}$. The associated error term follows as

$$ r(d) = |\mathcal{H}_{\rho-\rho(d)}| - |\mathcal{H}_{\rho}|\lambda^{-\rho(d)} = \lambda^{\rho-\rho(d)}(f(\rho-\rho(d)) - f(\rho)). $$

Inserting these forms for $m(d)$ and $r(d)$ in the sieve yields

$$ S(\mathcal{H}_\ell, \mathcal{P}) = |\mathcal{H}_\rho| \sum_{d \in \mathcal{P}^{\text{s.a.}}} \mu(d) \lambda^{-\rho(d)} + \lambda^\rho \sum_{d \in \mathcal{P}^{\text{s.a.}}} \mu(d) \lambda^{-\rho(d)} (f(\rho - \rho(d)) - f(\rho)). \quad (6.2.1) $$

We can now progress much further on making an additional assumption concerning the nature of the prime set $\mathcal{P}$. We could consider two possibilities: i) that $\mathcal{P}$ is the set of all primes on an induced subgraph $H \prec G$; or ii) that $\mathcal{P}$ is a cut-off set, e.g. one disposes of all the primes of length $\ell(p) \le L$. Remarkably, in number theory, if i) is true then ii) is true as well, and the sieve benefits from the advantages of both situations. In general however, i) and ii) are not compatible and while ii) could be used to obtain direct estimates for the number of primes of any length, a problem of great interest, this actually makes the sieve NP-hard to implement. We therefore focus on the first situation.

Let $H \prec G$ be an induced subgraph of the graph $G$ and let that $\mathcal{P} \equiv \mathcal{P}_H$ be the set of all primes (here simple cycles) on $H$. To conclude the proof we need only show that the error term of Eq. (6.2.1) is asymptotically dominated by the first term $\sum_{d \in \mathcal{P}_H^{\text{s.a.}}} \mu(d)\lambda^{-\rho(d)}$. To this end, we note that since $H$ is finite<fnref n="4" />

$$ \lambda^{\rho} \sum_{d \in \mathcal{P}_H^{\text{s.a.}}} \mu(d) \lambda^{-\rho(d)} (f(\rho - \rho(d)) - f(\rho)), $$

is a sum involving finitely many self-avoiding hikes $d$. In addition, given that $\lim_{\rho \to \infty} f(\rho)$ exists (either by Assumption 1. or by Proposition 6.2.1 for the length rank function), $\lim_{\rho \to \infty} f(\rho - \rho(d)) - f(\rho) = 0$ as long as $\rho(d)$ is finite, which is guaranteed by the finiteness of $H$. We have consequently established that the error term comprises finitely many terms, each of which vanishes in the $\rho \to \infty$ limit. As a corollary, the first term is asymptotically dominant:

$$ \frac{S(\mathcal{H}_\rho, \mathcal{P}_H)}{|\mathcal{H}_\rho|} \sim \sum_{d \in \mathcal{P}_H^{\text{s.a.}}} \mu(d) \lambda^{-\rho(d)} \quad \text{as } \rho \to \infty, $$

where we assume that $|\mathcal{H}_\rho| \ne 0$.

We now turn to establishing the length corollary of the finite sieve theorem. We are specifically looking for the number of closed walks which are multiples of a prime $p$. To this end, we need only choose $H$ correctly. Let $h$ be a hike, for $w = hp$ to be a walk of length $\ell$, then $h$ must have length $\ell - \ell(p)$ and be such that none of its right-prime divisor commutes with $p$. The sieve must thus eliminate all hikes $h$ which are left-multiples of primes commuting with $p$. Observe that all such primes are on $H = G \setminus p$. Consequently the finite sieve theorem yields, for $|\mathcal{H}_{\ell-\ell(p)}| \ne 0$,

$$ S(\mathcal{H}_\ell, \mathcal{P}_{G \setminus p}) = |\mathcal{H}_{\ell-\ell(p)}| \sum_{d \in \mathcal{P}^{\text{s.a.}}} \mu(d) \lambda^{-\ell(d)} \\ + \lambda^{\ell-\ell(p)} \sum_{d \in \mathcal{P}^{\text{s.a.}}} \mu(d) \lambda^{-\ell(d)} (f(\ell - \ell(p) - \ell(d)) - f(\ell - \ell(p))), $$

where $\lambda$ is now the graph dominant eigenvalue per Proposition 6.2.1. The asymptotically dominant term is a sum over all the self-avoiding hikes on $G \setminus p$, each with coefficient $\mu(d)\lambda^{-\ell(d)}$ and is equal to $\det(\mathrm{Id} - \lambda^{-1}\mathcal{A}_{G \setminus p})$. Since furthermore $|\mathcal{H}_{\ell-\ell(p)}| = |\mathcal{H}_\ell|\lambda^{-\ell(p)}f(\ell-\ell(p))/f(\ell)$, we have asymptotically for $\ell \gg 1$

$$ \frac{S(\mathcal{H}_\ell, \mathcal{P}_{G \setminus p})}{|\mathcal{H}_\ell|} \sim \lambda^{-\ell(p)} \det \left( \mathrm{Id} - \frac{1}{\lambda} \mathcal{A}_{G \setminus p} \right), $$

<footnote n="4">⁴$G$ is finite and so are all its induced subgraphs.</footnote>
while the error terms is

$$
\begin{align*}
\mathrm{Err}(\mathcal{H}_\ell, \mathcal{P}_{G\setminus p}) &:= \frac{S(\mathcal{H}_\ell, \mathcal{P}_{G\setminus p})}{|\mathcal{H}_\ell|} - \lambda^{-\ell(p)} \det \left( \mathrm{Id} - \frac{1}{\lambda} \mathcal{A}_{G\setminus p} \right), \\
&= \lambda^{-\ell(p)} \left( \frac{f(\ell - \ell(p))/f(\ell) - 1}{f(\ell)} \right) \det \left( \mathrm{Id} - \frac{1}{\lambda} \mathcal{A}_{G\setminus p} \right) + \frac{\lambda^{-\ell(p)}}{f(\ell)} \sum_{d \in \mathcal{P}^{\mathrm{s.a.}}} \mu(d) \lambda^{-\ell(d)} \left( f(\ell - \ell(p) - \ell(d)) - f(\ell - \ell(p)) \right).
\end{align*}
$$

The last line can be brought in determinantal form as well, since

$$
\begin{align*}
\frac{\lambda^{-\ell(p)}}{f(\ell)} \sum_{d \in \mathcal{P}^{\text{s.a.}}} \mu(d) \lambda^{-\ell(d)} (f(\ell - \ell(p) - \ell(d)) - f(\ell - \ell(p))) &= \lambda^{-\ell(p)} \sum_{d \in \mathcal{P}_H^{\text{s.a.}}} \mu(d) \lambda^{-\ell(d)} \sum_{k \ge 1} \frac{\nabla^k [f](\ell - \ell(p))}{f(\ell)k!} (\ell(d))_{(k)}, \\
&= \lambda^{-\ell(p)} \sum_{k \ge 1}^{\infty} \frac{\nabla^k [f](\ell - \ell(p))}{f(\ell)\lambda^k k!} \det^{(k)} \left( \mathrm{Id} - \frac{1}{\lambda} \mathcal{A}_{G\setminus p} \right).
\end{align*}
$$

Now setting $k = 0$ in the above recovers $\lambda^{-\ell(p)} (f(\ell - \ell(p))/f(\ell) - 1) \det (\mathrm{Id} - \frac{1}{\lambda} \mathcal{A}_{G\setminus p})$ with the exception of the $-1$ in the parenthesis, which can be introduced as $-\delta_{k,0}$. This establishes the finite sieve theorem and its length corollary. $\square$

Infinite graphs

We are now in position to sketch the proof of Theorem 6.1 for the fraction of walks that are multiple of any
chosen self-avoiding polygon on any infinite vertex-transitive graph. The first difficulty in extending the finite
sieve theorem to infinite graphs comes from the proliferation of hikes on such graphs: there are either exactly 0
or infinitely many hikes of any given length. Furthermore, the number of hikes increases uncontrollably with the
length as there are also infinitely many more hikes of any length $L' > L$ than of length $L$. These observations
continue to be true even when hikes are considered up to translation. To make matters worse, the fraction of all
hikes which are walks is exactly 0; and even with edge weights uniformly set to $1/\lambda$, the total weight carried by
all walk multiples of any SAP $p$ is still divergent. To resolve these serious difficulties requires us to separate the
finite sieve results into two contributions, the first of which relates hikes to walks and the second relates closed
walks to walks multiples of $p$. This second contribution must itself be dealt with carefully to cure divergences
stemming from the non-meromorphic nature of the generating functions involved. We illustrate every step of
the proof with explicit results on the square lattice.

Let us consider a sequence of finite graphs $G_N^{\text{Tor}}$ converging to the desired lattice as $N \to \infty$ (for an explicit construction of such a sequence and accompanying notions of convergence, see [61]). Fixing $N$, consider $p$ a self-avoiding polygon on $G_N^{\text{Tor}}$. Then we can transform the asymptotic fraction of hikes of length $\ell$ that are walks multiples of $p$ as $\ell \to \infty$ given by the finite sieve theorem into

$$
\frac{S(\mathcal{H}_\ell, \mathcal{P}_{G_N^{\text{Tor}}\setminus p})}{|\mathcal{H}_\ell|} \sim \lambda^{-\ell(p)} \det \left( \mathrm{Id} - \frac{1}{\lambda} \mathcal{A}_{G_N^{\text{Tor}}\setminus p} \right) = \lambda^{-\ell(p)} \lim_{z \to 1/\lambda^{-}} \zeta_N(z)^{-1} \det (\mathrm{Id} + z \mathbb{R}_N(z) \mathbb{B}_{N,p}).
$$

Here $\mathbb{R}_N(z) := (\mathrm{Id} - z \mathcal{A}_{G_N^{\mathrm{Tor}}})^{-1}$ and $\mathbb{B}_N(p) := \mathcal{A}_{G_N^{\mathrm{Tor}}} - \mathcal{A}_{G_N^{\mathrm{Tor}}\setminus p}$. Since $\mathbb{B}_{N,p}$ is zero everywhere but on the few edges touching vertices of $p$, the determinant on the right-hand side is reducible to that of a finite matrix and thus will be well-defined under $N \to \infty$. This suggests a strategy consisting of proving separate convergence in $z \to 1/\lambda^-$ of the two terms in the limit above. This naive strategy ultimately fails, but the procedure that works is best understood once the nature of this failure is made apparent and several results we will obtain along the way are necessary to implement the correct proof strategy. In this spirit, we pretend to follow the naive approach and thus first examine the behaviour of the limit $\lim_{z \to \lambda^{-1}} \zeta_N(z)^{-1}$ asymptotically in $N$. We find [61],

**Lemma 6.2.1.** Let {$G_N^{\mathrm{Tor}}$}$_{N \in \mathbb{N}}$ be a sequence of vertex-transitive graphs converging to the infinite bounded-degree vertex-transitive graph $G$ with maximum eigenvalue $\lambda$. Let $\zeta_N(z)$ be the zeta function of hikes on $G_N^{\mathrm{Tor}}$ and let $R(z) = R(z)_{ii}$ be the ordinary generating function of closed walks on $G$. Then,

$$
\lim_{N \to \infty} \zeta_N(z)^{1/N} = \tilde{\zeta}(z) = \exp \left( \int \frac{1}{z} (R(z) - 1) dz \right). \qquad (6.2.2)
$$

Furthermore $\alpha := \lim_{z \to 1/\lambda^{-}} \tilde{\zeta}^{-1}(z)$ is well defined.

All the coefficients $\tilde{\zeta}(z)[n]$ are positive integers, while the coefficients $\tilde{\zeta}^{-1}(z)[n]$ are integers. To see this, consider $h$ a hike and let $w_1, \cdots w_n$ be vertex-disjoint walks making up hike $h$, i.e. $h = w_1w_2 \cdots w_n$ modulo
the fact that all these walk commute with one another. A rooted hike $h_{\text{root}}$ is the object obtained from $h$ on translating all walks $w_i$ so that the origin lies on their unique right prime divisor but retaining the fact that they commute. Then $\tilde{\zeta}(z)[n]$ counts the number of rooted hikes of length $n$, $\tilde{\zeta}(z)$ is the zeta function of rooted hikes, while $\tilde{\mu}(z) := \zeta^{-1}(z)$ is the Möbius function on rooted hikes.

Lemma 6.2.1 implies that asymptotically, when $N \gg 1$, $\lim_{z \to 1/\lambda^{-}} \zeta_{N}(z)^{-1} \sim \alpha^{N}$ is well defined. We will see later on that $\alpha^{N}$ relates the density of hikes to that of walks on an infinite graphs.

**Lemma 6.2.2.** Let $G$ be an infinite vertex-transitive graph of bounded degree. Let $\{G_{N}^{\text{Tor}}\}_{N \in \mathbb{N}}$ be the small tori sequence of vertex-transitive graphs converging to $G$. Let $\bullet$ be any vertex of $G$. Then the fraction $F_{\bullet}$ of hikes which are closed walks from $\bullet$ to itself is asymptotically given by $F_{\bullet} \sim \alpha^{N}/N$, as $N \to \infty$. In this expression $\alpha$ is the constant defined in Lemma 6.2.1.

The $1/N$ factor in $F_{\bullet}$ originates from that we have fixed the vertex $\bullet$. If instead we consider translation invariant quantities, i.e. we consider all closed walks irrespectively of their starting point, then the fraction of hikes which are closed walks is asymptotically $\alpha^{N}$, $N \gg 1$. This important technical Lemma is proven on expanding the determinantal expression for $F_{\bullet}$ as given by the finite sieve theorem perturbatively, developing $A_{G} \setminus \bullet$ around $A_{G}$.

**Lemma 6.2.3.** Let $G$ be an infinite vertex-transitive graph of bounded-degree and let $\lambda$ be the supremum of its spectrum. Let $\{G_{N}^{\text{Tor}}\}_{N \in \mathbb{N}}$ be the small tori sequence of vertex-transitive graphs converging to $G$. Then the asymptotic fraction of closed walks which are walk multiples of $p$ is well defined and given by

$$ \frac{F_p}{\lambda^{\ell(p)}} = \lim_{N \to \infty} \lim_{z \to 1/\lambda^{-}} z^{\ell(p)} \frac{\det(\mathrm{Id} + z\mathrm{R}_N(z)\mathrm{B}_p)}{\det(\mathrm{Id} + z\mathrm{R}_N(z)\mathrm{B}_{\bullet})} = \frac{1}{\lambda^{\ell(p)+1}} \mathrm{deg}^{\mathrm{T}}. \mathrm{adj}(\mathrm{Id} + \mathrm{C}_G|_p \mathrm{B}_p) \cdot \mathbf{1}, $$

where $C_G|_p$ is the restriction to $G_p$ of $C_G := \lim_{z \to 1/\lambda^{-}} (\mathrm{Id} - P_{\lambda})\mathrm{R}(z)$.

According to the finite sieve theorem, the asymptotic fraction of hikes which are closed walks multiples of $p$ on $G_{N}^{\text{Tor}}$ is $\lim_{z \to 1/\lambda^{-}} z^{\ell(p)} \det(\mathrm{Id} - zA_{G_{N}^{\text{Tor}}|_p})$. Since all the limits taken here are finite and well defined (as everything takes place on $G_{N}^{\text{Tor}}$), the asymptotic fraction of closed walks which are multiples of $p$ on these finite graphs is

$$ \begin{aligned} \frac{\lim_{z \to 1/\lambda^{-}} z^{\ell(p)} \det(\mathrm{Id} - zA_{G_{N}^{\text{Tor}}|_p})}{\lim_{z \to 1/\lambda^{-}} z^0 \det(\mathrm{Id} - zA_{G_{N}^{\text{Tor}}|_\bullet})} &= \lim_{z \to 1/\lambda^{-}} z^{\ell(p)} \frac{\zeta_N(z) \det(\mathrm{Id} - zA_{G_{N}^{\text{Tor}}|_p})}{\zeta_N(z) \det(\mathrm{Id} - zA_{G_{N}^{\text{Tor}}|_\bullet})}, \\ &= \lim_{z \to 1/\lambda^{-}} z^{\ell(p)} \frac{\det(\mathrm{Id} + z\mathrm{R}_N(z)\mathrm{B}_p)}{\det(\mathrm{Id} + z\mathrm{R}_N(z)\mathrm{B}_{\bullet})}. \end{aligned} $$

We now turn to studying the behaviour of the right hand side as $N \to \infty$. To this end, we expand $\mathrm{Id} + z\mathrm{R}_N(z)\mathrm{B}_p$ around $1/\lambda$ with $z < 1/\lambda$.

We need to distinguish behaviours based on the dimensionality $d > 1$ of the lattice under study. We ignore the trivial 1D case (for which the only SAP is the edge, and the fraction of closed walk multiples of the left or right edge attached to any vertex is $1/2$). On $d > 1$ dimensional lattices we have,

$$ \mathrm{Id} + z\mathrm{R}_N(z)\mathrm{B}_p = C_N \mathrm{B}_p - \frac{1}{\lambda\pi} \mathrm{P}_{N,\lambda} \mathrm{B}_p \mathrm{Li}_{d/2}(1-z\lambda) + O(1-z\lambda), \quad (6.2.3) $$

with $C_N := \lim_{z \to 1/\lambda^{-}} (\mathrm{Id} - P_{N,\lambda})\mathrm{R}_N(z)$ and $\mathrm{Li}_a(x) := \sum_{n>1} \frac{x^n}{n^a}$ is the $a$-polylogarithm function. Combinatorially, it arises here from summations over closed walks weighted by $\lambda^{-\ell}$, which leaves a residual total weight asymptotically given by $\ell^{-d/2}$ for all closed walks of length $\ell \gg 1$. The generic nature of the behaviour exhibited by $\mathrm{Id} + z\mathrm{R}_N(z)\mathrm{B}_p$ is now readily apparent: 1) divergence occurs only on 2D lattices, where it is logarithmic; 2) it is the same for all SAPs; and 3) it is also the same for all closed walks (which are readily recovered upon taking $p$ to be length 0, i.e. $\mathrm{B}_p \equiv \mathrm{B}_{\bullet}$ is a corolla). Thanks to these observations, the determinant expansion at $1/\lambda^{-}$ is

$$ \begin{aligned} \det(\mathrm{Id} + z\mathrm{R}_N(z)\mathrm{B}_p) &= \det\left(C_N \mathrm{B}_p - \frac{1}{\lambda\pi} \mathrm{P}_{N,\lambda} \mathrm{B}_p \mathrm{Li}_{d/2}(1-z\lambda) + O(1-z\lambda)\right), \\ &= -\frac{1}{\pi N} \mathrm{Li}_{d/2}(1-z\lambda) \frac{1}{\lambda} \mathrm{deg}^{\mathrm{T}}. \mathrm{adj}(\mathrm{Id} + C_N \mathrm{B}_p) \cdot \mathbf{1} + o(\mathrm{Li}_{d/2}(1-z\lambda)), \end{aligned} $$

where we used the matrix-determinant lemma and the QR decomposition

$$ -\frac{1}{\lambda\pi} \mathrm{P}_{N,\lambda} \mathrm{B}_p = -\frac{1}{\pi N} \times \frac{1}{\lambda} \times \mathbf{1} \cdot \mathrm{deg}^{\mathrm{T}}. $$
This decomposition relies on the observation that $P_{N,\lambda}$ is the projector onto $\mathbf{1}$, i.e. that all $G_N^{\text{Tor}}$ are regular. We recall that in the above expression, $\deg = \mathbf{B}_p \cdot \mathbf{1} = \text{diag}(\mathbf{B}_p^2)$ is the degree of vertices on $G_p$. Similarly, at $1/\lambda^-$,

$$ \det (\mathrm{Id} + z \mathbf{R}_N(z) \mathbf{B}_\bullet) = -\frac{1}{\pi N} \mathrm{Li}_{d/2}(1-z\lambda) + o(\mathrm{Li}_{d/2}(1-z\lambda)), $$

and finally

$$ z^{\ell(p)} \frac{\det (\mathrm{Id} + z \mathbf{R}_N(z) \mathbf{B}_p)}{\det (\mathrm{Id} + z \mathbf{R}_N(z) \mathbf{B}_\bullet)} = \frac{1}{\lambda^{\ell(p)+1}} \mathrm{deg}^T \cdot \mathrm{adj}(\mathrm{Id} + \mathbf{C}_N \cdot \mathbf{B}_p) \cdot \mathbf{1} + o(1), $$

which yields the result after taking the limits $z \to 1/\lambda^-$ and $N \to \infty$ now both clearly well-defined, even when $d=2$. Combinatorially, the divergence curing on 2D lattices effected here comes from relating walk multiples of a SAP to all closed walks rather than directly to the hikes. The relation between closed walks and hikes is performed separately through Lemma 6.2.2.

## 6.3 Relation with the self-avoiding polygons counting problem

We recall that $R(z)$ and $R_p(z)$ are the ordinary generating functions of closed walks and of walk multiples of a SAP $p$, respectively. The research presented here suggests a natural strategy to tackle the open problem of asymptotically counting SAWs and SAPs. First, observe that we know the exact number $R(z)[L]$ of closed walks of length $L$ defined up to translation. Then, if we could determine the exact number $R_p(z)[L]$ of closed walks of length exactly $L$ that are multiples of a SAP $p$, it would be sufficient to sum this over all SAPs of length strictly less than $L$ and subtract the result from $R(z)[L]$ to determine the number $\pi(L)$ of SAPs of length exactly $L$:

$$ \pi(L) = R(z)[L] - \sum_{\substack{p: \text{SAP} \\ \ell(p) < L}} R_p(z)[L]. $$

While such a precise count is not feasible in practice as $L \to \infty$, an asymptotic estimate of the number of walk multiples of SAPs may seem, at first, to be sufficient to gain an insight into the number of SAPs themselves. Following this idea, we would rather write

$$ \frac{\pi(L)}{R(z)[L]} = 1 - \sum_{\substack{p: \text{SAP} \\ \ell(p) < L}} \frac{R_p(z)[L]}{R(z)[L]}. \qquad (6.3.1) $$

and use $R_p(z)[L]/R(z)[L] \sim F_p \lambda^{-\ell(p)}$ for $L \gg 1$. Thus, we would only need to estimate sums like

$$ S(L) := \sum_{\substack{p: \text{SAP} \\ \ell(p) \le L}} \frac{F_p}{\lambda^{\ell(p)}}, $$

for $L \gg 1$, in order to work out an asymptotic expansion for $\pi(L)$. Such an estimate can already be determined from Kenyon's seminal results [104], we find $S(L) = 1 - L^{-3/5} + O(L^{-3/5})$. See also Fig 6.2 for a numerical illustration. This result of course wildly differs from the $(\mu/\lambda)^L L^{-1/2}$ expected here from the numerically conjectured scaling for $\pi(L)$.<fnref n="5" /> From the point of view of probability theory, the origin of this discrepancy is clear: the law governing Lawler's loop erased random walks essentially converges to $SLE_2$ rather than the conjectured $SLE_{8/3}$ for SAP and SAW models. From the point of view of sieve techniques however, the chasm between these results originates from an uncontrolled accumulation of error terms affecting the estimate $R_p(z)[L]/R(z)[L] \sim F_p \lambda^{-\ell(p)}$.

It is important to recall that $F_p \lambda^{-\ell(p)}$ is only the first, asymptotically dominant term of the asymptotic expansion of the number of walk multiples of $p$. In particular $F_p \lambda^{-\ell(p)}$ is a good approximation to $R_p(z)[L]/R(z)[L]$ only when $L \gg \ell(p)$. Yet, when we subtract walks multiples of SAPs from all closed walks of length $L$, we must consider the multiples of SAPs $p$ of length up to $\ell(p) = L-1$. Given the exponential growth in the number of SAPs, this means that most of our estimates are affected by large, uncontrolled errors, and it is impossible to exploit Eq. (6.3.1) using solely $S(L)$.

This problem has two potential solutions. The first idea is to take into account some error terms $\text{Err}_p(L)$ in the asymptotic expansion of $R_p(z)[L]/R(z)[L]$ so as to determine this quantity more precisely. Since all the error terms are exactly available<fnref n="7" />, it seems possible that an extension to Kenyon's arguments would allow us to

<footnote n="5">⁵The correction term is $L^{-1/2}$ here because we count simple cycles rather than SAPs. This is responsible for a factor of $L$ in front of the $L^{-5/2}$. Since in addition, $R(z)[L] \sim \lambda^L/(\pi L)$ for $L \gg 1$, this accounts for another factor of $L$ and finally we get $L \times L \times L^{-5/2} = L^{-1/2}$.</footnote>

<footnote n="6">⁶These errors have the same origin as those affecting the Eratosthenes-Legendre sieve in number theory!</footnote>

<footnote n="7">⁷In fact $R_p(z)[L]$ itself is in principle exactly available from the extension of Viennot's Lemma to infinite graphs. In this situation however, it is a precise estimate for the sum over SAPs of $R_p(z)[L]$ which is utterly lacking.</footnote>
<figure><img src="image_18.png" /><figcaption>Figure 6.2: In red points and dashed red line: sum over all self-avoiding polygons $p$ of length at most $L$ of the fraction $F_p/4^{\ell(p)}$, as a function of $L$. Solid blue line: dominant term of the asymptotic expansion for this quantity, that is $1-L^{-3/5}$. The discrepancy between exponents $-3/5$ and the $-1/2$ expected from SAP counting is due to an accumulation of error terms when summing over SAPs in the infinite sieve theorem.</figcaption></figure>

estimate sums of such error terms generically. This idea suffers from a major drawback: error terms actually grow with $L$ if we consider classes of SAPs for which $L - \ell(p)$ is fixed. Since most SAPs of length up to $L-1$ are close in length to $L$, this means that the overall error term affecting Eq. (6.3.1) grows uncontrollably with $L$. Thus, an increasingly (and unrealistically) detailed knowledge of the errors is needed as $L \to \infty$, so that this strategy collapses completely with respect to rigorous arguments.

The second approach relies on a crucial foundational work by M. Bousquet-Mélou regarding the enumeration of heaps of pieces satisfying both left and right constraints [28, 27]. This work opens the way for two-sided sieves in the same manner as Viennot's Lemma relates to the finite and infinite sieve theorems: they give control over both the left and right prime divisors of a walk. Consequently, the maximum length of the primes to be considered in Eq. (6.3.1) is reduced to only $L/2$. The “sieving gap” between $L$ and $L/2$ dramatically reduces the importance of the error terms to the extent that we expect them all to vanish under the limit $L \to \infty$. Seeing heaps of pieces as an extension of number theory in the vein of Chapter 5, shows that this $L/2$ is the extension of the $\sqrt{x}$ gap present in all standard number-theoretic sieves. We can similarly show that the fraction $F_p \lambda^{-\ell(p)}$ extends the quantity $\log(x)/\log(p)$ and all identities given here extend (and hence reduce to) valid number-theoretic identities. Non-trivial (novel) results on partial sums of the Möbius function also follow heuristically.
# Chapter 7

## Exact enumeration formulas for simple cycles and simple paths

Counting simple paths, that is trajectories on a graph that do not visit any vertex more than once, is a problem of fundamental importance in enumerative combinatorics [128] with numerous applications, e.g. in sociology [172, 33]. In view of the existing research, this problem should be divided into two main subquestions. One concerns the exact enumeration of "short" simple cycles with direct applications in the analysis of real-world networks. The other, more related to enumerative combinatorics (see e.g. [55, 128]), concerns the asymptotic growth of the number of simple cycles of length $ℓ$ on regular lattices as $ℓ$ tends to infinity.

As these two problems have been recognised for a long time, the strategies implemented so far to solve them have been qualitatively different. The practical enumeration of short simple cycles has been tackled via diverse algorithmic and analytic methods, e.g. the inclusion-exclusion principle [11, 22, 103], recursive expressions of the adjacency matrix [105], sieves [13] or immanantal equations [35]. In contrast, the asymptotic growth in the number of long simple cycles on regular lattices has been mostly studied using probability theory [118, 128, 46].

### 7.1 Counting from weakly connected subgraphs

Expressions for counting simple cycles of small lengths on undirected graphs from traces of the adjacency matrix have been discovered by various authors since the 1950's [172, 91, 3]. In 1972, two Ukrainian mathematicians, Khomenko and Golovko, published an exact formula for counting simple cycles of arbitrary length on any graph [105]. The formula results from an elaborate use of the inclusion-exclusion principle and involves a function defined through a complicated recursion. Possibly owing to its inherent difficulty and lengthy proof, Khomenko and Golovko's result has remained largely unnoticed. In 2009, the Russian mathematicians Sergey Perepechko and Anton Voropaev managed to greatly simplify the formula of Khomenko-Golovko [159], likely by solving the difficult recursion equation involved in it. The formula obtained by Perepechko and Voropaev, one of the most elegant result of enumerative combinatorics, was only announced in a conference talk and, to the best of our knowledge, never published. While the result only applies to simple cycles, we extend it to count simple paths with any specified end points. This leads to a unification of several known formulas for counting simple paths into a single matrix equation. The generalization of Perepechko and Voropaev's result leads to an important simplification that makes use of the additivity of adjacency matrices of disjoint graphs. Thanks to this property, the generalised formula can be reduced to a summation over connected induced subgraphs. A remarkable consequence is an expression that links the Hamiltonian paths of a graph to its connected dominating sets. From a computational point of view, the formulas obtained are particularly effective for sparse graphs, leading to the best general purpose algorithm for this task, see below and [66].

Perepechko and Voropaev's result can be stated as follows.

**Theorem 7.1.1** (Perepechko-Voropaev, 2009). Let $G = (E, V)$ be an undirected graph on $N$ vertices with adjacency matrix $A$. The number $\pi_{\ell}$ of simple (unoriented) cycles of length $\ell$ is given by

$$ \pi_{\ell} = \frac{1}{2\ell} \sum_{i=2}^{\ell} (-1)^{\ell-i} \binom{N-i}{N-\ell} \sum_{S:|S|=i} \mathrm{Tr}(A_S^{\ell}), \quad 3 \le \ell \le N \quad (7.1.1) $$

where the inner sum runs over all non-empty subsets $S \subseteq V$ of size $i$ and $A_S$ is the adjacency matrix of the induced subgraph of $G$ with vertex set $S$.

Equation (7.1.1) seems to have had little more impact than Khomenko-Golovko's result so far in spite of its deep elegance. This is possibly because it involves a sum over subgraphs, thus producing $\pi_{\ell}$ in $O(N^{\ell} \log N)$
operations [159]. Since the formula was devised primarily within and for a numerical computing community, its value may have been gauged from its sole computational cost.

The alternating signs in the Perepechko-Voropaev formula bears similarities with Bax's approach for counting Hamiltonian paths [11], based on the inclusion-exclusion principle. In fact, applying the trace operator to the matrix $H_n$ defined in [11] recovers exactly the Perepechko-Voropaev formula for $\ell = N$. In this section we show how these two results, among others, can be summarised into a single matrix equation. Consider the matrix $P(z)$ whose $(i, j)$-entry is defined to be the ordinary generating function of simple paths from $i$ to $j$, i.e.

$$P_{ij}(z) = \sum_{\substack{p: i \to j \\ p \text{ simple}}} p z^{\ell(p)},$$

for $z$ a formal variable. The information relative to simple paths and simple cycles on the digraph is entirely summarised in $P(z)$, making it a natural object of interest. Our first result gives an expression of $P(z)$ in function of the labeled adjacency matrices of the induced subgraphs of $G$. For clarity, we distinguish between open and closed paths, by writing $P(z) = P_{\text{cl}}(z) + P_{\text{op}}(z)$, where

- $P_{\text{cl}}(z)$ is the matrix generating series of simple cycles. Its $i$-th diagonal entry is the generating function of the simple cycles visiting $i$, while the entries outside the diagonal are zero.

- $P_{\text{op}}(z)$ is the generating matrix of open simple paths. For $i \neq j$, its $(i, j)$-entry is the generating function of simple paths from $i$ to $j$, and its diagonal is zero.

For a square matrix $M$, we denote by $\text{Diag}(M)$ the diagonal matrix obtained by setting to zero all non-diagonal entries in $M$. We are now in position to state our first result.

**Theorem 7.1.2.** It holds

$$i) P_{\text{op}}(z) = \sum_{S \in \mathcal{S}} (zW_S)^{|S|-1} (\text{Id} - zW_S)^{N-|S|},$$

$$ii) P_{\text{cl}}(z) = \sum_{S \in \mathcal{S}} \text{Diag} \left( (zW_S)^{|S|} (\text{Id} - zW_S)^{N-|S|} \right),$$

where $|S|$ denotes the cardinality of $S$.

**Remark.** We recover Perepechko-Voropaev's formula by attributing the value $\omega_{ij} = 1$ to all directed edges, thus replacing $W$ by $A$, and taking the trace of $P(z)$ in Theorem 7.1.2.

## Counting simple paths from weakly connected sets

A digraph is said to be weakly connected if replacing all its directed edges by undirected edges produces a connected undirected graph. The expression of $P(z)$ can be reduced to a sum over weakly connected subgraphs of $G$ owing to the simple property that the adjacency matrix of a digraph with more than one weakly connected component is block diagonal. In particular, letting $G(S) = G(C_1) \cup \dots \cup G(C_k)$ be the decomposition of $G(S)$ into weakly connected components, we have for all $n \ge 1$, $W_S^n = W_{C_1}^n + \dots + W_{C_k}^n$. This simple observation leads to a profound reduction in the summation over induced subgraphs in Perepechko-Voropaev's formula which we first obtained in [72].

Let $C \subseteq S$ denote the non-empty subsets of $V$ for which the resulting induced subgraph is weakly connected. For $C \in \mathcal{C}$, the weak neighborhood $N(C)$ of $C$ in $G$ is the set of vertices in $V \setminus C$ that can reach and/or be reached from $C$ in one step. Formally,

$$N(C) = \{i \in V \setminus C : \exists j \in C, (i, j) \in E \text{ and/or } (j, i) \in E\}.$$

Of course, this definition recovers the classical definition of neighborhood in undirected graphs.

**Theorem 7.1.3.** The matrix generating series of open and closed simple paths verify:

$$i) P_{\text{op}}(z) = \sum_{C \in \mathcal{C}} (zW_C)^{|C|-1} (\text{Id} - zW_C)^{|N(C)|}$$

$$ii) P_{\text{cl}}(z) = \sum_{C \in \mathcal{C}} \text{Diag} \left( (zW_C)^{|C|} (\text{Id} - zW_C)^{|N(C)|} \right)$$
**Remark.** On an infinite regular lattice $G$ such as the square lattice, Theorem 7.1.3 relates the ordinary generating function of the Self-Avoiding Polygons (SAPs) with respect to their length, with a generating function of the polyominos involving both their perimeters and their areas. Remarkably, the asymptotic behaviours of both sides of the formula are the subjects of famous open conjectures.

$$ \sum_{\gamma \in \text{SAP}(G)} \ell(\gamma) z^{\ell(\gamma)} = \sum_{p \text{ polyomino}} \text{Tr} \left( (z \mathbf{A}_p)^{\mathbf{A}(p)} (\mathbf{I}_d - z \mathbf{A}_p)^{\mathbf{P}(p)} \right). $$

Here $z$ is a formal variable, $\mathbf{A}_p$ is the adjacency matrix of the subgraph of $G$ covered by the polyomino $p$, $\mathbf{A}(p)$ is the area of $p$ and $\mathbf{P}(p)$ its perimeter.

Another direct application of theorem 7.1.3 concerns Hamiltonian paths, i.e. simple paths of maximal length, which appear in the terms of maximal degrees in the expressions of $\mathbf{P}_{\text{op}}(z)$ and $\mathbf{P}_{\text{cl}}(z)$. From the formulas in Theorem 7.1.3, the terms of maximal degrees correspond to connected subsets $C$ such that $C \cup N(C) = V$, i.e. dominating sets. This leads to an expression of the number of Hamiltonian paths that only involves the connected dominating sets of $G$. For the next result, we denote by $\mathbf{H}$ the Hamiltonian path counting matrix, whose $(i, j)$-entry gives the number of Hamiltonian paths from $i$ to $j$.

**Proposition 7.1.1.** Let $\mathcal{D}$ be the set of weakly connected dominating sets in $G$,

$$ \mathbf{H} = \sum_{D \in \mathcal{D}} (-1)^{N-|D|} \left( \mathbf{A}_D^{N-1} + \frac{\text{Tr}(\mathbf{A}_D^N)}{N} \mathbf{I}_d \right). $$

The number of (oriented) Hamiltonian cycles appears in any diagonal entry of $\mathbf{H}$,

$$ \pi_N := \frac{1}{N} \sum_{D \in \mathcal{D}} (-1)^{N-|D|} \text{Tr}(\mathbf{A}_D^N), $$

where $N - |D|$ can be replaced by $|N(D)|$ due to the dominating property. This expression improves on Bax's and Khomenko and Golovko's (Theorem 4 in [105]) results for Hamiltonian cycles in that the sum is restricted to connected dominating sets. Similarly, the total number of open Hamiltonian paths follows by summing all non-diagonal entries of $\mathbf{H}$.

Open and closed Hamiltonian paths can be dealt with separately yielding a slightly stronger version of the result, namely

$$ \mathbf{H}_{\text{op}} = \sum_{D \in \mathcal{D}} (-1)^{N-|D|} \mathbf{A}_D^{N-1} \quad \text{and} \quad \mathbf{H}_{\text{cl}} = \frac{1}{N} \sum_{D \in \mathcal{D}} (-1)^{N-|D|} \text{Tr}(\mathbf{A}_D^N) \mathbf{I}_d. $$

From a computational point of view, the restriction to weakly connected subgraphs and weakly connected dominating sets provides a clear improvement for counting simple cycles, simple paths and Hamiltonian paths, especially for sparse graphs for which connected induced subgraphs are relatively rare. This observation is made rigorous by the analysis presented in the next section.

## 7.2 Algorithmic analysis of the counting formulae

Counting Hamiltonian cycles and, more generally, all simple cycles passing through a given vertex is a #P-complete problem [194, 31]. The same classification holds for the problem of counting simple paths with fixed endpoints. Unsurprisingly, the best existing algorithms for counting such cycles have time complexities $O(2^N \text{poly}(N))$, which scales exponentially with the number $N$ of vertices on the graph. Under the exponential time hypothesis [98], this exponential scaling is, in principle, the best possible.

Although evaluating the asymptotic running time of an algorithm in the worst case scenario is necessary for the classification of algorithmic performance, it is of little relevance to applications which differ significantly from this scenario. This is precisely the case when counting or enumerating simple cycles or simple paths. Real-world networks, be they from sociology, biology or chemistry, are typically very sparse. At the opposite, the worst case scenarios for this task—the complete graphs—are dense and counting or finding cycles and paths of any kind on them presents no interest. An algorithmic implementation of the results of Theorem 7.1.3 especially tailored for sparse graphs is therefore highly desirable.

In applications it is typically sufficient to count only those simple cycles whose length does not exceed some maximum value $\ell$, usually much smaller than the graph size $N$. Yet, even with these restrictions, the problem of counting these objects is known to be difficult:

**Theorem 7.2.1** (Flum and Grohe [56]). Counting simple cycles and simple paths of length $\ell$ on both directed and undirected graphs, parameterised by $\ell$, is #W[1]-complete.
The complexity classes #W[t], $t \ge 1$, introduced by Flum and Grohe, are relevant for parameterised counting problems corresponding to the classes of the W-hierarchy [44] which, in turn, qualify the difficulty of parametrised decision problems according to the type of circuits needed to determine them. Importantly, the class #W[1] is believed to strictly contain the class #W[0] of all fixed-parameter tractable (FPT) counting problems. We recall that a counting problem P with input x is said to be fixed-parameter tractable if there is a computable function f of the parameter k, a constant c and an algorithm solving P in $f(k)$ poly(|x|) steps. In this expression, |x| designates the size of the input [56, 85]. For the sake of simplicity, an algorithm achieving a $f(k)$ poly(|x|) asymptotic running time will be said to be FPT.

An algorithm for counting simple cycles and simple paths stems from implementing the formulas of Theorem 7.1.3. Concretely, this was done in MATLAB [65] and PYTHON [144]. The computational complexity of these algorithms is as follows:

**Theorem 7.2.2.** Let $G = (V, E)$ be a graph, possibly directed, on $N$ vertices and $M$ edges. Let $|S_\ell|$ be the number of connected induced subgraphs of $G$ on at most $\ell$ vertices. Let $\Delta$ be the maximum degree of any vertex on $G$ or, if $G$ is directed, let $\Delta$ be the maximum degree of any vertex on the undirected version of $G$. Then all the simple cycles of length up to $\ell$ on $G$ can be counted in time

$$O(N + M + (\ell^{\omega} + \ell\Delta)|S_{\ell}|),$$

and $O(N + M)$ space. In this expression, $\omega$ is the exponent of matrix multiplication. The same complexity is achieved when counting the simple paths of length up to $\ell$ or the simple cycles/paths with fixed endpoints of length up to $\ell$.

The important result of Theorem 7.2.2 is that the asymptotic running time of the general purpose algorithm presented here scales as poly($\ell$)$|S_\ell|$. In comparison, we show in Section 7.2 that the running times of all other general purpose algorithms scale either with $N^\ell$, and $N^\ell > |S_\ell|$, or with the number $|Cycle_\ell|$ of simple cycles of length at most $\ell$ on the graph.<fnref n="1" /> From these observations, we expect the algorithm presented here to be the best available for graphs with less connected induced subgraphs than simple cycles, something since then confirmed by experiments and theoretical investigations [66].

## Asymptotic running time

In the worst case scenario, that is the complete graphs $K_N$, Theorem 7.2.2 implies that the time complexity for counting all the simple cycles using the algorithm proposed here is $O(2^N N^\omega)$ since all induced subgraphs are connected, i.e. $|S_N| = 2^N$. This is marginally better than the complexities reported in [103, 13, 12, 179]. However, it is the performance of our algorithm on non-complete graphs that we want to highlight. To this end, it is helpful to recast the time complexity of the algorithm in terms of simple graph parameters.

We can do so by using an upper bound on the number $|S_k|$ of connected induced subgraphs on $k$ vertices that involves the maximum degree of any vertex. This result is due to Uehara:

**Lemma 7.2.1** (Uehara [192]). Let $\Delta$ be the maximum degree of the undirected version $G_{undir.}$ of $G$. Then the number of connected induced subgraphs on exactly $k$ vertices in $G_{undir.}$ is bounded by

$$|S_k| \le N \frac{(e\Delta)^k}{(\Delta - 1)k^2},$$

with $e$ the base of the natural logarithm. It follows that $|S_\ell| = \sum_{k \le \ell} |S_k| = O(N \frac{\Delta^\ell}{(\Delta - 1)\ell^2})$.

Furthermore, on a graph with maximum degree $\Delta$, there are at most $M \le N\Delta$ edges, so that, by Theorem 7.2.2, the time-complexity of counting all the simple cycles of length $k \le \ell$ is upper bounded by

$$O\left(N(\Delta + 1) + (\ell^{\omega} + \ell\Delta)N \frac{\Delta^{\ell}}{(\Delta - 1)\ell^{2}}\right) = O\left(N\Delta + N(\ell^{-1}\Delta + \ell^{\omega-2})\Delta^{\ell-1}\right), \quad (7.2.1a)$$

$$\sim O(N\ell^{-1}\Delta^{\ell}), \quad (7.2.1b)$$

where we used that $\Delta/(\Delta - 1) \le 2$ as soon as the graph has a connected component with at least 3 vertices.

The bound on $|S_\ell|$ obtained from Uehara's work is typically very far from tight, especially on graphs that are far from regular, such as scale-free networks. Consequently, the running time predicted by Eq. (7.2.1b) is typically much larger than that observed in numerical experiments. However, Eq. (7.2.1b) simplifies the analysis of the running time of the algorithm, which will help us compare it with other algorithms for the same task. We now easily verify that the algorithm is FPT on bounded degree graphs. In fact, on such graphs $\Delta = O(1)$, consequently the asymptotic running time scales as $N$, that is the algorithm is fixed parameter linear.

<footnote n="1">¹There is one exception to this observation: by extending an approach of Merris to count Hamiltonian cycles [141], we show in Section 7.2 that all simple cycles can be counted with an asymptotic running time scaling as $\ell t_{imm}(\ell)|S_\ell|$, where $t_{imm}(\ell)$ is exponential in $\ell$. Hence, this extension is still not competitive with the algorithm presented here.</footnote>
# Detailed comparisons with existing algorithms

## Sieve methods

Bax and Bax and Franklin authored two articles detailing the use of combinatorial sieves to count simple cycles [13, 12], which extend previous results by Karp [103] for counting Hamiltonian cycles. Similar techniques had previously been expounded by Khomenko and Golovko [105, 106] and more recently by Perepechko and Voropaev [159, 160]. All these combinatorial sieves produce the simple cycles via sums over all the induced subgraphs of a graph, i.e. including the non-connected ones. There are $\binom{N}{\ell}$ such subgraphs of size $\ell$ on a graph on $N$ vertices. Assuming $\ell$ is fixed and much smaller than $N$, the number of subgraphs is $\Omega(N^\ell/\ell!)$). Consequently, counting all simple cycles of length up to $\ell$ using these sieves takes at least $\Omega(N^\ell/\ell!)$ time. If $\Delta$ is sub-linear in $N$, this time complexity is much larger than the asymptotic running time achieved by the algorithm presented here, which is at most $O(N\Delta^\ell/\ell)$.

## Zeon algebras

An algorithm for counting simple cycles based on zeon algebras has been proposed by Schott and Staples in [179]. The algorithm relies on the observation that if one attaches a formal variable $\xi_e$ to each edge $e$ of the graph, such that any two such variable commute and $\xi_e^2 = 0$, then the corresponding labeled adjacency matrix $(A_\xi)_{ij} := \xi_{ij}A_{ij}$ generates only simple cycles. In other words, $\text{Tr}(A_\xi^\ell)$ is the number of simple cycles of length $\ell$ on $G$. Unfortunately, this method requires formal matrix multiplications and cannot be implemented fully numerically.

Schott and Staples proved that the average time taken by this algorithm to count simple cycles of length $\ell$ is $O(N^4(1+q)^N)$ where $q \ge \ell N\Delta/(N^2 - \ell)$ [179]. In the typical situation where $\Delta, \ell \ll N$, this cost is therefore at least $O(N^4e^{\ell\Delta})$. This is exponential in both $\ell$ and $\Delta$ and scales as the fourth power of $N$, in particular any function $f(N) = O(N\Delta^\ell/\ell)$, such as the asymptotic running time of the algorithm proposed here, obeys $f(N) = o(N^4e^{\ell\Delta})$.

## Counting using immanants

In 1983, R. Merris discovered an exact formula for counting the Hamiltonian cycles of a graph from a sum over at most $N$ of its immanants [141, 142]. On noting that any simple cycle is Hamiltonian on a unique connected induced subgraph of the graph, Merris' formula is easily extended to count all simple cycles of length up to $\ell$ via a sum over the $|S_\ell|$ connected induced subgraphs of size at most $\ell$. In this sum, each term is itself a sum over at most $\ell$ immanants. Therefore, evaluating the formula takes $O(t(|S_\ell|) + t_{\text{imm}}(\ell)|S_\ell|)$ time, with $t(|S_\ell|)$ and $t_{\text{imm}}(\ell)$ the times taken to find the connected induced subgraphs on at most $\ell$ vertices and to calculate the required immanants of $\ell \times \ell$ matrices, respectively.

In the same spirit, G. Cash described in 2007 an approach for counting simple cycles by solving a system of equations involving selected immanantal polynomials of the graph [35]. For length $\ell$ simple cycles, Cash's approach stems from the solution of a system involving $p(\ell) - p(\ell - 1)$ equations, where $p(\ell)$ is the number of integer partitions of $\ell$. This number grows as $\Theta(e^{x\sqrt{\ell}\ell^{-3/2}})$ with $x = \pi\sqrt{2/3} \sim 2.6$ and consequently solving the system takes $O(e^{7.7\sqrt{\ell}\ell^{-9/2}})$ time. Since the immanantal polynomials of the graph take $O(t_{\text{imm}}(N))$ time to calculate, the cost of Cash's approach is $O(t_{\text{imm}}(N)e^{7.7\sqrt{\ell}\ell^{-9/2}})$.

The time complexities of both methods are primarily influenced by the time taken to calculate the required immanants. Unfortunately, these are difficult to obtain. First, as recognised by Cash, they require computing the matrix of irreducible representations of the symmetric group $S_x$, a very costly task for large $x$. Second, while the determinant of an $x \times x$ matrix requires only $O(x^3)$ time, the second immanant $d_2$ already costs $O(x^c)$ with $3 < c \le 4$ and computing the last immanant, the permanent, is itself a \#P-complete problem [193]. The permanent is required by both Merris' and Cash's approaches, meaning that, assuming the exponential time hypothesis, $t_{\text{imm}}(x)$ grows exponentially in $x$. Comparing with Theorem 7.2.2, we observe that neither approach can compete with the algorithm proposed here. The results we present in the next section are in the same vein, as they involve combinations of permanents and determinants summed over the set of induced subgraphs of a graph, of which there are $\Theta(N^\ell)$.

## Counting short simple cycles on undirected graphs

When only short simple cycles on *undirected graphs* are of interest, these may be counted via a set of special identities involving the adjacency matrix. This approach was pioneered by Harary and Manvel in the 1970s and has remained popular ever since [91, 3, 37, 149]. The principle of this approach is to distillate the number of simple cycles of length $k$ from the number of walks of length $k$, by removing all closed walks which are not simple from the count. For example, if one wishes to count all the squares, one must count all closed walks of length four, that is $\text{Tr}(A^4)/4$, and remove from those all closed walks of the forms $1 \to 2 \to 1 \to 2 \to 1$ or $1 \to 2 \to 1 \to 3 \to 1$ and $1 \to 2 \to 3 \to 2 \to 1$. The former type of walks traverses a single edge twice, thus is counted by $|E|/2$. The two latter types of walks traverse adjacent edges, of which there are $\sum_{i \in G} \binom{\text{deg}(i)}{2}$ with
deg(i) the degree of vertex i. Taken together, these results indicate that the number of squares is

$$n_{\text{squares}} = \frac{1}{4} \text{Tr}(\mathbf{A}^4) - \sum_{i \in G} \binom{\text{deg}(i)}{2} - \frac{1}{2} |E|.$$

Similar identities exist for longer simple cycles but the number of terms they involve grows exponentially with the length of the simple cycles being counted. Alon, Yuster and Zwick presented an algorithm for evaluating these identities up to $\ell = 7$ in $O(N^\omega)$ time and $O(N^2)$ space [3]. This cost grows for longer cycles, being $O(N^{\omega+1})$ when $\ell = 8$, and then $O(N^{\ell/2}) \log N)$ when $\ell = 9, 10$. To the best of our knowledge, no special identity for counting $\ell > 17$ cycles has been found. Although such identities must exist, we note that that for $\ell = 17$ comprises over $10^5$ terms and is already far beyond what is concretely usable on large real-world networks.

Finally, we note that the space required for running AYZ scales as $O(N^2)$ rather than $O(N+M)$, the former being much larger than the latter on sparse graphs. We found this to be AYZ main limitation in practice,<fnref n="2" /> barring us from making computations on networks with over 12,000 nodes. This memory cost is unavoidable since AYZ necessitates the computation of powers of the adjacency matrix A of the graph (not just their traces), which quickly become dense even on large sparse graphs. Recall in particular, that $A^x$ is full for $x$ larger than the graph diameter.

## Counting simple cycles via enumeration

Enumerating the simple cycles or simple paths of a graph, that is producing their vertex sequences, is much more time consuming than simply counting them. The best general purpose algorithm for this task is still Johnson's 1975 landmark algorithm [101, 137], which achieves an asymptotic running time of $O((N+M)(|\text{Cycle}_N|+1)) \sim O(N\Delta|\text{Cycle}_N|)$. In this expression, $|\text{Cycle}_N|$ is the total number of simple cycles (or of simple paths) on G, including backtracks, that is simple cycles of length 2. This result was recently improved on undirected graphs to $O(N(|\text{Cycle}_N|+1)+M)$, a scaling which is optimal for this task [21].

In the worst case scenario, i.e. on the complete graph $K_N$, $|\text{Cycle}_N| = O(N!)$, that is enumerating all simple cycles takes factorial time. For this reason, counting simple cycles via enumeration has often been deemed greatly inefficient, in particular in comparison with the “only” exponential cost $O(2^N \text{poly}(N))$ achieved by the algorithm presented here as well as other approaches [12]. This conclusion follows from a peculiarity of dense graphs however and for sparse graphs it is not so. Indeed, using the results of Theorem 7.1.3 to count all the simple cycles on a graph costs $O(N^\omega|S_N|)$. It follows that if $N^\omega|S_N| \ge N\Delta|\text{Cycle}_N|$, then Johnson's algorithm and its variants can count all the simple cycles of a graph via enumeration faster than any combinatorial sieve, including the one presented here. When counting simple cycles of fixed maximum length $\ell$, Johnson's algorithm takes $O(N+M+(\ell+\ell\Delta)|\text{Cycle}_\ell|)$ time, $|\text{Cycle}_\ell|$ being the total number of simple cycles of length up to $\ell$. This means in order for the algorithm presented here to be faster than Johnson's the following must hold $(1+\ell^{\omega-1/\Delta})|S_\ell| \le |\text{Cycle}_\ell|$.

## 7.3 Counting via convolutions over induced subgraphs

Let $\mathcal{G}$ be the set of finite digraphs. For $G = (V(G), E(G)) \in \mathcal{G}$, we say that $H = (V(H), E(H)) \in \mathcal{G}$ is an induced subgraph of $G$ if $V(H) \subseteq V(G)$ and $E(H) = E(G) \cap V(H)^2$. If $H \prec G$, then $G-H$ designates the subgraph of $G$ induced by $V(G) \setminus V(H)$. Let $(\mathcal{A}, \cdot, +)$ be an algebra, for two functions $\phi, \psi : \mathcal{G} \to \mathcal{A}$, the induced subgraph convolution between $\phi$ and $\psi$ is defined by

$$(\phi * \psi)[G] = \sum_{H \prec G} \phi[H] \psi[G-H], \quad G \in \mathcal{G},$$

where the sum runs over all induced subgraphs of $G$ including the empty graph $\emptyset$ and $G$ itself. In this section, we investigate the induced subgraph convolution between function with values in the algebra $\mathbb{R}\langle\mathcal{H}\rangle$ of formal series on hikes with real coefficients. Examples of such functions arising from usual expressions of the labeled adjacency matrix $W_H$ of a digraph $H$ have been discussed in Section 5.3.

Our first result is a Mbius inversion relation involving the subgraph convolution:

**Lemma 7.3.1.** For all $G \in \mathcal{G}$,

$$\sum_{H \prec G} \det(-W_H) \text{perm}(W_{G-H}) = \delta[G] := \begin{cases} 1 & \text{if } G = \emptyset \\ 0 & \text{otherwise,} \end{cases}$$

where we use the convention $\text{perm}(W_\emptyset) = \det(-W_\emptyset) = 1$.

<footnote n="2">²That is, beyond the fact that AYZ is limited to $\ell = 7$ on undirected graphs.</footnote>
The function $\delta$ is the identity function for the induced subgraph convolution *, in view of $\phi * \delta = \phi$ for all $\phi: G \to \mathbb{R}\langle H\rangle$. Thus, the lemma establishes that the functions $G \mapsto \text{perm}(W_G)$ and $G \mapsto \det(-W_G)$ are mutual inverse through *. The proof of the Lemma relies on the expression of the permanent and determinant from formal series on self-avoiding hikes, that is on the number-theoretic structure underlying the combinatorics of hike monoids.

**Corollary 7.3.1.** For all $G \in \mathcal{G}$,

$$ \sum_{H \prec G} \text{perm}(W_H) \det(\text{Id} - W_{G-H}) = \sum_{H \prec G} \text{perm}(\text{Id} + W_H) \det(-W_{G-H}) = 1. $$

Seeing these sums as convolutions makes the proof almost trivial. Letting $\phi[H] = \det(-W_H)$ and $\psi[H] = \text{perm}(W_H)$, the equations of Corollary 7.3.1 read

$$ \psi * (\phi * 1) = 1 \text{ and } \phi * (\psi * 1) = 1. $$

The result follows directly from Lemma 7.3.1, using the distributivity and commutativity of the convolution. We now derive an expression of the formal series of Hamiltonian cycles. In the spirit of [139], we introduce the derivation operator $D$ defined by

$$ D \sum_{h \in \mathcal{H}} f(h)h = \sum_{h \in \mathcal{H}} \ell(h)f(h)h. $$

This leads to the following theorem for counting the Hamiltonian cycles on $G$.

**Theorem 7.3.1.** Let $\Gamma_G$ denote the set of primes with support exactly $V$, that is the set of Hamiltonian cycles on $G$. Let $\pi[G] := \sum_{\gamma \in \Gamma_G} \gamma$. Then

$$ D\pi[G] = \sum_{H \prec G} \det(-W_H) D \text{perm}(W_{G-H}) = - \sum_{H \prec G} \text{perm}(W_H) D \det(W_{G-H}). $$

The theorem is proven on expressing the determinants and permanents above as series over the self-avoiding hikes and using the properties of the walk von Mangoldt function.

**Remark.** Because $\phi$ is the inverse of $\psi$, the relation $D\{\pi\} = \phi * D\{\psi\}$ suggests an expression for $\pi$ as a logarithm of $\psi$. This is indeed the case. Observe that the $k$-times convolution

$$ \pi^{*k}[G] := \underbrace{\pi * \cdots * \pi}_{k \text{ times}} [G] = \sum_{(H_1, \dots, H_k)} \pi[H_1] \cdots \pi[H_k], $$

writes as the sum over all $k$-partitions $H_1, \dots, H_k$ of $G$ (here, the order is important meaning that there are $k!$ partitions involving the subgraphs $H_1, \dots, H_k$). Thus, every spanning self-avoiding hike $h$ is counted exactly once in the exponentiation

$$ \exp_*(\pi[G]) = \sum_{k \ge 0} \frac{1}{k!} \pi^{*k}[G] = \psi[G]. $$

This aspect originates from an Hopf algebraic structure, which we describe in the next section.

The formal series of simple cycles (of any length) follows from the convolution of $\pi$ with the constant 1,

$$ \Gamma[G] := (\pi * 1)[G] = \sum_{H \prec G} \pi[H] = \sum_{\gamma \in \Gamma_G} \gamma, $$

Because derivation and convolution with the constant are commuting operators, we recover

$$ D\Gamma = D\{\pi * 1\} = D\{\pi\} * 1 = (\phi * D\psi) * 1 = \phi * D\{\psi * 1\} = \phi * D\Psi, $$

where $\Psi[G] = (\psi * 1)[G] = \sum_{H \prec G} \text{perm}(A_H) = \text{perm}(\text{Id} + A_G)$. This gives the following corollary to Theorem 7.3.1

**Corollary 7.3.2.** Let $\Gamma_G$ be the set of all primes, i.e. simple cycles, on $G$, then

$$ D \sum_{\gamma \in \Gamma_G} \gamma = \sum_{H \prec G} \det(-W_H) D \text{perm}(\text{Id} + W_{G-H}). $$

We give an alternative approach to this result in the next section. Practical versions of this formula involving the generating function of simple cycles on $G$ as well as the ordinary adjacency matrix of the graph will also be given.
## 7.4 An Hopf algebra structure for the hikes

Since any hike on a graph can be seen as a disjoint ensemble of connected components, it is natural that an algebraic structure should exist describing the generation of arbitrary hikes from connected ones. In particular, when it comes to the self-avoiding hikes, their connected components are their prime factors. Therefore, if this algebraic structure provides a mean of projecting the set of hikes back onto the set of connected hikes, it might send the self-avoiding ones onto the primes. In this section, we establish these heuristic arguments rigorously by showing that a cocommutative Hopf algebra describes the generation of arbitrary hikes from connected ones. This algebra provides several exact formulas for the formal series of connected hikes and of primes, stemming from projectors onto the irreducible elements of the algebra. We also show that the subgraph convolution operation introduced previously is a necessary and unavoidable feature resulting from this algebra.

We denote $K$ an algebraically closed field of characteristic zero, and $K\langle\mathcal{H}\rangle$ is the monoid algebra of $\mathcal{H}$ over $K$, that is essentially the algebra of formal series on hikes. Note that given the isomorphism between such series and linear functions on hikes $f \in \text{Hom}(\mathcal{H}, \mathcal{H})$, from now on we shall not distinguish the two and will conveniently write any series $f \in K\langle\mathcal{H}\rangle$ as $f = \sum_{h \in \mathcal{H}} f(h)$. We designate $\mathcal{C}$ the ensemble of connected hikes.<fnref n="3" />

We endow $K\langle\mathcal{H}\rangle$ with an Hopf algebra structure following Schmitt's construction for general trace monoids [178]. We define the comultiplication $\Delta: K\langle\mathcal{H}\rangle \to K\langle\mathcal{H}\rangle \otimes K\langle\mathcal{H}\rangle$ and counit $\epsilon: K\langle\mathcal{H}\rangle \to K$ by

$$ \epsilon = \begin{cases} 1, & \text{if } h = 1, \\ 0, & \text{otherwise,} \end{cases} \quad \text{and} \quad \Delta(h) = \sum_{d|h: V(d) \cap V(h/d) = \emptyset} d \otimes \frac{h}{d}. \qquad (7.4.1) $$

In particular, the comultiplication introduced above decomposes any hike into its disjoint divisors and recovers that defined by Schmitt on general trace monoids in [178].

Equipped with these operations, $K\langle\mathcal{H}\rangle$ forms a cocommutative coalgebra [178]. Its irreducible elements are immediately seen from Eq. (7.4.1) to be the connected hikes since these have no non-empty disjoint divisors. This further confirms that $\Delta$ pertains to the generation of arbitrary hikes from connected ones. The multiplicative operation between elements of $K\langle\mathcal{H}\rangle$, that is the operation that gives it an algebra structure, is identified by the following Lemma [74]:

**Lemma 7.4.1.** $K\langle\mathcal{H}\rangle$ is isomorphic as an algebra to the commutative algebra formed by functions on graphs equipped with the induced subgraph convolution.

We may now invoke standard general results of [178] to observe that the algebraic and coalgebraic structures of $K\langle\mathcal{H}\rangle$ are compatible, that is $\Delta$ and $\epsilon$ are algebra maps and $K\langle\mathcal{H}\rangle$ is a bialgebra. These results are subsumed in the following theorem, which in addition to the bialgebra structure, provides an antipode for $K\langle\mathcal{H}\rangle$, turning it into a Hopf algebra.

**Theorem 7.4.1.** $K\langle\mathcal{H}\rangle$ is a cocommutative Hopf algebra, with comultiplication and counit defined above and antipode $S$ given $S(h) := (-1)^{c(h)}h$, where $c(h)$ is the number of disjoint connected components of $h$.

The generation of arbitrary hikes from connected ones thus gives rise to an Hopf algebra which, we will see, provides means of doing the opposite, that is to obtain the connected hikes from the set of all hikes. Before we proceed to these results, we note that the same algebraic structure relates the self-avoiding hikes with the primes.

**Corollary 7.4.1.** $K\langle S\rangle$ is a cocommutative sub-Hopf algebra of $K\langle\mathcal{H}\rangle$.

The irreducible elements of $S$ are now easy to discern: they are the irreducible elements of $\mathcal{H}$—the connected hikes—which are also self-avoiding, that is the primes. This observation in conjunction with Corollary 7.4.1 above, implies that any projector from the hikes onto the connected hikes will send the self-avoiding hikes onto the primes. Using standard formula from Hopf algebras we get:

**Theorem 7.4.2.** For any coalgebra map $f \in K\langle\mathcal{H}\rangle$, then $\log_* f: K\langle\mathcal{H}\rangle \to K\langle\mathcal{C}\rangle$, in particular the $*-\logarithm$ of the identity on $\mathcal{H}$ is the identity on $\mathcal{C}$,

$$ \log_* \left( \frac{1}{\det(\mathrm{Id} - W)} \right) = \sum_{h \in \mathcal{C}} h. $$

For any coalgebra map $f \in K\langle S\rangle$, then $\log_* f: K\langle S\rangle \to K\langle\Gamma_G\rangle$, in particular the $*-\logarithm$ of the identity on $S$ is the identity on $\Gamma_G$,

$$ \log_* (\text{perm}(\mathrm{Id} + W)) = -\log_* (\det(\mathrm{Id} - W)) = \sum_{h \in \Gamma_G} h. $$

<footnote n="3">³The notion of connected hike is clear intuitively but a rigorous definition can also be given for it. A hike $h$ is connected iff for any non-empty divisor $d$ of $h$, we have $V(d) \cap V(h/d) \neq \emptyset$.</footnote>
**Example 7.4.1** (Simple cycles from the logarithm of the determinant). Let us illustrate how the logarithm with respect to induced subgraph convolution distillates the simple cycles from a determinant or a permanent. Consider the following graph with three simple cycles a, b and c of arbitrary lengths:

$$G = \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.5, every node/.style={scale=0.5}] 
  \node[circle, fill, inner sep=1pt] (id) at (0,0) {};
  \node[circle, fill, inner sep=1pt] (b) at (1,0) {};
  \node[circle, fill, inner sep=1pt] (a) at (0,1) {};
  \draw[->] (id) -- (b) node[left] {$a$};
  \draw[->] (id) -- (a) node[right] {$b$};
  \draw[->] (b) -- (a) node[right] {$c$};
\end{tikzpicture}$$

for which $\det(\mathrm{Id} - W) = 1 - a - b - c + ac + bc$. Expanding the logarithm of this determinant as a series and focusing on the first and second orders to begin with, we have

$$-\log_* \left( \det(\mathrm{Id} - W) \right) = -(-a - b - c + ac + bc) + \frac{1}{2} (-a - b - c + ac + bc)^2 - \dots \quad (7.4.2)$$

Since $V(a) \cap V(c) = V(b) \cap V(c) = \emptyset$ and $V(a) \cap V(b) \neq \emptyset$, terms such as $a*a, a*b$ and $b*ac$ all vanish and only $a*c$ and $b*c$ are non-zero. Thus, expanding the second order leaves $ac + ca + bc + cb$. For the same reasons all higher orders of the logarithm are exactly zero. In addition, since a and c and b and c are vertex-disjoint, they commute, and the second order further simplifies to $2ac + 2bc$. Thanks to these observations, Eq. (7.4.2) becomes

$$-\log_* \left( \det(\mathrm{Id} - W) \right) = a + b + c - ac - bc + \frac{1}{2} (2ac + 2bc) = a + b + c,$$

which is indeed the formal series of the primes on G.

Admittedly, a *-logarithm is not very convenient to implement. Instead, we turn to its derivative for more practical results

**Corollary 7.4.2.** Let G be a non-empty graph, and $\Gamma := \sum_{h \in \Gamma_G} h$ be the characteristic series of the primes. Then

$$D\Gamma = D \operatorname{perm}(\mathrm{Id} + W) * \det(\mathrm{Id} - W) = -\operatorname{perm}(\mathrm{Id} + W) * D \det(\mathrm{Id} - W).$$

In practice, prime counting is achieved upon replacing all labeled adjacency matrices with ordinary adjacency matrices $W \mapsto zA$, with $z$ a formal variable. In this situation, formal series on hikes become ordinary generating functions and the derivative operator $D$ is implemented as a derivative with respect to $z$. Then, because of the commutativity of the induced subgraph convolution, Corollary 7.4.2 yields the following variant formulas for the derivative of the ordinary generating function of the primes $\Gamma(z) := \sum_{\gamma \in \Gamma_G} z^{\ell(\gamma)}$,

$$\frac{d\Gamma(z)}{dz} = \sum_{H \subset G} \frac{d}{dz} \operatorname{perm}(\mathrm{Id} + zA_H) \det(-zA_{G-H}) = \sum_{H \subset G} \frac{d}{dz} \operatorname{perm}(zA_H) \det(\mathrm{Id} - zA_{G-H}),$$

$$\frac{d\Gamma(z)}{dz} = -\sum_{H \subset G} \operatorname{perm}(\mathrm{Id} + zA_H) \frac{d}{dz} \det(-zA_{G-H}) = -\sum_{H \subset G} \operatorname{perm}(zA_H) \frac{d}{dz} \det(\mathrm{Id} - zA_{G-H}).$$

## Existence of further counting formula from Lie idempotents

The celebrated Milnor-Moore theorem [145] provides an explicit relation between connected graded cocommutative Hopf algebras and Lie algebras. In this section we exploit this relation to assert the existence of many more formulas for counting simple cycles on graphs. We illustrate this with two examples.

The cocommutative Hopf algebra $K\langle\mathcal{H}\rangle$ introduced earlier is both graded, with gradation $c(h)$, and connected since $c(h) = 0 \iff h = 1$ so that $K\langle\mathcal{H}|_{c(h)=0}\rangle$ is just $K$ itself as required [148]. Hence, we can use the theorem of Milnor and Moore to obtain that $K\langle\mathcal{H}\rangle$ is isomorphic to the universal enveloping algebra of the graded Lie algebra formed by the series on connected hikes on the graph, i.e. $K\langle\mathcal{H}\rangle \simeq U(K\langle C\rangle)$ which, for simplicity, we shall write $\mathcal{H} \simeq U(C)$. By the same arguments, we also have $S \simeq U(\Gamma)$. These results provide new tools to pass from $\mathcal{H}$ to the free Lie algebra formed by $C$ and from $S$ to $\Gamma$: the Lie idempotents.

Lie idempotents are symmetrisers projecting the tensor algebra $T(A)$ of a Lie algebra $A$ onto the free Lie algebra. Now recall that the universal enveloping algebra of the Lie algebra $A$ is $U(A) = T(A)/I$, with $I$ the two-sided ideal generated by elements of the form $a \otimes b - b \otimes a - [a, b]$. In particular, if $A$ is free, then a Lie idempotent project $U(A)$ onto $A$ itself. Since both $C$ and $\Gamma$ are free, this reasoning leads to:

**Theorem 7.4.3.** Let $\iota$ be a Lie idempotent. Then

$$\iota: K\langle\mathcal{H}\rangle \to K\langle C\rangle, \\ K\langle S\rangle \to K\langle\Gamma\rangle.$$

We now give two examples of Lie idempotents to illustrate this result.
**Example 7.4.2 (Eulerian idempotent).** Let $A$ be a cocommutative connected graded $K$-bialgebra with product $*$ and let $id_A$ be the identity map on $A$. Then the endomorphism $\epsilon: \log_*(id_A)$ projects $A$ onto the $K$-submodule of primitive elements and is called the Eulerian idempotent of $A$ [83]. Theorem 7.4.2 thus appears to state the Eulerian idempotents on $\mathcal{H}$ and $\mathcal{S}$.

**Example 7.4.3 (Dynkin idempotent).** Let $K$ a commutative $\mathbb{Q}$-algebra and $A$ be a cocommutative connected graded $K$-Hopf algebra with product $*$. Let $S$ be antipode of $A$ and for any $a \in A$ define $E(a) := deg(a)a$, with $deg(a)$ the grade of $a$. Then the endomorphism of $A$ denoted $\partial := S * E$ projects $A$ onto the $K$-submodule of primitive elements and is called the Dynkin idempotent of $A$ [198, 157, 83]. In the context of the self-avoiding hikes, $deg(h) = c(h) = \Omega(h) = \omega(h)$, with $\omega$ the number of distinct prime factors of $h$. Thus the Dynkin idempotent on $S$ reads$^4$

$$ \Gamma = \sum_{h \in S} (-1)^{\Omega(h)} h \sum_{h \in S} \omega(h)h. $$

In fact, this result is recovered from a straightforward argument in the reduced incidence algebra of $S$. Indeed, a direct multiplication of $\Gamma$ with the zeta function of $S$ (i.e. the identity on $S$) gives

$$ \Gamma \zeta_S = \sum_{h \in S} \left( \sum_{\gamma \in \Gamma, \gamma|h} 1 \right) h = \sum_{h \in S} \omega(h)h, $$

and the Dynkin idempotent follows after a Möbius inversion of the above relation.

Many more Lie idempotents have been discovered and can be found in the relevant literature, see e.g. [156, 157, 190, 83] and references therein. By Theorem 7.4.3, each one of them provides a formula for counting the primes, that is the simple cycles, on arbitrary weighted directed graphs.

<footnote>$^4$A similar, though less interesting, relation holds on $\mathcal{H}$ with both $\Omega(h)$ and $\omega(h)$ replaced by $c(h)$. It yields the identity on $\mathcal{C}$.</footnote>
# Chapter 8

## On the *tenuous* relation between walks and their graphs

With the help of dependency graphs, hike monoids provide a mean of discussing the properties of sets of walks and hikes without explicitly referring to the graph on which these exist. Indeed, the dependency graph $H$ of a hike monoid $\mathcal{H}$ encodes the “cycle skeleton” of a digraph $G$, as vertices of $H$ are simple cycles on $G$ and edges in $H$ exist whenever two simple cycles of $G$ share at least one vertex. In particular, sets of closed walks and more generally of hikes on two digraphs $G$ and $G'$ sharing the same hike dependency graph $H$ are related through a bijection. This bijection stems from the isomorphism between their hike monoids $\mathcal{H}_G$ and $\mathcal{H}_{G'}$. Indeed, these monoids have the same presentation because they have the same number of generators (this being the number of nodes in the hike dependency graph $H$) as well as the same commutation relations between these generators (the edges in the complement $H^c$ of $H$). Then $\mathcal{H}_G$ and $\mathcal{H}_{G'}$ are isomorphic and there is a bijection between their sets of words, that is the sets of hikes (and thus of walks) on $G$ and $G'$. Conversely, the existence of an isomorphism between hike monoids $\mathcal{H}_G$ and $\mathcal{H}_{G'}$ implies that $G$ and $G'$ share the same hike dependency graph. Relating graph properties and walk properties is thus equivalent to understanding which hike dependency graphs do exist and what properties of a digraph can we ascertain from its sole hike dependency graph.

Let $\phi$ be the map which to any digraph $G$ associates $\phi(G)$, the dependency graph of the hike monoid of $G$. We say that two digraphs $G_1$ and $G_2$ are $\phi$-equivalent if $\phi(G_1) = \phi(G_2)$ and we denote this by $G_1 \sim_{\phi} G_2$. Any digraph transformation passing between two $\phi$-equivalent digraphs implements an isomorphism between their hike monoids since these two digraphs share the same hike dependency graph. The problem of understanding the relation between graph properties and walk properties can therefore be formulated as two questions on $\phi$:

1. $\phi$-Surjectivity: Given a graph $H$, is there a digraph $G$ such that $\phi(G) = H$?

If this is the case we say that $H$ is realizable and that $G$ realises $H$. Question 1. is equivalent to asking which trace monoid are hike monoids since any graph $H$ is necessarily the dependency graph of a trace monoid.

2. $\phi$-Injectivity: Given a graph $H$ determine $\phi^{-1}(H)$. Equivalently, what are all digraph transformations that induce isomorphisms of hike monoids?

From the examples presented earlier in the introduction we know already that $\phi$ is not injective. A good question is thus to characterise the class $\phi^{-1}(H)$ of all digraphs with hike dependency graph $H$. This, in turn, is equivalent to determining all digraph transformations that induce isomorphisms of hike monoids since any two digraphs in $\phi^{-1}(H)$ are related by such a transformation.

Observe that hike monoids, map $\phi$ and questions 1. and 2. naturally extend to multidigraphs. In fact the set of all graphs realizable by multidigraphs is exactly the set of graphs realizable by digraphs since every digraph is a multidigraph and, for any directed multigraph, we can construct a digraph with identical hike monoid by adding transient vertices in the middle of each directed multi-edge. As a consequence, from now on we work equally with multidigraphs and digraphs referring to both as ‘digraphs’.

### 8.1 Realizable cycle structures in digraphs

Before we address the surjectivity and injectivity questions, we begin with three properties of the map $\phi$ that reduce considerations to connected dependency graphs $H$ and strongly connected multidigraphs $G$:

**Proposition 8.1.1.** Let $G$ be a digraph. We have
is unrealizable for the same reasons barring the square from being realised. In fact, this graph can be seen as the particular case of Proposition 8.1.2 for cycles of length 3. Indeed, the reader may attempt to build a digraph with a triforce dependency graph to see that because of the 3 external vertices, the cycles composing the central triangle necessarily imply the existence of two further cycles sharing vertices with every other cycle hence a pair of vertices connected to all vertices of the triforce, contradicting its structure.

All observations made so far point to realizability as depending solely on the induced cycles of $H$ and their neighborhood, with the need to distinguish long (length $\ell \ge 4$) from short ones (exception of the triforce graph). This is in fact not true; for example the following graph is unrealizable yet possesses neither an induced cycle of length $\ell \ge 4$ nor a triforce of triangles:

<figure><img src="image_19.png" /></figure>

## Surjectivity: which dependency graphs are realizable?

As suggested by our observations so far, understanding the image of $\phi$ is more complicated than it may first appear. Ideally, one would like to have a criterion for deciding if a graph is realizable, i.e. if it is in the image of $\phi$. Such a criterion remains elusive and if it exists, it must be highly non-trivial as we will demonstrate. Nonetheless we here establish that realizability is *decidable* by providing an algebraic condition that is equivalent to it. While this algebraization does not in itself shed additional light on realizability it leads to an algorithm for systematically checking for it.

Given a digraph $G = (V, E)$ and $H = \phi(G)$ its hike dependency graph we have, by definition, that the vertices of $H$ correspond to the simple cycles of $G$. Conversely we may ask under what form do the vertices of $G$ manifest themselves in $H$? Given $v$ a vertex of $G$, all simple cycles of $G$ visiting $v$ share at least this vertex hence do not commute in $\mathcal{H}_G$. This implies that they are all mutually connected by edges in $H$, i.e. they form a clique $\kappa_v$. The fact that vertices of $G$ yield cliques in $H$ leads to the following observations:

i) The set $\{\kappa_v\}_{v \in V}$ is a *clique cover* of $H$, that is each clique $\kappa_v$ is a subgraph of $H$ and every edge and vertex of $H$ appears in at last one $\kappa_v$.

ii) For $W \subseteq V$, the set $\bigcap_{v \in W} \kappa_v \setminus \bigcup_{v \in V \setminus W} \kappa_v$ corresponds to the simple cycles of $G$ with exactly $W$ as vertex set.

Let us now give a criterion equivalent to realizability, discovered by T. Karaboghossian. For $S$ a set, we denote by $\mathcal{C}_S$ the set of permutations over $S$ with cycle decomposition of length 1.

**Theorem 8.1.1.** Let $H$ be a graph. Then $H$ is realizable if and only if there exists a clique cover $\{\kappa_1, \dots, \kappa_n\}$ of $H$ such that the following polynomial system in variables $(m_{ij})_{i,j \in [n]}$ admits an integer solution:

$$ \forall W \subseteq [n], \quad \sum_{\sigma \in \mathcal{C}_W} \prod_{v \in W} m_{v,\sigma(v)} = |\mathcal{K}_W|, \qquad (8.1.3) $$

where $\mathcal{K}_W := \bigcap_{v \in W} \kappa_v \setminus \bigcup_{v \in [n] \setminus W} \kappa_v$. In this case, $H$ is realised by the digraph $G$ with vertex set $[n]$ and adjacency matrix $A$ defined by $A_{i,j} := m_{i,j}$ for $1 \le i, j \le n$.

### Corollary 8.1.1. Realizability is decidable.

We can ignore clique covers such that $\kappa_i \subseteq \kappa_j$ for some $i \neq j$. Indeed, if for such a clique cover the system (8.1.3) admits an integer solution, then no cycles would pass by the vertex $i$ in the associated digraph, since we have $|\mathcal{K}_W| = 0$ for any $W$ containing $i$. Hence the digraph obtained by removing vertex $i$ still realises $H$ and corresponds to the clique cover obtained by removing the clique $\kappa_i$. In the sequel, we call trivial any clique $\kappa_i$ such that $\kappa_i \subseteq \kappa_j$ for some $j \neq i$.

We can deduce the following corollary from Theorem 8.1.1.

### Corollary 8.1.2. All trees are realizable.

As mentioned in Corollary 8.1.1, realizability is decidable: an algorithm checking for it can work through all possible cliques covers of a graph $H$, verifying for each such cover if the accompanying system (8.1.3) admits an integer solution.

Using Proposition 8.1.2 (p. 73) to test for non-realizability and with ad-hoc arguments in remaining undecided cases, we computed the number of unlabelled connected realizable graphs with up to 7 vertices as (OEIS
A348365, computations based on the list of unlabelled connected graphs available at http://users.cecs.anu.edu.au/~bdm/data/graphs.html and [138].)

$1, 1, 2, 5, 15, 58, 265.$

In comparison, the number of unlabelled connected graphs on up to 7 vertices is known to be (OEIS A001349)

$1, 1, 2, 6, 21, 112, 853.$

Whilst most graphs are realizable for small number of vertices this changes when more vertices are considered. We conjecture that the proportion of realizable graphs on *n* vertices with respect to all unlabelled connected graphs on *n* vertices decreases as *n* increases.

We conclude this section by an observation about those graphs that are unrealizable. Since they are not, we might think that the elements of the corresponding trace monoids $\mathcal{T}$ cannot be drawn as cycles on a digraph and are therefore essentially different from walks and hikes. This however is incorrect:

**Proposition 8.1.3.** Let $H$ be a graph that is unrealizable. Then there exist at least one realizable graph $H'$ such that $H$ is an induced subgraph of $H'$. Equivalently, let $\mathcal{T}$ be a trace monoid that is not a hike monoid. Then $\mathcal{T}$ is a submonoid of a hike monoid $H'$.

This indicates that elements of $\mathcal{T}$ are walks and walk-like objects after all, yet these are not renewable as such by themselves. Perhaps more strikingly, since $\mathcal{T}$ is a monoid in its own right it is algebraically closed. Elements of $H'\setminus\mathcal{T}$ are, in this sense, algebraically unrelated to those of $\mathcal{T}$. Yet allowing these additional elements turns the undrawable members of $\mathcal{T}$ into drawable objects. As a corollary there cannot be a forbidden induced-subgraph criterion for realizability.

<figure><img src="image_20.png" /><figcaption>Figure 8.2: An example of Proposition 8.1.3, graph $H$ is unrealizable yet appears as an induced subgraph of $H'$ which is realised by the digraph $G'$ shown on the right.</figcaption></figure>

**Injectivity: graphs with isomorphic hike monoids**

We now turn to question 2 pertaining to $\phi$-injectivity, that is we seek to find a description of $\phi$-equivalence. In [58] we present two sufficient conditions for two digraphs to be $\phi$-equivalent, but also show that these fail to be necessary. Relying on the sufficiency of these conditions we obtain sets of transformations that reduce the number of vertices and edges in digraphs while preserving their hike dependency graphs. For example, we obtain that the problem of realizability is reducible to cubic graphs, that is digraphs where all vertices have total degree 3:

**Proposition 8.1.4.** A graph is realizable if and only if it is realizable by a cubic graph.

This and the other transformations found give us a potential characterisations of $\phi$-equivalence: $G_1 \sim_{\phi} G_2$ if and only if $G_1$ and $G_2$ reduce to the same cubic graph after recursively applying transformations preserving the hike monoidal structure. The cubic graph so obtained would then be a canonical representative of the $\phi$-equivalent class $\phi^{-1}(H)$ to which $G_1$ and $G_2$ belong. For example, all complete graphs on $n$ vertices $H = K_n$ are realizable, being realised by the cubic ladder digraph $L_n$,

<figure><img src="image_21.png" /></figure>

which satisfies $\phi(L_n) = K_n$ for $n \ge 3$. The graph $K_n$ is also realised by the bouquet graph $B_n$ on $n$ self-loops attached to the same vertices, as predicted by other transformations.

Unfortunately while it is true that two digraphs reducing to the same digraph are necessarily $\phi$-equivalent, the converse proposition does not hold. For example the following three digraphs are realizations of the complete graph on 17 vertices $K_{17}$, yet do not reduce to the same digraph,
<figure><img src="image_22.png" /></figure>

More generally we found that for most graph theoretic properties, we could construct a realization of $K_n$ that has the property and another that does not have it. For example both of the following digraphs realise $K_{12}$

<figure><img src="image_23.png" /></figure>

yet $G_1$ is vertex-transitive while $G_2$ is not, $G_2$ is planar and $G_1$ is not; or consider the flower graph $F_n$ on $n$ petals

<figure><img src="image_24.png" /></figure>

for which $\phi(F_n) = K_{n^2+1}$. Flower $F_n$ has a highly skewed degree distribution while that of the ladder $L_{n^2+1}$ is uniform; etc. This means that even considering the purportedly simpler case of the complete graphs $H = K_n$, we still find a profusion of $\phi$-equivalent graphs which do not seem to be related to one another in any obvious way. These observations show that to pursue a full characterisation of $\phi$-equivalence we need an exhaustive description of the hike dependency graphs of all graphs with in- and out-degrees at least 2. We could not find such a description-and a plethora of cases make this task clearly daunting.

## 8.2 Simple graphs do not relate well with their simple cycles

We recall that $P_G = (\mathcal{H}, \leq)$ denotes the poset of hikes $\mathcal{H}$ partially ordered by left division: $h \leq h' \iff h|h'$. Observe that the minimal elements of $P_G$ are the simple cycles and two simple cycles $c, c'$ commute if and only if there exists $h$ such that $c \leq h$ and $c' \leq h$. Thus, knowing the poset $P_G$ reduces exactly to knowing the simple cycles and their commutativity relations (i.e. the pairs of intersecting cycles). We now aim to characterise the precise information on a digraph $G$ that is contained in its hike poset $P_G$.

Let $A$ denote the adjacency matrix of $G$. Replacing $W$ by $zA$, for $z$ a formal variable, in Eq. (5.2.4) yields a slight modification of the characteristic polynomial of $G$ by $\det(\mathrm{Id} - zA) = \sum_{h \in \mathcal{H}} \mu(h) z^{\ell(h)}$. This expression indicates that knowing the poset $P_G$, along with the length function $\ell: P_G \to \mathbb{N}$, suffices to recover the spectrum of a digraph $G$ of known size $N$. On the other hand, the information given by the hike structure $(P_G, \ell)$ is not sufficient to reconstruct $G$ exactly. For instance, all acyclic digraphs on $N$ vertices have their hike posets reduced to $\{1\}$ and are therefore indistinguishable from their hike structure. Things are somewhat different for undirected graphs which are in fact characterised by their hike structure, provided they contain no isolated vertex and all information about their backtracks is retained. Since the connected components of $G$ are apparent in $P_G$, we shall assume that $G$ is connected without loss of generality.

**Proposition 8.2.1.** Let $G$ be a connected simple graph. Then, the hike structure $(P_G, \ell)$ determines $G$ uniquely up to isomorphism.

Of course, the length function provides a significant amount of information and the question remains to know whether an undirected graphs $G$ with no isolated vertex can be reconstructed from the poset $P_G$ only. This turns out to be the case for all undirected graphs but two exceptions: $K_3$, the complete graph on 3 vertices and $K_{1,5}$, the complete bipartite graph on 1 and 5 vertices.

**Theorem 8.2.1.** Let $G$ be a connected bi-directed digraph with no self-loop. The hike poset $P_G$ determines $G$ uniquely up to isomorphism, unless $G \in \{K_3, K_{1,5}\}$.

The proof of the theorem relies exclusively on simple cycles of length 2 (called backtracks) sustained by every undirected edge $\{i, j\}$ on $G$. Vertices of the hike dependency graph $H$ of $G$ corresponding to backtracks in $G$ can always be identified even though the lengths of the simple cycles corresponding to the vertices of $H$ are not
known (with the single exception $H = K_5$ leading to the {$K_3, K_{1,5}$} special case). Now the induced subgraph of $H$ formed by the backtracks is the line graph $L(G)$ of $G$, which is well known to determine $G$ uniquely. In this context, the condition that the graph contains no self-loop is crucial. Indeed, when the length is unknown, a self-loop is indistinguishable from a pendent edge, i.e. an edge with an endpoint of degree one in $G$.

While this result seems to be quite powerful at first glance, the seemingly harmless assumption that the graph is bidirected (i.e. effectively undirected, that is simple) is essential. Should even a single edge be directed the theorem would completely fail to hold. In other terms, the theorem makes no use of longer simple cycles, so much so that if the information regarding the backtracks is discarded from $H$, that is we only have access to $\phi(G)\setminus L(G)$, then graphs suffer from exactly the same shortfalls as directed graphs when it comes to relating them to their closed walks. That is,

* There are graphs $G$ and $G'$ with $\phi(G)/L(G) = \phi(G')/L(G')$ and $G$ and $G'$ do not share fundamental graph theoretic properties. See Figure 8.3 below.

<figure><img src="image_25.png" /><figcaption>Figure 8.3: A pair of graphs with $\phi(K_4)/L(K_4) = \phi(B_7)/L(B_7)$, graph $K_4$ on the left is Hamiltonian and vertex-transitive but not bipartite unlike the bouquet graph $B_7$ on the right, which is bipartite and neither Hamiltonian nor vertex-transitive.</figcaption></figure>

* Given a graph $H$, deciding whether there exists a graph $G$ such that $H = \phi(G)/L(G)$ is widely open.

These issues are pressing since many tools of modern network analysis and algebraic graph theory explicitly disregard or forbid backtracks. This includes backtrackless walks methods [10], Ihara zeta function and primitive orbits [188] and open problems about graphs and cycles, foremost among which is the cycle double cover conjecture [100].

## 8.3 Invariants of hike monoids

Recall that for a digraph $G$, $H = \phi(G)$ is the dependency graph of its hike monoid, which is the trace monoid generated by its simple cycles under the partial commutation rule that two cycles commute if and only if they share no vertex.

Given that isomorphisms of hike monoids implement profound changes on digraphs, it is worth investigating quantities left invariant by these isomorphisms. The first type of such invariants are algebraic quantities based on the adjacency matrix.

**Proposition 8.3.1.** Let $G$ and $G'$ be two $\phi$-equivalent digraphs and let $A$ and $A'$ be their adjacency matrices, respectively. Then:

$$1) \det(\mathbf{Id} - A) = \det(\mathbf{Id}' - A'),$$

$$2) \operatorname{perm}(\mathbf{Id} + A) = \operatorname{perm}(\mathbf{Id}' + A'),$$

where $\mathbf{Id}$ and $\mathbf{Id}'$ are identity matrices of appropriate sizes.

The proposition is proven on expliciting the above invariants as hike series over self-avoiding hikes, which are completely and solely determined by the hike dependency graph. The list of algebraic invariants provided above is not exhaustive, many more invariants can for example be inferred from the Hopf structure described in §7.4. To see this consider two algebraic invariants of hike monoids $a(G)$ and $b(G)$ defined on a digraph $G$ and all its induced subgraphs $g \prec G$. Then the induced subgraph convolution $(a * b)(G) = \sum_{g \prec G} a(g)b(G \setminus g)$ is also an algebraic invariant of hike monoids. In other terms if $G$ and $G'$ are two $\phi$-equivalent digraphs, then $a(G) = a(G')$, $b(G) = b(G')$ and $(a * b)(G) = (a * b)(G')$. As an instance of this we unify and generalise assertions 1) and 2) with $\operatorname{perm}(\mathbf{Id} + A)^{*k}$, the $k$th-induced subgraph convolution of the permanent with itself, which is therefore an invariant of hike monoids for all $k \in \mathbb{Z}$.

If the isomorphism of hike monoids between $\mathcal{H}_G$ and $\mathcal{H}_{G'}$ is length preserving, then all algebraic quantities computable from their adjacency matrices are identical (e.g. degree sequence, graph spectra, permanent polynomial $\operatorname{perm}(\mathbf{Id} - zA)$ etc). Allowing for the addition of transient vertices it is always possible to construct a pair of digraphs related by a length-preserving isomorphism of hike monoids from a pair of digraphs related
by an isomorphism that does not preserve the length. This gives a systematic mean of generating cospectral
pairs, although the digraphs so generated are much more similar than just cospectral (remark also that there
are pairs of cospectral graphs do not share the same hike dependency graph). Below is an example of digraphs
related by such a morphism:

<figure><img src="image_26.png" /></figure>

<figure><img src="image_27.png" /></figure>

The second type of invariant are combinatorial invariants sensitive to how walks and hikes are composed of
cycles:

**Proposition 8.3.2.** Let $G = (V_G, E_G)$ be a digraph, $\mathcal{H}_G$ its hike monoid and $W_G \subset \mathcal{H}_G$ be the set of walks in $\mathcal{H}_G$, that is the set of hikes $h = c_1 \cdots c_k \in \mathcal{H}_G$ with a unique right simple cycle $c_k$. Let $\Omega(h)$ be the number of simple cycles in a hike $h$. Let $f_{\mathcal{H}_G}^{\Omega}(z) := \sum_{h \in \mathcal{H}_G} z^{\Omega(h)}$, $f_{W_G}^{\Omega}(z) := \sum_{h \in W_G} z^{\Omega(h)}$, be the associated ordinary generating functions on hikes and walks, respectively.

Then $G \sim_{\Phi} G'$ implies

$$
1. f_{H_G}^{\Omega}(z) = f_{H_{G'}}^{\Omega}(z);
$$

$$
2. f_{W_G}^{\Omega}(z) = f_{W_{G'}}^{\Omega}(z).
$$

Now consider the set $W_{G:i \to j}$ of rooted walks $w$ from vertex $i$ to vertex $j$ in $G$. Let $\Omega(w)$ designate the number of loops erased from $w$ following Lawler's loop erasing procedure [122]. Let $\sigma(\cdot)$ be an additive function on hikes. Then $G \sim_{\Phi} G'$ implies that for all $i, j \in V_G$ there exists $i', j' \in V_{G'}$ with

$$
3. f_{W_{G:i \to j}}^{\Omega}(z) = f_{W_{G':i \to j'}}^{\Omega}(z);
$$

4. The shape of the branched continued fraction representation of the generating series associated with an additive function $\sigma$ defined on rooted walks from $i$ to $j$ on $G$ is the same as that representing the generating function of $\sigma$ on rooted walks from $i'$ to $j'$ on $G'$.

Invariant 4. exploits both the number-theoretic properties of hike monoids and the bialgebraic structure
obeyed by graph walks implying the path-sum theorem for the ordinary generating function associated with $\sigma$.

**Example 8.3.1.** Consider the following two graphs with identical hike dependency graph:

<figure><img src="image_28.png" /></figure>

<figure><img src="image_29.png" /></figure>

Let $\sigma$ be the length function $\ell$, which is additive as necessary. Then the path-sum continued fraction repre-
sentation of the ordinary generating function of all rooted closed walks from vertex $\bullet$ to itself on $G$ and $G'$
associated with the length function is

$$
\sum_{w \in W_{G: \bullet \to \bullet}} z^{\ell(w)} = \frac{1}{1 - z - z^2 - \frac{z^3}{1 - \frac{z^2}{1-z}}}
$$

$$
\sum_{w \in W_{G': \bullet \to \bullet}} z^{\ell(w)} = \frac{1}{1 - z - z - \frac{z^2}{1 - \frac{z^4}{1-z^2}}}
= (\mathrm{Id}' - z \mathbf{A}_{G'})^{-1}_{\bullet\bullet},
$$

where $A_G$ and $A_{G'}$ are the adjacency matrices of $G$ and $G'$, respectively. The common structure $T$ of both
fractions is readily apparent and stems from the hike dependency graph $H = \phi(G) = \phi(G')$ as explained in the
proof of Proposition 8.3.2:

<figure><img src="image_30.png" /></figure>

<figure><img src="image_31.png" /></figure>
In $G$, $a$ and $e$ are self-loops, $b$ and $d$ are backtracks and $c$ is a triangle. In $G'$, $a$ and $b$ are self-loops, $c$ and $e$ are backtracks and $d$ is a square. Since $\Omega$ is additive the same structure $T$ appears in $f_{W_{G:1\to1}}^{\Omega}(z) = f_{W_{G':1\to1}}^{\Omega}(z)$,

$$f_{W_{G:1\to1}}^{\Omega}(z) = f_{W_{G':1\to1}}^{\Omega}(z) = \frac{1}{1-z-z-\frac{z}{1-\frac{z}{1-z}}}$$

The picture painted by these investigations is that the relation between digraphs and their hikes is in fact rather weak: no graph theoretic property seems to be directly related to the arrangement of simple cycles on a digraph. Among the graph properties we found may be lost whilst leaving the hike monoidal structure of cycles invariant are vertex-transitivity, regularity, planarity, bipartiteness, (bi)directedness, Hamiltonicity, being Eulerian, being chordal, being triangle-free, chromatic number, graph spectra, in- and out-degree distributions and a majority of algebraic quantities computable from adjacency matrices. This list is undoubtedly non-exhaustive. As a corollary, there is a great variety of digraphs with isomorphic hike monoids and characterizing all transformations relating such digraphs remains completely open.

Conversely, deciding which arrangements of simple cycles exist at all is highly non-trivial, even allowing for multidigraphs to realise them as was done here. We have shown that realizability is equivalent to the existence of integer solutions to polynomial systems of equations, making realizability decidable but no less obscure. The characterization and existence questions concern simple undirected graphs too as soon as information about their line graph is removed. That is, simple graphs do not relate to their simple cycles of length $\ell \neq 2$ any better than multidigraphs do to their simple cycles of any length.

All of this demonstrates that walks are in fact much less dependent on the digraphs on which they take place than might have first been thought; and that a “theory of walks” distinct from graph theory needs to be developed. Here we proceeded by relying on hike monoids, which provide a representation for walks and walk-like objects that is markedly detached from graphs sustaining those walks. As monoids, hike monoids are plain trace monoids. Unfortunately, while the latter are well understood, there is no simple way to know which trace monoids are hike monoids. Although we have formulated most of our results in terms of dependency graphs, expressing them directly as statements on trace monoids makes this fact even more clear. Consider for example the following family of trace monoids with identical independence relations but differing number of generators:

$$\mathcal{T}_0 = \{a, b, c, d \mid ac = ca, bd = db\}, \\ \mathcal{T}_n = \{a, b, c, d, x_1, \dots, x_n \mid ac = ca, bd = db\}.$$

Among these very similar trace monoids, we know that $\mathcal{T}_0$, $\mathcal{T}_1$, $\mathcal{T}_3$, $\mathcal{T}_5$, $\mathcal{T}_9$, $\mathcal{T}_{17}$ and $\mathcal{T}_{29}$ are not hike monoids, while all others are. Trace theory does not seem to be any better equipped than graph theory to address the questions raised here.
# Chapter 9

## Further applications of hike monoids

Hike monoids have found applications in network analysis, through the novel formulas for cycle counting and the finite sieve theorem. In this chapter, we briefly summarise these applications.

### 9.1 Cycle counting in social analysis and computer science

The algorithm for counting simple cycles and simple paths presented and analysed in §7.2 based on the formulas of §7.1 is sufficiently performant to enable its concrete use in the analysis of large real-world networks, in particular in sociology, econometry and computer science.

#### Evaluating balance on social networks

In the social sciences, complex systems may conveniently be represented by graphs whose nodes represent social entities (people, tribes, companies etc.) and whose edges represent interactions between these entities (e.g. acquaintance, war, financial exchanges etc.). Relations of amity and enmity between entities are well encoded by signed networks, where an edge is assigned a positive value if two entities are acquainted and in good terms, and a negative one if there are instead enemies [90, 151, 52]. Such networks provide a natural setting to study inter-personal relationships and their correlations.

For example, one could expect that people are friendly towards the friends of their friends, a situation that is said to be “balanced”. More generally, on signed networks, a group of individuals who are cyclically connected—i.e. forming a triangle, a square, a pentagon etc.—are said to be balanced if the number of negative edges in the cycle is even. Otherwise the cycle is said to be unbalanced. Starting with Heider’s work in the 1940s, sociologists have conjectured that such negative cycles are the cause of tension and thus, that social networks should evolve into a state where balanced cycles are largely predominant [95, 33, 5], the so-called “Heider’s conjecture”. The question of whether the conjecture is satisfied by real-social networks and if not, by how much it fails to be true, has been discussed since Heider’s formulation in 1946 [95].

Mathematically speaking, this sociological question translates into the following problem: on a signed network $G$, determine for all $\ell$ the percentage of negatively-signed simple cycles of length $\ell$. This problem remained largely unsolved owing to its natural formulation in terms of simple cycles, making it formally NP-hard to verify (see §7.2) and practically beyond the reach of current algorithms when it comes to large, real, social networks. This changed thanks to the algorithm we introduced in §7.2 whose improved performances were sufficient to tackle the question for cycles of length up to 15. More precisely the algorithm was tasked with evaluating the ratio $R_\ell$ of the number of negatively signed simple cycles of length $\ell$ to the total number of simple cycles of length $\ell$, i.e.

$$R_\ell := \frac{N_\ell^-}{N_\ell^- + N_\ell^+}$$

Here $N_\ell^-$ (resp. $N_\ell^+$) is the number of unbalanced (resp. balanced) simple cycles of length $\ell$. In particular, $R_\ell = 0$ when the network is perfectly balanced for a length $\ell$, while $R_\ell = 1$ indicates a totally unbalanced situation. In order to ascertain the significance of the results, $R_\ell$ is compared with that obtained on a graph with the same proportion $p$ of negative directed edges than the real network under study, but where the sign of any directed edge is negative with probability $p$. In particular, in the null-hypothesis model, the signs of any two directed edges are *independent* random variables. Then the probability that a simple cycle $c$ of length $\ell$ be negative (i.e. unbalanced) is

$$\text{Prob}(c \text{ negative}) = \sum_{i=0}^{[\ell/2]-1} \binom{\ell}{i} p^{2i+1} (1-p)^{\ell-2i-1}. \qquad (9.1.1)$$
<figure><img src="image_32.png" /><figcaption>Figure 9.1: Computed percentage of negatively signed simple cycles on the Epinions network for cycle length up to 15 (red line and error bars). The blue shaded region bordered by dashed blue lines shows the values of $R_\ell$ compatible with the null-hypothesis, as determined by Eq. (9.1.1) with the $2\sigma$ interval.</figcaption></figure>

Supposing for simplicity that the signs of any two simple cycles are independent random variables then the probability distribution for $N_\ell^-/(N_\ell^- + N_\ell^+)$ in the null-hypothesis is a binomial law with expectation value $R_\ell^{\text{null}}$ given by Eq. (9.1.1). Consequently, in this simple model the null-hypothesis is compatible up to a near 95% confidence level with any value of $R_\ell$ within the $2\sigma$ interval $R_\ell^{\text{null}} \pm 2\sqrt{R_\ell^{\text{null}}(1-R_\ell^{\text{null}})}/\sqrt{N_\ell^- + N_\ell^+}$. The assumption that the signs of any two simple cycles are independent random variables is not true on real social networks. Calculating the null-hypothesis without this assumption is very difficult in practice however. Indeed, a more accurate null model is given by evaluating the average balance ratios of all lengths over all random shufflings of the edges-signs from the social network under study. We also implemented this more accurate model and found only minor modifications that did not affect the overall conclusions of our study.

Concretely, we studied one small (Gahuku-Gama tribe network) and three large real-world networks (Wiki-elections, Slashdot and Epinions). The observations we made are broadly similar on the three large networks and so, for brevity, we here report the results only in the case of Epinions. This is a directed graph with 131,828 vertices and 841,372 edges [48], representing positive/negative relations between the users of the now-defunct consumer review website Epinions.com. We find the balance ratio $R_\ell$ to transition from small to high values at around $\ell \sim 10$. Strikingly, for $4 \le \ell \le 9$, $R_\ell$ is almost constant around 15% witnessing a very strong, almost length-independent, inter-edge correlation. This example and the other analysed in our study show that social networks are indeed strongly balanced. More precisely, the percentage of negatively signed simple cycles is greatly depressed as compared to an independent sampling scenario (the null hypothesis), typically up to lengths of circa $\ell \sim 10$. As explained in [73], this is a signature of strong inter-edges correlations with correlation length $\xi \approx 10/2 = 5$ since most edges are bidirected. The correlation depth, which quantifies the degree up to which individuals are correlated with their neighbours, is thus close to 5. A rebound of the balance ratio to over 50%, above and beyond the null-hypothesis, following the transition is also clearly detectable in the data, indicating that much of the imbalance is shifted to long simple cycles. Sociologically this seems to indicate that conflict is strongly suppressed in close communities of up to 5 people and rather shifted to larger communities of over $\sim 12$ people, where its dilution seems to allow for its management. In terms of modeling, our results suggest that the simplest model for the balance ratio $R_\ell$ on large (sparse) social networks is a step function, with the step located circa $\xi \sim 5$, that is $\ell \sim 10$. Consequently, Heider's conjecture is verified only for short simple cycles and fails for longer ones.

## The all-paths and cycles graph kernel

With the recent rise in the amount of structured data available, there has been considerable interest in methods for machine learning with graphs. Many of these approaches have been kernel methods, which focus on measuring the similarity between graphs. Kernel methods are very popular methods for pattern recognition in machine vision and machine learning because they allow the use of a wide variety of classification and clustering tools through the definition of a suitable kernel function for the type of data at hand. A kernel function is a function $K(A, B)$ between two objects, A and B, which in effect measures their similarity. Most graph kernels are of the convolution type [94], which decompose the structural object into parts and measure the similarity between those parts. Particular examples include the intersection kernel, the optimal-assignment kernel [112] and the cross-product kernel. In the cross-product kernel, the objects are decomposed into sets of parts $X_A$ and $X_B$
which are then compared individually

$$K(A, B) = \sum_{x_i \in X_A} \sum_{x_j \in X_B} K_B(x_i, x_j)$$

where $K_B(.,.)$ is a base kernel measuring the similarity of parts. Many types of parts have been proposed for such a decomposition, including walks, cycles and paths. In [26], Borgwardt and Kriegel proposed the “all-paths kernel”, decomposing the graphs into the set of all paths between any pair of vertices. They noted that this was an NP-hard decomposition, and very difficult to compute in practice. Instead, they computed the shortest-path kernel, an approximation which considers a single path between each pair with the shortest geodesic length.

Relying on the novel algorithm of §7.2 in [78] we managed to compute an “all-paths and cycles kernel”, an extension of the all-paths kernel, further enriched by including the simple cycles as well. Extensive evaluations on a variety of graph datasets demonstrate that the all-paths and cycles kernel has superior performance to the shortest-path kernel and state-of-the-art performance overall.

## 9.2 Sieves on hikes as a cycle centrality measure

### Theory & motivations

Networks, that is collections of nodes together with sets of edges linking some of these nodes, naturally encode relations (the edges) between entities (the nodes). The trajectories on the network, i.e. the walks, represent the dynamical processes of the system of entities. Networks and walks play a ubiquitous role across many domains, from economy to defence through biology and physics, where graphical models are essential tools to master the interactions and dynamics of complex systems.

Network analysis has slowly progressed from questions concerning individual entities to questions regarding the dynamics of the system, from the local to the global scale. Already over the course of the development of vertex-centralities, i.e. measures of the importance of individual nodes, it became clear that vertex-neighborhoods, subgraphs and motifs were of paramount importance to understand the evolution of real networks [146, 205]. For example, in a biological context Estrada and Rodríguez-Velázquez showed that protein-lethality in *Saccharomyces cerevisiae* was better accounted for by an analysis of the subgraphs to which a protein belongs in the protein-protein interaction network (PPI) rather than by its degree [51]. In another study, Mukthar *et al.* showed that while a number of the proteins of the plant *Arabidopsis thaliana* under attack by pathogens were high degree nodes (hubs) in the plant PPI, dozens of these proteins were “targeted significantly more often [...] than expected given their respective degrees”. They concluded that protein-targeting by pathogens “cannot be explained merely by the high connectivity of those target [proteins]” [150]. In addition, it is also well known that in PPIs, certain small subgraphs of protein interactions, called motifs, are over-represented as compared to what one might expect from random networks [152]. These motifs are believed to perform crucial roles in emergent biological functions [202], such as the formation of protein complexes, functions which are not readily apparent at the level of single proteins [93, 152].

In spite of all of these observations, much attention is still devoted to individual nodes when exploring the dynamics and properties of complex networks. This is possibly because the versatility, ease of implementation and easy to grasp definition of many vertex centralities is lacking an equivalent at the cycle or subgraph level. It is a central goal of the mathematical tools we presented in [80] to remediate to this situation.

We propose a centrality measure for individual cycles based on the premise that a cycle is central if it intersects an important proportion of all the information flows on the network. In concrete applications, these flows represent actual dynamical processes, that is sequences of interactions between discrete entities, such as wealth exchanges between economic actors or successions of protein reactions in a living organism. This premise provides a clear meaning for the centrality as well as a contextual framework within which to appraise its results. To translate these ideas into mathematical tools, we propose to count all walks $\omega$ which have the same *last erased loop* per Lawler's procedure. This unambiguously attributes every walk to a single cycle since the last erased loop is unique. In addition, by the results of §5.3 this loop presents the only vertices from which the walk can be started without changing its equivalence class in the Cartier-Foata monoid. This entails that all walks which are structurally similar are attributed to the same cycle. Finally, instead of naively counting infinitely many walks, we shall calculate the fraction of walks with a cycle $\gamma$ as last erased loop among all the closed walks on the graph. This fraction is a well-defined quantity given exactly by the finite sieve theorem of §6.2:

**Definition 9.2.1 (Cycle centrality).** Let $G$ be a possibly weighted (di)graph, and let $\lambda$ be its maximum eigenvalue. Let $A$ be the adjacency matrix of $G$, including weights if any. For any cycle $\gamma$ of length $\ell(\gamma)$, let $A_{G\setminus\gamma}$ be the adjacency matrix of the graph $G$ where all vertices visited by $\gamma$ and the edges adjacent to them have been removed. We define the centrality $c(\gamma)$ of the cycle $\gamma$ as

$$c(\gamma) := \lambda^{-\ell(\gamma)} \det \left( \mathrm{Id} - \frac{1}{\lambda} A_{G\setminus\gamma} \right).$$
As outlined in the introduction to this section, the centrality $c(\gamma)$ has a precise combinatorial meaning underpinning its role as a measure of cycle importance. Rigorously we have:

**Proposition 9.2.1.** Let $G$ be a (di)graph with adjacency matrix $A$ and let $\gamma$ be a cycle on $G$. Then the total number $n_{\gamma}(k)$ of cycles of length $k$ on $G$ intersecting the cycle $\gamma$ is asymptotically given by $n_{\gamma}(k) \sim c(\gamma)(\det(\mathrm{Id} - zA)^{-1})[z^k]$ as $k \to \infty$.

**Proposition 9.2.2.** Let $G$ be a (weighted di)graph with non-negative edge weights and let $\Gamma(G)$ be the set of all simple cycles on $G$. Then for $\gamma \in \Gamma(G)$, $0 < c(\gamma) \le 1$. Furthermore $0 < \sum_{\gamma \in \Gamma(G)} c(\gamma) = \alpha \le 1$ is the (weighted) fraction of all hikes on $G$ which are walks.

The fact that $\sum_{\gamma \in \Gamma(G)} \alpha^{-1}c(\gamma) = 1$ confirms that there is a probabilistic interpretation for the centralities $c(\gamma)$. Remarkably this interpretation continues to hold on infinite vertex-transitive graphs, provided $\alpha^{-1}c(\gamma)$ is understood as $F(\gamma)/\lambda^{\ell}(\gamma)$ in the sense of Chapter 6.

**Proposition 9.2.3.** Let $G$ be a finite graph or an infinite vertex-transitive graph, $\lambda$ the largest eigenvalue of $G$ and let $\gamma$ be a simple cycle on it. Let $w$ be a random walk with uniform edge-transition probability $1/\lambda$. Run the walk until it comes back to its starting point. Then the probability $\mathbb{P}(w \mapsto \gamma)$ that the last erased loop of $w$ be $\gamma$ is equal to the fraction of all closed walks (including those passing an arbitrary number of times through the origin) which are right-multiples of $\gamma$ in the hike monoid $\mathcal{H}_G$, $\mathbb{P}(w \mapsto \gamma) = c(\gamma)$.

The logarithm of $c(\gamma)$ also has a probabilistic interpretation based on results by Espinasse and Rochet [49]:

**Proposition 9.2.4.** Let $G$ be a finite graph or an infinite vertex-transitive graph and let $\gamma$ be a simple cycle on it. Let $\mathbb{E}_w(\cdot)$ designate the expectation value of a random variable with respect to the closed random walks (defined up to translation if $G$ is infinite) and weighted with probability $\lambda^{-\ell(w)}$. Then

$$ \log(c(\gamma)) = \sum_{w: \text{walk}} \frac{\Lambda_{\gamma}(w)}{\ell_{\gamma}(w)} \lambda^{-\ell(w)} = \mathbb{E}_w \left( \frac{\Lambda_{\gamma}(w)}{\ell_{\gamma}(w)} \right). $$

Here $\Lambda_{\gamma}(w)$ counts the vertices that are both in $\gamma$ and the unique right divisor of $w$ and $\ell_{\gamma}(w)$ is the number of vertices of $\gamma$ visited by $w$, counted with multiplicity.

Function $\Lambda_{\gamma}(w)$ is a kind of $\gamma$-overlap von Mangoldt function: defining $\Lambda_{\gamma}(h)$ to be 0 when the hike $h$ is not a walk and otherwise $\Lambda_{\gamma}(h)$ is as in the Proposition above, we have $\Lambda_{\gamma}(h) = \Lambda(h)$ when $\gamma$ is the unique right prime divisor of $h$. The combination of two preceding Propositions implies the rather uncommon result that the entropy of the distribution of $c(\gamma)$ values is a double expectation value: it is the expectation value over the SAPs of an expectation value over walks. This entropy has not yet been properly studied.

**Remark.** If $\gamma$ is taken to be the empty walk on some vertex $i$, then $c(i)$ is the asymptotic proportion of closed walks passing through $i$ on $G$ and a measure of the importance of this vertex. This centrality is essentially the same as the eigenvector centrality. Indeed take $G$ a (weighted) graph with adjacency matrix $A$ and largest eigenvalue $\lambda$. Let $\mathrm{eig}(i)$ be the $i$th entry of the eigenvector corresponding to eigenvalue $\lambda$. Then there exists a constant $\eta$ such that for all vertices, $c(i) = \eta \mathrm{eig}(i)^2$. In fact $\eta = \lim_{z \to 1/\lambda} (1 - \lambda z)^{-1} \det(\mathrm{Id} - zA)$.

## Predicting protein targeting in plants

We first consider the protein-protein interaction network (PPI) obtained by Mukhtar et al. in a landmark study of plant-pathogens interactions between the plant *Arabidopsis thaliana*, the bacterium *Pseudomonas syringae* and the oomycete *Hyaloperonospora arabidopsidis*. The network, comprises 3,148 interactions between 926 proteins, of which 170 are known to participate in plant immunity and 137 are targeted by effectors from one or both pathogens [150].

The state-of-the-art model posits a positive correlation between protein-targeting and the degree-centrality of the proteins. Mukhtar et al. confirmed such a correlation, showing it to be statistically significant, yet also observed shortfalls of the model, such as numerous low-degree targets and hubs targeted by few pathogen-effectors, if at all. Nonetheless, the degree-based model is the best available vertex-based model, see Table (9.1). Mukhtar et al. also showed that highly connected proteins tend to be involved in immune interactions [150]. Furthermore, subsequent biological studies, notably into oomycetes, have shown that pathogen effectors are potent stimulants of immune activity in *Arabidopsis thaliana*. Consequently, we might expect the PPI to comprise small protein motifs involving not only a pathogen target, but also one or more interactions with an immune protein, interactions which may be stimulated by the activity of the pathogen on the target, and an accompanying central protein. If we now hypothesise that pathogens primarily aim at disrupting a sizeable proportion of sequences of protein reactions in the host, then the motifs mentioned above should have high cycle-centrality. This is because in the context of PPIs the cycle-centrality of a motif measures the fraction of
<figure><img src="image_33.png" /><figcaption>Figure 9.2: Solid black line: ROC curve of the dominant-triad model in the plant-pathogen PPI of *A. thaliana*, *P. syringae* and *H. arabidopsidis*. In this model, all triads involving AT5G08080 and/or AT5G22290 are ranked in descending order according to cycle-centrality. A true positive is a triad involving at least one more target and at least one immune reaction, while a false positive is a triad which does not meet both of these criteria. Red dashed line: ROC curve of the degree-based model proposed in [150], where proteins are ranked in descending order according to their degree in the PPI. A true positive is a protein targeted by at least one pathogen effector. Dotted line: null-hypothesis model with random protein-targeting.</figcaption></figure>

sequences of protein interactions intercepted by the motif. In other words, pathogen-targets should primarily be found in triads with dominant cycle-centrality involving at least one target, one or more central proteins, and one or more immune interactions.

To test this model, we calculated the cycle-centrality of all 113,398 triads of proteins in the PPI. We then selected those triads involving a protein involved in plant resistance against bacteria or one with a role in stress responses. Among the selected triads, we classified as true positive those which involve at least one target and at least one protein related to immunity. Finally, in order to compare the performances of the dominant-triad and degree-based models, we obtained the ROC curves for both. The results, presented on Fig. (9.2), clearly show the dominant-triad model out-performing the degree-based one of [150]. The performances of models based on summing vertex-centralities in cycles are reported in Table (9.1) for comparison. These results suggest that the hypothesis where pathogens select their targets to maximise the fraction of disrupted sequences of protein reactions better fits the observations than the hypothesis where they target high-degree nodes of the PPI. In particular, the model explains why hubs are not the only targets nor necessarily the most targeted proteins, as interactions with peripheral proteins in the immediate vicinity of a central protein are seemingly equally disruptive to the ensemble of sequences of reactions on the PPI. The performance of the dominant-triad model also underscores the remarkable efficiency of the plant immune response: nearly all triads with the highest cycle-centrality involving a pathogen target also involve an immune interaction. Taken together, these observations paint the picture of a PPI where two central proteins are immediately surrounded by numerous pathogen targets and a flurry of immune interactions.
<table><caption>Table 9.1: The ROC AUC is the area under the ROC curve. A perfect model making only correct predictions would have ROC AUC=1, while the null-hypothesis yields ROC AUC=0.5. The discrimination is the (absolute) area between the ROC curve and the null-hypothesis line. The crucial difference between vertex-based and cycle-based models is that the former attempt at directly identifying individual protein-targets, while the latter aim at identifying targeted triads.</caption><caption>Performances of protein-targeting models</caption><thead><tr><th>Model</th><th>ROC AUC</th><th>Discrimination</th></tr></thead><tbody><tr><td>1. Dominant-triad c(γ)</td><td><strong>0.97</strong></td><td><strong>0.47</strong></td></tr><tr><td>2. Σ<sub>R</sub> (α = 0.85/λ)</td><td>0.89</td><td>0.39</td></tr><tr><td>3. Σ<sub>CS</sub></td><td>0.88</td><td>0.38</td></tr><tr><td>4. Σ<sub>eig</sub></td><td>0.87</td><td>0.37</td></tr><tr><td>5. Σ<sub>R</sub> (α = 0.5/λ)</td><td>0.85</td><td>0.35</td></tr><tr><td>6. Degree centrality [150]</td><td>0.73</td><td>0.23</td></tr><tr><td>7. Resolvent centrality (α = 0.5/λ)</td><td>0.28</td><td>0.22</td></tr><tr><td>8. Resolvent centrality (α = 0.85/λ)</td><td>0.28</td><td>0.22</td></tr><tr><td>9. Exponential centrality</td><td>0.60</td><td>0.10</td></tr><tr><td>10. Eigenvector centrality</td><td>0.41</td><td>0.09</td></tr></tbody></table>

## Finding biological protein complexes

The PPI network of the yeast *Saccharomyces cerevisiae* has been mapped by [92], which provides a network comprising 5303 interactions between 1689 individual proteins. These proteins are known to belong to complexes, a curated list of which is provided by the Munich Information center on Protein Sequences (MIPS) [87]. This complexes are not readily apparent from the PPI alone, which comprises no information on complexes. Yet using the cycle centrality $c(γ)$ we can detect them directly from the topology of the PPI. To do so we analysed the PPI in three steps. Firstly, we found all edges (that is connected pairs of vertices) connected triplets (triangles and paths on 3 vertices) and connected quadruplets of proteins on the network. Secondly, we calculated the centralities $c(.)$ of these objects. To present the third step of our analysis, we invite the reader to observe the distribution of centrality values, which we show at the top of Fig. (9.3) in the case of triplets. Triplet centralities fall into separate plateau-like ensembles. Therefore, the third and final step of our analysis is to gather the list of all proteins appearing in all the triplets whose centrality values placed them in the same plateau. We then compare these lists of proteins with the biological complexes found in curated databases [168]. Remarkably, these lists of proteins correspond to actual biological complexes. Mathematically, the fact that biological complexes lead to clustered plateau-like centrality values for triplets means that the frequency with which proteins belonging to these complexes are involved in successions of proteins reactions depends first and foremost on the complexes themselves. In other terms, the frequency of protein activation is determined at the complex level. For a full discussion of the biological activity of the identified complexes, see [79].

<figure><img src="image_34.png" /><figcaption>Figure 9.3: Distributions of triplet centralities on the PPI of the yeast.</figcaption></figure>
# Chapter 10

## And from there...

The two branches of ‘walk theory’ presented in this report offer different perspectives of further development:

In the first branch, the operadic context of the CAP-co-preLie bialgebra ought to be explored to better connect it to Feynman categories in particular. This might help in extending some of the tools presented here, in particular the path-sum theorem, to renormalization procedures and seek a continuum version of it, with walks made of continuous steps. This is necessary to tackle resummation of non-Abelian Feynman diagrams for physical systems with continuous degress of freedom for example. That this is possible might already be indicated by an alternative interpretation of the ⋆-algebras, seeing ⋆-products as simply summing up continuous walks on a graph that is both spatially discrete and continuous along the time-dimension. Mathematically, this description is equivalent to that presented here, where the discrete graph and the time-dependence of its edge weights are treated separately. Re-summations of continuous walks may be arduous however as it generally leads to incurable divergences. In the case of time mentioned above, such divergences are concretely avoided by the impossibility of backward time-travel, leading to unconditional convergence of ⋆-Neumann series.<fnref n="1" />

The main area of current development–to the point of taking much of my research time at the expense of all other venues of research–is that of tackling fractional and non-linear ODEs as well as PDEs within extended ⋆-algebras. The underlying ideas, given in more details below, are strongly unifying, lending the path-sum theorem a quasi-universal applicability. This *will work*, e.g. the solution of fractional and non-linear systems of ODEs have already been given a path-sum formulation although the general theory is still under construction.

For the second branch, at the moment a bit starved of research-time, I view sieves on hikes as uniquely powerful tools to tackle counting problems. The asymptotic behaviour of the fraction $F(p)$ and the control of errors are the two main areas of development as explained in details below. Another interesting problem raised in Chapter 8 is that of characterizing hike monoids, i.e. those arrangements of cycles that exist on graphs. The fact that this problem is profoundly non-trivial is a signature of its importance. Every single aspect of the question turned out to be unexpectedly difficult. For every intuition we found an abundance of seemingly unrelated and always surprising counter-examples. This is the only problem of my career that led to a publication with essentially no positive results and at this point I sincerely have no idea how to even conceive what a possible solution would look like. That is, it feels like we do not have the right mathematical framework for it. As I discussed with collaborators, I have the vague intuition that the characterization of hike monoids is related to the cycle double cover conjecture, but my intuitions on the matter have been systematically wrong so far!

### 10.1 Exotic umbral calculi for path-sum solutions to non-linear ODEs and PDEs

The solution of non-autonomous systems of linear ODEs as path-sums in ⋆-algebras necessarily invites the question of whether a similar approach might work for other types of equations?

Consider firstly the non-linear ODEs. An insurmountable issue seems to obstruct any hope for these: the path-sum theorem is inherently limited to linear problems. Indeed, take for example the graph $G$ with a single vertex and one self-loop $c$ on it. Then the series of all closed walks on $G$ is $\Sigma_G := 1 + c + c^2 + \dots \equiv 1/(1-c)$. Now if we add a weight function $w(\cdot)$ to the loop $c$ and since the weight of a walk is the product of the weights of the edges it traverses, $\forall n \in \mathbb{N}$, $w(c^n) = w(c)^n$ leading formally to $w(\Sigma_G) = 1/(1-w(c))$. In particular $w(\Sigma_G)$ solves a linear equation, namely

$$w(c)w(\Sigma_G) = w(\Sigma_G) - 1.$$

<footnote n="1">¹Interpreting ⋆-products as walks along the tim-dimension is the way non-autonomous ODEs were solved in [67]. In this context the fact that $\Theta(t' - t) = 0$ when $t' < t$ is a signature of causality.</footnote>
Now let us impose different weights to turn this into a non-linear equation, e.g. weights that depends on the length of a walk $\omega$ as $W(\omega) := f(\ell(\omega))w(\omega)$ with $f: \mathbb{N} \to \mathbb{C}$. One verifies easily that if the path-sum theorem hold for these weights then one should still have $W(\Sigma_G) = 1/(1 - W(\Sigma_G))$, which imposes that $f(n) = \prod_i f(n_i)$ for any weak composition $\{n_i\}$ of $n$, i.e. $\sum_i n_i = n$. In other terms, the path-sum resummation which exploits the bialgebraic structure on walks necessitates purely geometric weights and these are found only in solutions to linear problems.

To use the path-sum theorem one must therefore map a non-linear problem of interest to a linear one *exactly*, or else forfeit any hope of interesting applications. For weights depending on the length and the ordinary product, this means seeking operators $O$ mapping the weights $f(\ell)$ to geometric ones $f(\ell) = O[\prod_i f(n_i)]$, $\sum_i n_i = n$. Oddly, this ad-hoc strategy works in all cases where it was given a chance, enabling e.g. weights $f(n) = 1/n!$, $f(n) = 1/n$ or $f_q(n) = \binom{q}{n}$ to be used in conjunction with path-sums [77]. We mention the true underlying cause of success of this approach below, but first we turn to a related question about ODEs.

In the context of differential equations, and since the time-ordered exponential is a $\star$-resolvent, seeking a linear formulation for a non-linear problem is equivalent to seeking a solution of such a problem in terms of time-ordered exponentials. This idea was first explored by A. A. Agrachev and R. V. Gamkrelidze [1, 2] and later by Y. Kosovtsov in a series of powerful but completely overlooked contributions [107, 108, 109]. The key take-away message is that it is indeed formally possible to do so. Take for example the non-linear ODE,

$$ \dot{u} = u^2, \quad u(0) = u_0 $$

Kosovtsov made the following observational trick: introduce $S(\omega, t) = e^{\omega u(t)}$ so that $\partial_{\omega}S(\omega, t)|_{\omega=0}$ recovers $u$. Then observe that $\partial_t S(\omega, t) = \omega \dot{u}(t)S(\omega, t)$ while for all $n \in \mathbb{N}$ we get $\partial_{\omega}^n S(\omega, t) = u(t)^n S(\omega, t)$. Then the original equation reads, for $S$,

$$ \partial_t S(\omega, t) = \omega \partial_{\omega}^2 S(\omega, t) $$

This is now a linear ODE in $S(\omega, t)$ that we solve as we did so far: introduce the (time-wise) Green's function $G_S := \delta' \star S\Theta$. This yields $G_S = \omega \partial_{\omega}\Theta \star G_S$ where $\delta'$, $\Theta$ and the $\star$-products are all with respect to time. It follows that

$$ G_S = (1_{\star} - \omega \partial_{\omega}^2 \Theta)^{-1}, $$

is a $\star$-resolvent. Remark crucially that this resolvent involves an operator $\partial_{\omega}^2$. This is perfectly fine because this operator is $\partial_{\omega}^2 \equiv \delta''$ an element of $\mathcal{D}$ just as those elements of $\text{Sm}_{\Theta}$ encountered so far in ordinary linear ODEs. The $\star$-resolvent formal solution guarantees the applicability of the path-sum theorem to systems of non-linear ODEs and their amenability to $\star$-linear algebra methods, including a Lanczos procedure for tridiagonalization. Since $\text{Inv}(\mathcal{D})$ is a Fréchet Lie-group to which $\delta'$ belongs, non-integers $\star$-powers of $\delta'$ are meaningfully accessible as functions of $\delta'$. This observation justifies the calculus of fractional derivatives with the $\star$-algebra framework and allows it to tackle fractional differential equations, yielding $\star$-resolvent formal solutions for them as well.<fnref n="2" />

In the context of recurrence equations, exact linearization is an indirect consequence of umbral methods. Classical umbral calculus concerns itself with the combinatorial study of polynomial sequences. The central tool is the umbral algebra formed by power series seen as both automorphisms and as linear functionals of the vector space $\mathcal{P}$ of polynomials [171]. An umbral operator $U_f$ associated with a series $f(t)$ is an automorphism of $\mathcal{P}$ that allows for global treatments of all polynomials of a sequence related to $f$ at once. Products of umbral operators correspond to the composition of the associated series $U_f.U_g = U_{f \circ g}$. This effectively allows one to perform exact linearization because if one disposes of a formal derivation operator $D$, then it must hold that for any function $\Phi$ and umbral operator $U_f$,

$$ \Phi(D).U_f = U_f.\Phi(f(D)), $$

In other terms, multiplying $\Phi(f(D))$-which may be non-linear in $f$-by the umbral operator associated with $f$ turns it into $\Phi(D).U_f$, which is purely linear in $f$. This gives the proper explanation for Kosovtsov's trick and for the "operator-mapping weights to geometric ones" strategy. More precisely, umbral calculi on 'exotic' vector spaces explain both observations: $S(\omega, t)$ is one of the representations of the umbral operator associated with $u$ in an umbral calculus where $\mathcal{P}$ is replaced by $\mathcal{C}^{\infty}[I]$; and so are the operators $O$ in an umbral calculus on the vector space $\mathcal{F}$ of functions $\mathbb{N} \to \mathbb{C}$. We may now understand the $\star$-product as implementing the umbral composition on $\mathcal{C}^{\infty}[I]$ via multiplication of operators on $\overline{\mathcal{C}}^{\infty}(I^2)$. The Fréchet Lie-group $\text{Inv}(\mathcal{D})$ plays for this umbral calculus the same role as the Riordan group [184, 38] does for the classical umbral construction on $\mathcal{P}$. This line of research points to an 'universality' theorem for graph walks and path-sums, something along the lines of the following conjecture (to which assumptions may yet be missing or need altering):

<footnote n="2">²Applicability of the path-sum theorem to such equations is known since my thesis. These unpublished results rely on an explicit representation of the derivative operator on a basis. A basis independent modern outlook using the $\star$-product is under development by S. Pozza and F. Durastante</footnote>
**Conjecture 10.1.1.** Let $V$ be a (possibly infinite dimensional) vector space. Let $S := \{s_1, \dots, s_n\} \in \mathrm{Seq}(V)^{\otimes n}$ be a set of $n \in \mathbb{N}$ (discrete or continuously indexed) sequences of elements of $V$. Let $\mathcal{E}(S) = 0$ be a possibly non-linear, non autonomous system of, ordinary, partial or fractional equations to be solved in $S$ and let $A \in V^{n \times n}$ represent the sparsity structure of that system. Then there exists $a, b \in V^{n \times n}$ and a product $\bullet$ such that the solution is $S = a \bullet R_A \bullet b$ where $R_A$ is the $\bullet$-resolvent of $A$.

Sequences of objects over vector spaces naturally come with a product $\bullet$ (umbral composition) because these sequences are in bijection with endomorphisms of $V$ (the umbral operators associated to the sequences), which form a natural algebra under composition. Combined with the path-sum expression for $R_A$ in terms of the internal structure of $A$ (seen as some sort of adjacency matrix, $A$ gives rise to a graph $G$ on which the path-sum makes sense), this provides an almost universal mean of tackling structured problems by providing formal solutions to such problems.

## 10.2 Sieves on hikes

Both the finite and the infinite sieve theorems have not been exploited to their full potential yet. In the finite case, the cycle centrality §9.2 deserves a closer look, in particular the associated entropy which has the curious property of also being an expectation value over SAPs of an expectation value over walks. But the main area of development should be the SAP-counting problem itself as detailed in §6.3:

### Asymptotic behaviour of one-sided sieves

A one-sided sieve on hikes suffers from an accumulation of errors hindering its direct use for SAP-counting. This is in line with the blight affecting the Eratosthenes-Legendre sieve from number theory. While the origin of these errors is sufficiently well understood, it is the main term itself that lacks understanding. For example it is still necessary to rely on R. Kenyon's results [104] to obtain the $1 - L^{-3/5}$ asymptotics for the series $S(L)$ (see Fig. 6.2). That should not be: clearly a truly developed command of the sieve would produce this asymptotic by itself, a necessary step for further progress. The fundamental issue is that in spite of now having exactly access to the fraction $F(\gamma)$ for any SAP $\gamma$, there lacks estimations for sums of fractions $F(\gamma)$ over infinite families of SAPs. This may only be accessed via a better control of the asymptotic behaviour of determinants of infinite graphs with finite holes, something that may now be tackled with the tools of [54, 81]. For example, we obtain:

**Proposition 10.2.1** (Unpublished). Let $\gamma_{4L}$ with the square SAP on the infinite square lattice with side length $L$. Then the fraction of closed walks whose last erased loop is $\gamma_{4L}$ behaves asymptotically, when $L \to +\infty$, as

$$ \frac{(4\sqrt{2} - 4)^{4L}}{4^{4L}}. $$

As a corollary, the connective constant of the square lattice obeys $\mu > \sqrt{2} + 1$.

While not revolutionary the above bound stems from purely theoretical arguments with no explicit counting of anything involved and exemplifies the connection with the SAP counting problem. Refinements of the above bound can be made on studying other families of SAPs such as rectangles, but as explained in §6.3, to determine $\mu$ exactly likely necessitates two-sided sieves.

### Two-sided sieves

For such sieves one aims at controlling both the right and left divisors of hikes. Let $M_1, M_2$ be sets of hikes such that one desires counting only those hikes whose left divisors are in $M_2$ and whose right divisors are in $M_1$. Then, translating Bousquet-Mélou and Viennot's results on heaps of pieces to the language of hikes, one obtains for finite graphs the following extension of Viennot's lemma:

$$ \sum_{h = p_2 h' p_1} z^{\ell(h)} = \sum_{h' \in \mathcal{P}_{G \setminus \{M_1, M_2\}}^{\mathrm{s.a.}}} z^{\ell(h')} \frac{\det(1 - z A_{G \setminus \{h', M_1\}}) \det(1 - z A_{G \setminus \{h', M_2\}})}{\det(1 - z A_{G \setminus h'})}. $$

Here $\mathcal{P}_{G \setminus \{M_1, M_2\}}^{\mathrm{s.a.}}$ is the set of self-avoiding hikes on the subgraph of $G$ obtained on deleting all vertices visited by at least one element $M_1 \cup M_2$ and all edges adjacent to them. Similarly, $G \setminus \{h', M_1\}$ Exploiting this result concretely is difficult because of the sum over the set $\mathcal{P}_{G \setminus \{M_1, M_2\}}^{\mathrm{s.a.}}$, on which little is known in general. Choosing $M_1$ and $M_2$ to control this set precisely is possible but necessitates a good control of the asymptotic behaviours of the above determinants as $G$ becomes infinite. This is now feasible thanks to [54, 81]. For example we obtain:
**Theorem 10.2.1** (Unpublished). Let G be the infinite regular lattice with degree $\lambda$ and fix a vertex on it. Let $W_{SAP_r}(2\ell)$ be the number of of closed walks on G of length $2\ell \gg 1$ and which begin by a self-avoiding section that moves at least a distance of $r$ from the starting point. Then

$$W_{SAP_r}(2\ell) \sim \frac{\lambda^{2\ell}}{\pi\ell} \alpha^{2r^2}, \quad \text{as } \ell \to +\infty$$

Here $\alpha$ is the constant relating hike and walk densities defined in Lemma 6.2.1.

Remarkably, on the square lattice this implies that $W_{SAP_r}(2\ell)$ grows exponentially with $\ell$ only if $r = \sqrt{2q\ell}$ with $q < \frac{\pi \log(2)}{\pi \log(4) - 4C} \simeq \pi$ and C being Catalan's constant. Given that all SAP of length $2\ell$ begin with a self-avoiding section of length $2\ell$, and given that the number of such SAPs is known to grow exponentially with $\ell$, we deduce that the fraction of those SAPs that are fully contained in the ball of radius $\sqrt{2q\ell}$ centered on the origin goes to 1 as $\ell$ goes to infinity. This is non-trivial since it relates to the dimension of the SAPs curves on the square lattice. Two-sided sieves necessitate much more studies to be fully understood, in particular naive approaches to the associated error terms yield permanents of infinite graphs with finite holes, quantities which are wholly unexplored.
List of Symbols

<table>
  <tbody>
    <tr>
      <td>(α)<sub>G</sub></td>
      <td>Vertex α dressed by all closed walks rooted in α on G</td>
      <td>p. 17</td>
    </tr>
    <tr>
      <td>C<sup>∞</sup>(I<sup>2</sup>)</td>
      <td>Set of functions that are smooth on an open neighborhood of compact I<sup>2</sup></td>
      <td>p. 20</td>
    </tr>
    <tr>
      <td>A<sub>G</sub></td>
      <td>Adjacency matrix of graph G</td>
      <td>p. 18</td>
    </tr>
    <tr>
      <td>c(γ)</td>
      <td>Cycle centrality of simple cycle γ</td>
      <td>p. 82</td>
    </tr>
    <tr>
      <td>D</td>
      <td>Set of distributions</td>
      <td>p. 20</td>
    </tr>
    <tr>
      <td>δ</td>
      <td>Dirac delta distribution</td>
      <td>p. 20</td>
    </tr>
    <tr>
      <td>Δ<sub>CP</sub></td>
      <td>Co-preLie coproduct on walks</td>
      <td>p. 14</td>
    </tr>
    <tr>
      <td>E</td>
      <td>Edge set of a graph</td>
      <td>p. 44</td>
    </tr>
    <tr>
      <td>f̃</td>
      <td>A function that is smooth on a compact I of interest</td>
      <td>p. 20</td>
    </tr>
    <tr>
      <td>F</td>
      <td>Reduced incidence algebra of a hike poset</td>
      <td>p. 47</td>
    </tr>
    <tr>
      <td>F<sub>p</sub>λ<sup>-ℓ(p)</sup></td>
      <td>Fraction of all closed-walk multiples of a SAP p</td>
      <td>p. 52</td>
    </tr>
    <tr>
      <td>φ(.)</td>
      <td>Map sending a graph to its hike dependency graph</td>
      <td>p. 72</td>
    </tr>
    <tr>
      <td>G</td>
      <td>Graph, digraph, multi-(di)graph</td>
      <td>p. 44</td>
    </tr>
    <tr>
      <td>G</td>
      <td>Green's matrix of a system of linear non-autonomous ODEs</td>
      <td>p. 26</td>
    </tr>
    <tr>
      <td>G</td>
      <td>Semi continuous graph with discrete (space-like) and continuous (time-like) edges</td>
      <td>p. 20</td>
    </tr>
    <tr>
      <td>G</td>
      <td>Set of finite digraphs</td>
      <td>p. 67</td>
    </tr>
    <tr>
      <td>γ</td>
      <td>Simple cycle</td>
      <td>p. 17</td>
    </tr>
    <tr>
      <td>Γ(G)<sub>α</sub></td>
      <td>Set of simple cycles from α to itself on G</td>
      <td>p. 17</td>
    </tr>
    <tr>
      <td>H</td>
      <td>Hamiltonian matrix</td>
      <td>p. 33</td>
    </tr>
    <tr>
      <td>Θ</td>
      <td>Heaviside Θeta distribution</td>
      <td>p. 20</td>
    </tr>
    <tr>
      <td>H</td>
      <td>Hike monoid</td>
      <td>p. 46</td>
    </tr>
    <tr>
      <td>H</td>
      <td>Hike dependency graph</td>
      <td>p. 46</td>
    </tr>
    <tr>
      <td>H<sup>c</sup></td>
      <td>Hike independency graph</td>
      <td>p. 46</td>
    </tr>
    <tr>
      <td>h</td>
      <td>Hike</td>
      <td>p. 46</td>
    </tr>
    <tr>
      <td>h</td>
      <td>Induced subgraph relation</td>
      <td>p. 57</td>
    </tr>
    <tr>
      <td>1<sub>*</sub></td>
      <td>Identity element for the ★-product</td>
      <td>p. 21</td>
    </tr>
    <tr>
      <td>Id<sub>*</sub></td>
      <td>Identity matrix times the identity element for the ★-product</td>
      <td>p. 26</td>
    </tr>
    <tr>
      <td>K<sub>n</sub></td>
      <td>Complete graph on n vertices</td>
      <td>p. 75</td>
    </tr>
    <tr>
      <td>K</td>
      <td>Algebraically closed field of characteristic 0</td>
      <td>p. 12</td>
    </tr>
    <tr>
      <td>λ</td>
      <td>Hike Liouville function</td>
      <td>p. 50</td>
    </tr>
    <tr>
      <td>λ</td>
      <td>Dominant eigenvalue of a graph</td>
      <td>p. 55</td>
    </tr>
    <tr>
      <td>Λ</td>
      <td>Hike von Mangoldt function</td>
      <td>p. 48</td>
    </tr>
    <tr>
      <td>μ</td>
      <td>Mbius function on hikes</td>
      <td>p. 47</td>
    </tr>
    <tr>
      <td>⊙</td>
      <td>Nesting product</td>
      <td>p. 16</td>
    </tr>
    <tr>
      <td>P<sub>G</sub></td>
      <td>Poset of hikes on graph G ordered per left-divisibility</td>
      <td>p. 47</td>
    </tr>
    <tr>
      <td>P<sup>s.a.</sup></td>
      <td>Set of self-avoiding hike constructible from the primes of set P</td>
      <td>p. 56</td>
    </tr>
    <tr>
      <td>π<sub>ℓ</sub></td>
      <td>Number of of simple cycles of length ℓ</td>
      <td>p. 62</td>
    </tr>
    <tr>
      <td>Π(G)<sub>αω</sub></td>
      <td>Set of simple paths from α to ω on G</td>
      <td>p. 17</td>
    </tr>
    <tr>
      <td>ω(.)</td>
      <td>Number of prime factors of a hike</td>
      <td>p. 48</td>
    </tr>
    <tr>
      <td>Ω(.)</td>
      <td>Number of distinct prime factors of a hike</td>
      <td>p. 50</td>
    </tr>
    <tr>
      <td>ω<sup>k,k'</sup></td>
      <td>Closed walk w<sub>k</sub> ... w<sub>k'</sub> cut out of ω = w<sub>0</sub> ... w<sub>ℓ</sub></td>
      <td>p. 12</td>
    </tr>
    <tr>
      <td>ω<sub>k,k'</sub></td>
      <td>Remainder w<sub>0</sub> ... w<sub>k</sub> ... w<sub>k'+1</sub> ... w<sub>ℓ</sub> after removal of ω<sup>k,k'</sup> from ω</td>
      <td>p. 12</td>
    </tr>
    <tr>
      <td>Sf(s)</td>
      <td>Series associated with the function on hikes f</td>
      <td>p. 48</td>
    </tr>
    <tr>
      <td>Σ<sub>G; αω</sub></td>
      <td>Formal series of all walks from α to ω on G</td>
      <td>p. 17</td>
    </tr>
    <tr>
      <td>★, ★<sub>I</sub>, ★<sub>R</sub></td>
      <td>Star-product</td>
      <td>p. 21</td>
    </tr>
    <tr>
      <td>*</td>
      <td>Subgraph convolution</td>
      <td>p. 67</td>
    </tr>
    <tr>
      <td>T</td>
      <td>Trace monoid</td>
      <td>p. 45</td>
    </tr>
    <tr>
      <td>T<sub>CF</sub></td>
      <td>Trace monoid of Cartier-Foata</td>
      <td>p. 45</td>
    </tr>
    <tr>
      <td>T<sub>n</sub></td>
      <td>Tridiagonal matrix output of ★-Lanczos</td>
      <td>p. 29</td>
    </tr>
  </tbody>
</table>
<table>
  <tr>
    <td>ξ</td>
    <td>Time-ordering operator</td>
    <td>p. 19</td>
  </tr>
  <tr>
    <td>U</td>
    <td>Evolution operator, time-ordered exponential</td>
    <td>p. 19</td>
  </tr>
  <tr>
    <td>V</td>
    <td>Vertex set of a graph</td>
    <td>p. 44</td>
  </tr>
  <tr>
    <td>w, ω</td>
    <td>Walk</td>
    <td>p. 12</td>
  </tr>
  <tr>
    <td>W</td>
    <td>Labelled adjacency matrix of a graph</td>
    <td>p. 18</td>
  </tr>
  <tr>
    <td>W(G)</td>
    <td>Set of all walks on G</td>
    <td>p. 12</td>
  </tr>
  <tr>
    <td></td>
    <td>K-vector space of rooted walks on G</td>
    <td>p. 12</td>
  </tr>
  <tr>
    <td>W(G)<sub>αω</sub></td>
    <td>Set of all rooted walks on G from α to ω</td>
    <td>p. 17</td>
  </tr>
  <tr>
    <td>z</td>
    <td>Formal variable</td>
    <td>Throughout</td>
  </tr>
  <tr>
    <td>ζ</td>
    <td>Zeta function on hikes</td>
    <td>p. 48</td>
  </tr>
</table>
Bibliography

[1] A. A. Agrachev and R. V. Gamkrelidze. Chronological algebras and nonstationary vector fields. *Journal of Soviet Mathematics*, 17:1650–1675, 1981.

[2] A. A. Agrachev and S. A. Vakhrameev. Chronological series and the Cauchy-Kowalevski theorem. *Journal of Soviet Mathematics*, 21:231–250, 1983.

[3] N. Alon, R. Yuster, and U. Zwick. Finding and counting given length cycles. *Algorithmica*, 17:209–223, 1997.

[4] R. M. Angelo and W. F. Wreszinski. Two-level quantum dynamics, integrability, and unitary NOT gates. *Physical Review A*, 72:034105, 2005.

[5] T. Antal, P. L. Krapivsky, and S. Red. Social balance on networks: The dynamics of friendship and enmity. *Physica D: Nonlinear Phenomena*, 224:130–136, 2006.

[6] H. Aoki, N. Tsuji, M. Eckstein, M. Kollar, T. Oka, and P. Werner. Nonequilibrium dynamical mean-field theory and its applications. *Rev. Mod. Phys.*, 86:779, 2014.

[7] P. K. Aravind and J. O. Hirschfelder. Two-state systems in semiclassical and quantized fields. *The Journal of Physical Chemistry*, 88(21):4788–4801, 1984.

[8] S. Ashhab, J. R. Johansson, A. M. Zagoskin, and F. Nori. Two-level systems driven by large-amplitude fields. *Physical Review A*, 75:063414, 2007.

[9] D. Atkinson and F. J. van Steenwijk. Infinite resistive lattices. *American Journal of Physics*, 67(6):486–492, 1999.

[10] F. Aziz, R. C. Wilson, and E. R. Hancock. Backtrackless walks on a graph. *IEEE Transactions on Neural Networks and Learning Systems*, 24(6):977–989, 2013.

[11] E. T. Bax. Inclusion and exclusion algorithm for the Hamiltonian path problem. *Information Processing Letters*, 47(4):203–207, 1993.

[12] E. T. Bax. Algorithms to count paths and cycles. *Information Processing Letters*, 52(5):249–252, 1994.

[13] E. T. Bax and J. Franklin. A finite-difference sieve to count paths and cycles by length. *Information Processing Letters*, 60(4):171–176, 1996.

[14] V. Beffara. The dimension of the SLE curves. *The Annals of Probability*, 36(4):1421–1452, 2008.

[15] V. Beffara and H. Duminil-Copin. Planar percolation with a glimpse of Schramm-Loewner evolution. *Probability Surveys*, 10:1–50, 2013.

[16] M. Benzi, P. Boito, and N. Razouk. Decay properties of spectral projectors with applications to electronic structure. *SIAM Review*, 55:3–64, 2013.

[17] M. Benzi and G. H. Golub. Bounds for the entries of matrix functions with application to preconditioning. *BIT*, 39:417–438, 1999.

[18] M. Benzi and N. Razouk. Decay bounds and $O(n)$ algorithms for approximating functions of sparse matrices. *Electron. T. Numer. Ana.*, 28:16–39, 2007.

[19] N. Biggs. *Algebraic Graph Theory*. Cambridge University Press, Cambridge, 2nd edition, 1993.

[20] T. Birkandan, P.-L. Giscard, and A. Tamar. Computations of general Heun functions from their integral series representations. In *2021 Days on Diffraction (DD)*, pp. 12–18, 2021.

[21] E. Birmelé, R. Ferreira, R. Grossi, A. Marino, N. Pisanti, R. Rizzi, and G. Sacomoto. Optimal listing of cycles and st-paths in undirected paths. In *Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms*, pp. 1884–1896, 2013.

[22] A. Björklund. Determinant sums for undirected Hamiltonicity. *SIAM Journal on Computing*, 43(1):280–299, 2014.

[23] S. Blanes, F. Casas, J. A. Oteo, and J. Ros. The Magnus expansion and some of its applications. *Physics Reports*, 470(5):151–238, 2009.

[24] F. Bloch and A. Siegert. Magnetic resonance for nonrotating fields. *Physical Review*, 57:522–527, 1940.

[25] C. Bonhomme, S. Pozza, and N. Van Buggenhout. A new fast numerical method for the generalized Rosen-Zener model. arXiv:2311.04144 [math.NA], 2023.
[26] K. M. Borgwardt and H.-P. Kriegel. Shortest-path kernels on graphs. In *Proceedings of the 5th IEEE International Conference on Data Mining (ICDM 2005)*, 27-30 November 2005, Houston, Texas, USA, pp. 74-81, 2005.

[27] M. Bousquet-Mélou. *q-Énumération de Polyominos Convexes*. PhD thesis, Université du Québec à Montréal, Département de mathématiques et d'informatique, 1991.

[28] M. Bousquet-Mélou. *Q-Énumération de Polyominos Convexes*. *Journal of Combinatorial Theory, Series A*, 64(2):265-288, 1993.

[29] M. Brion. Representations of quivers. *Notes, summer school on Geometric Methods in Representation Theory, Grenoble*, 2008.

[30] R. Brüschweiler and R. R. Ernst. A cog-wheel model for nuclear-spin propagation in solids. *Journal of Magnetic Resonance*, 124(1):122-126, 1997.

[31] P. Bürgisser, M. Clausen, and M. Amin Shokrollahi. *Algebraic Complexity Theory*, volume 315 of *Grundlehren der mathematischen Wissenschaften*. Springer, Berlin; New York, 1997.

[32] P. Cartier and D. Foata. Problèmes combinatoires de commutation et réarrangements. *Lecture notes in mathematics*, 85, 1969.

[33] D. Cartwright and F. Harary. Structural balance: a generalization of heider's theory. *Psychological Review*, 63:277-293, 1956.

[34] F. Casas. Sufficient conditions for the convergence of the Magnus expansion. *Journal of Physics A: Mathematical and Theoretical*, 40(50):15001-15017, 2007.

[35] G. G. Cash. The number of *n*-cycles in a graph. *Applied mathematics and computation*, 184(2):1080-1083, 2007.

[36] J. Cerha. A note on Volterra integral equations with degenerate kernel. *Commentationes Mathematicae Universitatis Carolinae*, 13(4):659-672, 1972.

[37] Y. C. Chang and H. L. Fu. The number of 6-cycles in a graph. *Bull. Inst. Combin. Appl.*, 39:27-30, 2003.

[38] G. S. Cheon, A. Luzn, M. A. Morn, L. F. Prieto-Martinez, and M. Song. Finite and infinite dimensional Lie group structures on Riordan groups. *Advances in Mathematics*, 319:522-566, 2017.

[39] S. Cipolla, S. Pozza, M. Redivo-Zaglia, and N. Van Buggenhout. A Lanczos-type procedure for tensors. *Numerical Algorithms*, 92:377-406, 2023.

[40] M. Cramer and J. Eisert. Correlations, spectral gap and entanglement in harmonic quantum systems on generic lattices. *New J. Phys.*, 8:71, 2006.

[41] J. Cserti, G. Széchenyi, and G. Dávid. Uniform tiling with electrical resistors. *Journal of Physics A: Mathematical and Theoretical*, 44(21):215201, 2011.

[42] D. J. Daniel. Exact solutions of Mathieu equations. *Prog. Theor. Exp. Phys.*, 4:043A01, 2020.

[43] R. Diestel. *Graph theory* {graduate texts in mathematics; 173}. Springer-Verlag Berlin and Heidelberg, 2000.

[44] R. G. Downey and M. R. Fellows. *Parameterized Complexity*. Monographs in Computer Science. Springer, New York, 1999.

[45] J.-N. Dumez, M. C. Butler, and L. Emsley. Numerical simulation of free evolution in solid-state Nuclear Magnetic Resonance using low-order correlations in Liouville space. *The Journal of Chemical Physics*, 133(22):224501, 2010.

[46] H. Duminil-Copin and S. Smirnov. The connective constant of the honeycomb lattice equals $\sqrt{2 + \sqrt{2}}$. *Annals of Mathematics*, 175:1653-1665, 2012.

[47] F. J. Dyson. Divergence of Perturbation Theory in Quantum Electrodynamics. *Physical Review*, 85(4):631-632, 1952.

[48] Epinions social network. http://snap.stanford.edu/data/soc-sign-epinions.html, accessed in September 2023.

[49] T. Espinasse and P. Rochet. A coupling of the spectral measures at a vertex. *The Electronic Journal of Combinatorics*, 26:1-15, 2019.

[50] E. Estrada and J. Rodríguez-Velázquez. Subgraph centrality in complex graphs. *Physical Review E*, 5:056103, 2005.

[51] E. Estrada and J. A. Rodríguez-Velázquez. Subgraph centrality in complex networks. *Physical Review E*, 71:056103, 2005.

[52] F. F. Harary and J. A. Kabell. A simple algorithm to detect balance in signed graphs. *Mathematical Social Sciences*, 1:131-136, 1980.

[53] E. B. Fel'dman. On the convergence of the Magnus expansion for spin systems in periodic magnetic fields. *Physics Letters*, 104A(9):479-481, 1984.

[54] S. Finski. Spanning trees, cycle-rooted spanning forests on discretizations of flat surfaces and analytic torsion. *Mathematische Zeitschrift*, 301(4):3285-3343, 2022.

[55] P. Flajolet and R. Sedgewick. *Analytic Combinatorics*. Cambridge University Press, Cambridge, 1st edition, 2009.
[56] J. Flum and M. Grohe. The Parameterized Complexity of Counting Problems. *SIAM Journal on Computing*, 33(892–922, 2004.

[57] L. Foissy, P.-L. Giscard, and C. Mammez. A co-preLie structure from chronological loop erasure in graph walks. *arXiv:2306.17605 [math.CO]*, 2023.

[58] J. Fromentin, P.-L. Giscard, and T. Karaboghossian. Realizable cycle structures in digraphs. *European Journal of Combinatorics*, 113:103748, 2023.

[59] P.-L. Giscard. *A graph theoretic approach to matrix functions and quantum dynamics*. PhD thesis, Oxford University, UK, 2014.

[60] P.-L. Giscard. On the solutions of linear Volterra equations of the second kind with sum kernels. *Journal of Integral Equations and Applications*, 32(4):429–445, 2020.

[61] P.-L. Giscard. Counting walks by their last erased self-avoiding polygons using sieves. *Discrete Mathematics*, 344(4):112305, 2021.

[62] P.-L. Giscard and C. Bonhomme. Dynamics of quantum systems driven by time-varying Hamiltonians: Solution for the Bloch-Siegert Hamiltonian and applications to NMR. *Physical Review Research*, 2:023081, 2020.

[63] P.-L. Giscard, Z. Choo, S. J. Thwaite, and D. Jaksch. Exact inference on gaussian graphical models of arbitrary topology using path-sums. *Journal of Machine Learning Research*, 17(71):1–19, 2016.

[64] P.-L. Giscard and M. Foroozandeh. Exact solutions for the time-evolution of quantum spin systems under arbitrary waveforms using algebraic graph theory. *Computer Physics Communications*, 282:108561, 2023.

[65] P.-L. Giscard, N. Kriege, and R. C. Wilson. CycleCount, CyclePathCount, PathCount, MATLAB algorithms. http://www-lmpa.univ-littoral.fr/~plgiscard/, 2017.

[66] P.-L. Giscard, N. Kriege, and R. C. Wilson. A general purpose algorithm for counting simple cycles and simple paths of any length. *Algorithmica*, 81(7):2716–2737, 2019.

[67] P.-L. Giscard, K. Lui, S. J. Thwaite, and D. Jaksch. An exact formulation of the time-ordered exponential using path-sums. *Journal of Mathematical Physics*, 56(5):053503, 2015.

[68] P.-L. Giscard and S. Pozza. Lanczos-like algorithm for the time-ordered exponential: The $\star$-inverse problem. *Applications of Mathematics*, 65:807–827, 2020.

[69] P.-L. Giscard and S. Pozza. Tridiagonalization of systems of coupled linear differential equations with variable coefficients by a Lanczos-like method. *Linear Algebra and its Applications*, 624:153–173, 2021.

[70] P.-L. Giscard and S. Pozza. A Lanczos-like method for non-autonomous linear ordinary differential equations. *Bolletino dell Unione Matematica Italiana*, 16:81–102, 2023.

[71] P.-L. Giscard and P. Rochet. Algebraic combinatorics on trace monoids: Extending number theory to walks on graphs. *SIAM Journal on Discrete Mathematics*, 31(2):1428–1453, 2017.

[72] P.-L. Giscard and P. Rochet. Enumerating simple paths from connected induced subgraphs. *Graphs and Combinatorics*, 34(6):1197–1202, 2018.

[73] P.-L. Giscard, P. Rochet, and R. C. Wilson. Evaluating balance on social networks from their simple cycles. *Journal of Complex Networks*, 5(5):750–775, 2017.

[74] P.-L. Giscard, P. Rochet, and R. C. Wilson. A Hopf algebra for counting cycles. *Discrete Mathematics*, 341(5):1439–1448, 2018.

[75] P.-L. Giscard and A. Tamar. Elementary integral series for Heun functions: Application to black-hole perturbation theory. *Journal of Mathematical Physics*, 63(6):063501, 2022.

[76] P.-L. Giscard, S. J. Thwaite, and D. Jaksch. Walk-sums, continued fractions and unique factorisation on digraphs. *arXiv:1202.5523 [cs.DM]*, 2012.

[77] P.-L. Giscard, S. J. Thwaite, and D. Jaksch. Evaluating matrix functions by resummations on graphs: The method of path-sums. *SIAM Journal on Matrix Analysis and Applications*, 34(2):445–469, 2013.

[78] P.-L. Giscard and R. C. Wilson. The all-paths and cycles graph kernel. *arXiv:1708.01410 [cs.LG]*, 2017.

[79] P.-L. Giscard and R. C. Wilson. A centrality measure for cycles and subgraphs ii. *Applied Network Science*, 3(1):9, 2018.

[80] P.-L. Giscard and R. C. Wilson. Cycle-centrality in economic and biological networks. In C. Cherifi, H. Cherifi, M. Karsai, and M. Musolesi, editors, *Complex Networks & Their Applications VI*, pp. 14–28, Cham, 2018. Springer International Publishing.

[81] R. L. Greenblatt. Discrete and zeta-regularized determinants of the Laplacian on polygonal domains with Dirichlet boundary conditions. *Journal of Mathematical Physics*, 64(4):043301, 2023.

[82] M. Grifoni and P. Hnggi. Driven quantum tunneling. *Physics Reports*, 304(5):229–354, 1998.

[83] D. Grinberg and V. Reiner. Hopf Algebras in Combinatorics. *arXiv:1409.8356 [math.CO]*, 2014.

[84] G. Gripenberg, S. O. Londen, and O. Staffans. *Volterra Integral and Functional Equations*. Oxford Mathematical Monographs. Cambridge University Press, Cambridge, 1990.

[85] M. Grohe. Descriptive and parameterized complexity. In J. Flum and M. Rodriguez-Artalejo, editors, *Computer Science Logic*, volume 1683 of *Lecture Notes in Computer Science*, chapter 3, pp. 14–31. Springer-Verlag, Berlin Heidelberg, 1999.
[86] F. Großmann and P. Hnggi. Localization in a driven two-level dynamics. *Europhysics Letters (EPL)*, 18(7):571-576, 1992.

[87] U. Güldener, M. Münsterkötter, M. Oesterheld, P. Pagel, A. Ruepp, H.-W. Mewes, and V. Stümpflen. MPact: the MIPS protein interaction resource on yeast. *Nucleic Acids Res*, 34 part 1:D436–41, 2006.

[88] W. Hackbusch. *Integral Equations: Theory and Numerical Treatment*. Birkhäuser Basel, 1995.

[89] U. Haeberlen. *High Resolution NMR in Solids Selective Averaging*. Supplement 1 Advances in Magnetic Resonance. Academic Press, 1st edition edition, 1976.

[90] F. Harary. On the measurement of structural balance. *Behavioral Science*, 4:316-323, 1959.

[91] F. Harary and B. Manvel. On the number of cycles in a graph. *Matematický časopis*, 21:55–63, 1971.

[92] G. T. Hart, I. Lee, and E. R. Marcotte. A high-accuracy consensus map of yeast protein complexes reveals modular nature of gene essentiality. *BMC Bioinformatics*, 8:236, 2007.

[93] L. H. Hartwell, J. J. Hopfield, S. Leibler, and A. W. Murray. From molecular to modular cell biology. *Nature*, 402:C47–C52, 1999.

[94] D. Haussler. Convolution kernels on discrete structures. Technical Report UCSC-CRL-99-10, University of California at Santa Cruz, 1999.

[95] F. Heider. Attitudes and cognitive organization. *The Journal of Psychology*, 21:107–112, 1946.

[96] K. Heun. Zur Theorie der Riemann'chen Functionen Zweiter Ordnung mit Verzweigungspunkten. *Math. Ann.*, 33:161–179, 1888.

[97] M. Hortaçsu. Heun functions and some of their applications in physics. *Adv. High Energy Phys.*, 2018:8621573, 2018.

[98] R. Impagliazzo and R. Paturi. On the Complexity of $k$-SAT. *Journal of Computer and System Sciences*, 62:367–375, 2001.

[99] A. Iserles, H. Z. Munthe-Kaas, S. P. Nrsett, and A. Zanna. Lie-group methods. *Acta Numerica*, 9:215–365, 2000.

[100] F. Jaeger. A survey of the cycle double cover conjecture. In B.R. Alspach and C.D. Godsil, editors, *Annals of Discrete Mathematics (27): Cycles in Graphs*, volume 115 of *North-Holland Mathematics Studies*, pp. 1–12. North-Holland, 1985.

[101] D. B. Johnson. Finding all the elementary circuits of a directed graph. *SIAM J. Comput.*, 4:77–84, 1975.

[102] B. Jones and M. West. Covariance decomposition in undirected Gaussian graphical models. *Biometrika*, 92:779–786, 2005.

[103] R. M. Karp. Dynamic programming meets the principle of inclusion and exclusion. *Operations Research Letters*, 1(2):49–51, 1982.

[104] R. Kenyon. The asymptotic determinant of the discrete Laplacian. *Acta Mathematica*, 185(2):239–286, 2000.

[105] N. P. Khomenko and L. D. Golovko. Identifying certain types of parts of a graph and computing their number. *Ukrainskii Matematicheskii Zhurnal*, 24:385–396, 1972.

[106] N. P. Khomenko and E. N. Shevchenko. The problem of isolating and counting. *Ukrainian Mathematical Journal*, 30(2):152–160, 1978.

[107] Y. N. Kosovtsov. The introduction to the operator method for solving differential equations. First-order DE. arXiv:math-ph/0202040, 2002.

[108] Y. N. Kosovtsov. The chronological operator algebra and formal solutions of differential equations. arXiv:0409035v1, 2004.

[109] Y. N. Kosovtsov. Formal exact operator solutions to nonlinear differential equations. arXiv:0910.3923v1, 2009.

[110] J. J. Kovacic. An algorithm for solving second order linear homogeneous differential equations. *Journal of Symbolic Computation*, 2(1):3–43, 1986.

[111] C. Krattenthaler. The theory of heaps and the Cartier-Foata monoid. *Appendix of the electronic edition of "Problèmes combinatoires de commutation et réarrangements"*, 2006.

[112] N. M. Kriege, P.-L. Giscard, and R. C. Wilson. On valid optimal assignment kernels and applications to graph classification. In *Proceedings of the 30th International Conference on Neural Information Processing Systems*, pp. 1623–1631, 2016.

[113] N. M. Kriege, F. D. Johansson, and C. Morris. A survey on graph kernels. *Applied Network Science*, 5(1):6, 2020.

[114] S. L. Lauritzen. *Graphical Models*. Oxford University Press, 1996.

[115] G. Lawler. A self-avoiding random walk. *Duke Mathematical Journal*, 47(3):655–693, 1980.

[116] G. Lawler. Conformally invariant loop measures. In *Proceedings of the International Congress Of Mathematicians, Rio de Janeiro*, volume 1, pp. 669–704, 2018.

[117] G. Lawler, O. Schramm, and W. Werner. The dimension of the planar brownian frontier is 4/3. *Mathematical Research Letters*, 8:401–411, 2001.
[118] G. Lawler, O. Schramm, and W. Werner. Fractal geometry and applications: a jubilee of Benoît Mandelbrot. *Proc. Sympos. Pure Math.*, 72:339–364, 2004.

[119] G. Lawler and J. Trujillo Ferreras. Random walk loop soup. *Transactions of the American Mathematical Society*, 359:767–787, 2007.

[120] G. Lawler and W. Wendelin. Universality for conformally invariant intersection exponents. *Journal of the European Mathematical Society*, 2:291–328, 2000.

[121] G. Lawler and W. Werner. The Brownian loop soup. *Probability Theory and Related Fields*, 128(4):565–588, 2004.

[122] G. F. Lawler. Loop-erased self-avoiding random walk and the Laplacian random walk. *Journal of Physics A: Mathematical and General*, 20(13):4565, 1987.

[123] G. F. Lawler. Loop-erased random walk. In M. Bramson and R. Durrett, editors, *Perplexing Problems in Probability: Festschrift in Honor of Harry Kesten*, pp. 197–217. Birkhäuser, 1999.

[124] P. Linz. *Analytical and Numerical Methods for Volterra Equations*. Society for Industrial and Applied Mathematics, 1985.

[125] M. Livernet. A rigidity theorem for pre-Lie algebras. *Journal of Pure and Applied Algebra*, 207:1–18, 2006.

[126] Z. Lü and H. Zheng. Effects of counter-rotating interaction on driven tunneling dynamics: Coherent destruction of tunneling and Bloch-Siegert shift. *Physical Review A*, 86:023831, 2012.

[127] P. A. MacMahon. *Combinatory analysis*. Cambridge: The University Press, 1915.

[128] N. Madras and G. Slade. *The self-avoiding walk*. Springer Science & Business Media, 2013.

[129] W. Magnus. On the exponential solution of differential equations for a linear operator. *Communications on Pure and Applied Mathematics*, 7(4):649–673, 1954.

[130] P. Mahé and J.-P. Vert. Graph kernels based on tree patterns for molecules. *Machine Learning*, 75(1):3–35, 2009.

[131] R. S. Maier. The 192 solutions of the Heun equation. *Math. Comp.*, 76:811–843, 2007.

[132] D. M. Malioutov, J. K. Johnson, and A. S. Willsky. Walk-sums and belief propagation in Gaussian graphical models. *Journal of Machine Learning Research*, 7:2031–2064, 2006.

[133] E. Mananga. Theoretical perspectives of spin dynamics in solid-state Nuclear Magnetic Resonance and physics. *Journal of Modern Physics*, 9:1645–1659, 2018.

[134] B. Mandelbrot. *The fractal geometry of nature*. Freeman, San Francisco, CA, 1982.

[135] S. Mano, H. Suzuki, and E. Takasugi. Analytical solutions of the Teukolsky equation and their low frequency expansions. *Prog. Theor. Phys.*, 95:1079–1096, 1996.

[136] M. M. Maricq. Convergence of the Magnus expansion for time dependent two level systems. *The Journal of Chemical Physics*, 86(10):5647–5651, 1987.

[137] P. Mateti and N. Deo. On Algorithms for Enumerating all Circuits of a Graph. *SIAM J. Comput.*, 5:90–99, 1976.

[138] B. D. McKay and A. Piperno. Practical graph isomorphism, ii. *Journal of Symbolic Computation*, 60:94–112, 2014.

[139] F. Menous and F. Patras. Logarithmic derivatives and generalized Dynkin operators. *Journal of Algebraic Combinatorics*, 38(4):901–913, 2013.

[140] F. Mentink-Vigier, S. Vega, and G. De Pape. Fast and accurate MASDNP simulations of large spin ensembles. *Physical Chemistry Chemical Physics*, 19:3506–3522, 2017.

[141] R. Merris. Single-hook characters and Hamiltonian circuits. *Linear and Multilinear Algebra*, 14:21–35, 1983.

[142] R. Merris. Immanantal invariants of graphs. *Linear Algebra and its Applications*, 401:67–75, 2005.

[143] J. G. Mikusiski. Sur la méthode de généralisation de M. Laurent Schwartz et sur la convergence faible. *Fundamenta Mathematicae*, 35:235–239, 1948.

[144] M. Milani. Cycle Index, PYTHON algorithm, 2017. https://github.com/milani/cycleindex.

[145] J. W. Milnor and J. C. Moore. On the structure of Hopf algebras. *Ann. of Math.*, 81:211–264, 1965.

[146] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network motifs: simple building blocks of complex networks. *Science*, 298:824–827, 2002.

[147] C. W. Misner, K. S. Thorne, and J. A. Wheeler. *Gravitation*. W.H. Freeman and Company, San Francisco, USA, 1973.

[148] S. Montgomery. *Hopf Algebras and Their Actions on Rings*, volume 82 of CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences by the American Mathematical Society, 1993.

[149] N. Movarraei and S. A. Boxwala. On the Number of Cycles in a Graph. *Open Journal of Discrete Mathematics*, pp. 41–69, 2016.

[150] M. S. Mukhtar, A.-R. Carvunis, M. Dreze, P. Epple, J. Steinbrenner, J. Moore, M. Tasan, M. Galli, T. Hao, M. T. Nishimura, S. J. Pevzner, S. E. Donovan, L. Ghamsari, B. Santhanam, V. Romero, M. M. Poulin, F. Gebreab, B. J. Gutierrez, S. Tam, D. Monachello, M. Boxem, C. J. Harbort, N. McDonald,
L. Gai, H. Chen, Y. He, J. Vandenh aute, F. P. Roth, D. E. Hill, J. R. Ecker, M. Vidal, J. Beynon, P. Braun, and J. L. Dangl. Independently Evolved Virulence Effectors Converge onto Hubs in a Plant Immune System Network. *Science*, 333:596–601, 2011.

[151] R. Z. Norman. A derivation of a measure of relative balance for social structures and a characterization of extensive ratio systems. *Journal of Mathematical Psychology*, 9:66–91, 1972.

[152] Z. N. Oltvai and A.-L. Barabási. Life's complexity pyramid. *Science*, 298:763, 2002.

[153] T. Opsahl, F. Agneessens, and J. Skvoretz. Node centrality in weighted networks: Generalizing degree and shortest paths. *Social Networks*, 32(3):245–251, 2010.

[154] W. Orr. Statistical treatment of polymer solutions at infinite dilution. *Transactions of the Faraday Society*, 43:12–27, 1947.

[155] B. N. Parlett. Reduction to tridiagonal form and minimal realizations. *SIAM J. Matrix Anal. Appl.*, 13(2):567–593, 1992.

[156] F. Patras and C. Reutenauer. Higher Lie idempotents. *Journal of Algebra*, 222:51–64, 1999.

[157] F. Patras and C. Reutenauer. On Dynkin and Klyachko idempotents in graded bialgebras. *Advances in Mathematics*, 28:560–579, 2002.

[158] J. Pearl. *Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference*. Morgan Kaufmann Publishers Inc., San Mateo, California, 1988.

[159] S. N. Perepechko and A. N. Voropaev. The number of fixed length cycles in an undirected graph. explicit formulae in case of small lengths. *Mathematical Modeling and Computational Physics (MMCP2009)*, pp. 148–149, 2009.

[160] S. N. Perepechko and A. N. Voropaev. Количество простых циклов фиксированной длины в неориентированном графе. *Явные формулы в случае малых длин*. (The Number of Fixed Length Cycles in Undirected Graph. Explicit Formulae in Case of Small Lengths). Вестник РУДН. Серија Математика. Информатика. Физика, 2:5–11, 2012.

[161] N. B. Pleshchinskii and R. R. Tagirov. On the structure of the solutions of Volterra integral equations with degenerate kernel. *Journal of Mathematical Sciences*, 74(5):1268–1273, 1995.

[162] A. D. Polyanin and A. V. Manzhirov. *Handbook of Integral Equations*. Chapman and Hall / CRC, second edition, 2008.

[163] J. Ponstein. Self-avoiding paths and the adjacency matrix of a graph. *SIAM Journal on Applied Mathematics*, 14(3):600–609, 1966.

[164] S. Pozza. A new closed-form expression for the solution of ODEs in a ring of distributions and its connection with the matrix algebra. arXiv:2302.11375 [math.NA], 2024.

[165] S. Pozza and N. Van Buggenhout. A new Legendre polynomial-based approach for non-autonomous linear ODEs. arXiv:2303.11284 [math.NA], 2023.

[166] S. Pozza and N. Van Buggenhout. A new matrix equation expression for the solution of non-autonomous linear systems of ODEs. *PAMM*, 22:e202200117, 2023.

[167] S. Pozza and N. Van Buggenhout. A *-product solver with spectral accuracy for non-autonomous ordinary differential equations. *PAMM*, 23:e202200050, 2023.

[168] S. Pu, J. Wong, B. Turner, E. Cho, and S. J. Wodak. Up-to-date catalogues of yeast protein complexes. *Nucleic Acids Res.*, 37(3):825–831, 2008.

[169] X. Qi, E. Fuller, Q. Wu, Y. Wu, and C.-Q. Zhang. Laplacian centrality: A new centrality measure for weighted networks. *Information Sciences*, 194:240–253, 2012. Intelligent Knowledge-Based Models and Methodologies for Complex Information Systems.

[170] J. Ramon and T. Gärtner. Expressivity versus efficiency of graph kernels. In L. De Raedt and T. Washio, editors, *Proceedings of the First International Workshop on Mining Graphs, Trees and Sequences (MGTS 2003) at the 14th European Conference on Machine Learning and 7th European Conference on Principles and Practice of Knowledge Discovery in Databases (ECML/PKDD 2003)*, September 22 and 23, 2003, Cavtat-Dubrovnik, Croatia, pp. 65–74, 2003.

[171] S. Roman and G.-C. Rota. The umbral calculus. *Advances in Mathematics*, 27(2):95–188, 1978.

[172] I. C. Ross and F. Harary. On the determination of redundancies in sociometric chains. *Psychometrika*, 17:195–208, 1952.

[173] G.-C. Rota. On the foundations of combinatorial theory. In *Classic Papers in Combinatorics*, pp. 332–360. Springer, 1987.

[174] H. Rue and L. Held. *Gaussian Markov Random Fields: Theory and Applications*. Chapman & Hall/CRC, 2005.

[175] M. Ryckebusch. A Fréchet-Lie group on distributions. arXiv:2307.09037 [math.FA], 2023. M. Ryckebusch is a Ph.D. student supervised by P.-L. Giscard.

[176] S. Sánchez, F. Casas, and A. Fernández. New analytic approximations based on the Magnus expansion. *Journal of Mathematical Chemistry*, 49(8):1741–1758, 2011.

[177] J. Sándor and B. Crstici. *Handbook of number theory II*, volume 2. Springer Science & Business Media, 2004.
[178] W. R. Schmitt. Hopf algebras and identities in free partially commutative monoids. *Theoretical Computer Science*, 73:335-340, 1990.

[179] R. Schott and G. S. Staples. Complexity of counting cycles using Zeons. *Computers & Mathematics with Applications*, 62(4):1828-1837, 2011.

[180] L. Schwartz. *Théorie Des Distributions*. Hermann, Paris, nouvelle édition, entièrement corrigée, refondue et augmentée édition, 1978.

[181] F. Schfer. *Darstellung und Berechnung von Matrixfunktionen*. Dissertation (phd), University of Klagenfurt, 2017.

[182] M. Sezer. Taylor polynomial solutions of Volterra integral equations. *International Journal of Mathematical Education in Science and Technology*, 25(5):625-633, 1994.

[183] M. Shao. On the finite section method for computing exponentials of doubly-infinite skew-Hermitian matrices. *Linear Algebra and its Applications*, 451:65-96, 2014.

[184] L. W. Shapiro, S. Getu, W.-J. Woan, and L. C. Woodson. The Riordan group. *Discrete Applied Mathematics*, 34(1):229-239, 1991.

[185] J. H. Shirley. Solution of the Schrödinger equation with a Hamiltonian periodic in time. *Physical Review*, 138:B979-B987, 1965.

[186] S. Smirnov. Conformal invariance in random cluster models. I. Holomorphic fermions in the Ising model. *Annals of Mathematics*, 172:1435-1467, 2010.

[187] K. Takegoshi, N. Miyazawa, K. Sharma, and P. K. Madhu. Comparison among Magnus/Floquet/Fer expansion schemes in solid-state NMR. *The Journal of Chemical Physics*, 142(13):134201, 2015.

[188] A. Terras. *Zeta Functions of Graphs: A Stroll through the Garden*. Cambridge University Press, Cambridge, 1st edition, 2011.

[189] S. A. Teukolsky. Perturbations of a rotating black hole. I. Fundamental equations for gravitational, electromagnetic, and neutrino-field perturbations. *Astroph. J.*, 185:635-648, 1973.

[190] J.-Y. Thibon. Lie idempotents in descent algebras. Online resource www-igm.univ-mlv.fr/~jyt/TALKS/lieids.ps, accessed 2016.

[191] M. Thorwart, L. Hartmann, I. Goychuk, and P. Hänggi. Controlling decoherence of a two-level atom in a lossy cavity. *Journal of Modern Optics*, 47(14-15):2905-2919, 2000.

[192] R. Uehara. The number of connected components in graphs and its applications. *IEICE Technical Report, COMP99-10*, 1999.

[193] L. G. Valiant. The complexity of computing the permanent. *Theoret. Comput. Sci.*, 8:189-201, 1979.

[194] L. G. Valiant. The Complexity of Enumeration and Reliability Problems. *SIAM J. Comput.*, 8:410-421, 1979.

[195] G. X. Viennot. Heaps of pieces, i: Basic definitions and combinatorial lemmas. In *Combinatoire énumérative*, pp. 321-350. Springer, 1986.

[196] G. X. Viennot. Heaps of pieces, i: Basic definitions and combinatorial lemmas. *Annals of the New York Academy of Sciences*, 576(1):542-570, 1989.

[197] M. Vogl, P. Laurell, A. D. Barr, and G. A. Fiete. Flow equation approach to periodically driven quantum systems. *Physical Review X*, 9:021037, 2019.

[198] W. von Waldenfels. Zur Charakterisierung Liescher Elemente in freien Algebren. *Archiv der Mathematik*, 17:44-48, 1966.

[199] J. S. Waugh, L. M. Huber, and U. Haeberlen. Approach to High-Resolution NMR in Solids. *Physical Review Letters*, 20:180-182, 1968.

[200] Y. Weiss and W. T. Freeman. Correctness of belief propagation in Gaussian graphical models of arbitrary topology. *Neural Computation*, 13:2173-2200, 2001.

[201] W. Werner. The conformally invariant measure on self-avoiding loops. *Journal of the American Mathematical Society*, 21:137-169, 2000.

[202] S. Wuchty, Z. N. Oltvai, and A.-L. Barabási. Evolutionary conservation of motif constituents in the yeast protein interaction network. *Nature Genetics*, 35:176-179, 2003.

[203] Q. Xie and W. Hai. Analytical results for a monochromatically driven two-level system. *Physical Review A*, 82:032117, 2010.

[204] Y. Yan, Z. Lü, and H. Zheng. Bloch-Siegert shift of the rabi model. *Physical Review A*, 91:053834, 2015.

[205] E. Yeger-Lotem, S. Sattath, N. Kashtan, S. Itzkovitz, R. Milo, R. Y. Pinter, U. Alon, and H. Margalit. Network motifs in integrated cellular networks of transcription-regulation and protein-protein interaction. *Proc. Natl. Acad. Sci. U.S.A.*, 101:5934-5939, 2004.

[206] D. Zeuch, F. Hassler, J. J. Slim, and D. P. DiVincenzo. Exact rotating wave approximation. *Annals of Physics*, 423:168327, 2020.

[207] J. Zhang, S. Saha, and D. Suter. Bloch-Siegert shift in a hybrid quantum register: Quantification and compensation. *Physical Review A*, 98:052354, 2018.

[208] Y.-Y. Zhang and Q.-H. Chen. Generalized rotating-wave approximation for the two-qubit quantum Rabi model. *Physical Review A*, 91:013814, 2015.