arXiv CSopen access

Temporal Conductance and Bounds on the Voter Model for Dynamic Networks

Temporal Conductance and Bounds on the Voter Model for Dynamic Networks Tatiana Rocha Avila∗

Holger Dell†

John Lapinskas‡

arXiv:2606.13374v1 [cs.DC] 11 Jun 2026

June 12, 2026

Abstract The voter model is a classical stochastic process that models how opinions might spread through a network: at each step, every node lazily adopts the opinion of a random neighbour; eventually all nodes share the same opinion (consensus). Stronger connectivity should yield faster consensus. Berenbrink, Giakkoupis, Kermarrec, and Mallmann-Trenn (ICALP 2016) make this precise via the network’s conductance: if the network has m edges, minimum degree dmin , and conductance at least ϕ, then the voter model reaches consensus in expected O(m/(dmin ϕ)) steps. Their results extend to dynamic networks with fixed vertex degrees by considering the network’s conductance at each time step. We introduce temporal conductance Φ, a more general connectivity measure for dynamic networks. Unlike static conductance, which collapses to 0 whenever some snapshot is disconnected, Φ captures connectivity through edges that appear at different times. We generalise the results of Berenbrink et al. from static conductance to temporal conductance, showing that the expected consensus time of the standard voter model is at most O(m/(dmin Φ)). Moreover, we prove that this bound is tight up to constant factors. We expect temporal conductance to be a useful primitive for analysing other dynamics on temporal networks, and potentially time-inhomogeneous Markov chains more generally.

1

Introduction

The voter model [8, 16] is a model of how opinions spread through a social network, see Fig. 1. It is most interesting not because it is realistic—it is too simplistic for that—but because it resists rigorous mathematical analysis despite its simplicity. If we cannot analyze the voter model, then we are unlikely to be able to analyze realistic models of opinion dynamics, which are more complex. The voter model serves as a testbed for methods in network dynamics more generally, and has been the subject of a large body of work in the mathematical physics [6] and probability [22] communities. Consensus time. One of the most fundamental questions about the voter model is this: How long does it take for the process to reach consensus, that is, for all vertices to have the same opinion? Results span a wide range of graph families: on the complete graph Kn the expected consensus time is Θ(n) [22]; on random regular graphs it is also Θ(n) [10]; on heterogeneous (configuration-model) ∗

Goethe University Frankfurt, Germany IT University of Copenhagen, Denmark ‡ University of Bristol, UK †

1

update

chose neighbor to copy

after update

Figure 1: An update step in the standard voter model with two opinions (that is, all vertices act independently and synchronously). In the left panel, each vertex points to a neighbour that it chooses randomly; a self-loop means that the vertex is “lazy” and keeps its current opinion; this happens with probability 12 . In the right panel, every vertex has adopted the opinion of the vertex that it pointed to. graphs it depends on the degree distribution [27]; and on subcritical scale-free graphs the exponent varies in a rich phase diagram [12]. An important result by Berenbrink et al. [5] shows that the expected consensus time of the voter model is captured by the conductance of the underlying graph, which is a measure of how wellconnected the graph is. In particular, they show that the consensus time is at most O(m/(dmin ϕ)), where m is the number of edges in the graph, dmin is the minimum degree of any vertex, and ϕ is the conductance of the graph. They also show that there are graphs where this upper bound is asymptotically tight. Voter model in temporal graphs. When it comes to real-world social networks, the underlying graph is not static; it changes over time. For example, people make new friends, they interact with different subsets of people at different times, and during pandemics, lockdowns may be imposed or lifted. This motivates the study of the voter model as a test-bed for network dynamics on temporal graphs G, which are sequences of graphs that change over time: G = (Gt : t ∈ N). In the context of spreading processes like the voter model, this is particularly useful in settings where the graph structure is independent from the spreading process being studied and can be observed in detail, such as epidemic modelling in livestock markets [2] or schools [28]. The results of [5] are stated for the temporal setting as well, in the setting where vertex degrees are fixed with respectPto time, by considering the conductance ϕt of the graph at each time step t. They show that if Tt=0 ϕt ≥ Cm/dmin for an appropriate constant C, then with probability at least 1/2 the absorption time is at most T ; in particular, if ϕt ≥ ϕ for all t ≥ 0 then this generalises their result in the static case. However, both bounds are proved in an adaptive setting, where an adversary can choose each graph Gt with full knowledge of the state of the voter model at time t − 1, rather than the non-adaptive paradigm described above where the graph and voter model evolve independently. While their upper bound carries over to this setting immediately, their lower bound does not. As a simple example, consider an n-vertex temporal graph consisting of one uniformly-random perfect matching per time step, drawn independently. It is not hard to show that such a graph has O(log PT n) expected absorption time in the voter model, but it is disconnected at every time step so t=0 ϕt = 0 for all T — that is, the results of [5] do not give any upper bound on the expected absorption time. Our contribution. In this paper, we study the voter model on temporal graphs with fixed vertex degrees in the non-adaptive setting. We define a novel parameter Φ(G) of temporal conductance 2

which measures the connectivity of such graphs. We generalize the results of [5] and show that with probability at least 1/2 the consensus time is at most O(m/(dmin Φ(G))), and that there are temporal graphs for which this upper bound is asymptotically tight. Further, we generalise the stepwise bound of [5] to an interval-wise boundP— if time interval Ii contains at least one time t such that Gt has conductance at least ϕi , and Ii=0 ϕi ≥ Cm/dmin for some suitable constant C, then we prove absorption with probability 1/2 after I intervals have passed. We prove this bound is asymptotically tight even if instead of requiring maximum conductance at least ϕi over each interval Ii , we require average conductance at least ϕi . In order to prove our results, we perform a drift analysis with a potential function inspired by [5]. Dealing with temporal conductance turns out to pose significant challenges, which we overcome by splitting time into stable intervals (during which the volume of each opinion class remains roughly constant, allowing conductance to be exploited) and unstable intervals (during which the volume of the minority opinion changes significantly, causing rapid decline of the potential even if conductance is poor).

1.1

Related work

Conductance in static graphs. The conductance of a Markov chain was defined by Jerrum and Sinclair [17] in 1988 to prove their seminal result: counting the number of perfect matchings in bipartite graphs admits a randomized polynomial-time approximation scheme. In order to do this, they proved that the conductance is closely tied to the Markov chain’s mixing time, and used this to show that randomly switching between perfect and near-perfect matchings in bipartite graphs is enough to approximately uniformly sample perfect matchings in polynomial time. Sinclair and Jerrum [26] then developed this connection into a general framework for approximate counting and uniform generation, now central to the analysis of MCMC algorithms [21]. Conductance is also equivalent (up to squaring) to the spectral gap of the random walk matrix—a discrete Cheeger inequality established by Alon and Milman [1] and Mihail [24]—linking it to expander graph theory, spectral graph partitioning [3], and the mixing of reversible Markov chains more broadly [19]. Spreading and random walks on dynamic graphs. Random walks and spreading processes on dynamic graphs have been studied in various models. Clementi et al. [7] studied flooding time in the edge-Markovian model—where each edge appears and disappears independently as a two-state Markov chain—and proved near-tight bounds. Giakkoupis, Sauerwald, and Stauffer [14] studied push-pull rumor spreading under adversarial rewiring, allowing degrees to vary by at most a constant factor, andP showed that the protocol broadcasts to all vertices whenever the cumulative conductance satisfies i ϕi = Ω(log n), where ϕi is the conductance at round i. Avin, Koucký, and Lotker [4] showed that an oblivious adversary can force exponential cover time on a simple random walk even when every snapshot is well-connected, but that the lazy random walk achieves polynomial cover and mixing time against any oblivious adversary. Sauerwald and Zanetti [25] proved O(n2 ) mixing and hitting time bounds for random walks on any sequence of d-regular connected graphs via a local expansion argument. Recently, Galanis, Goldberg, and Mifsud [13] studied random walks on dynamic graphs where edges evolve according to Glauber dynamics for the random-cluster model, and prove O(log n) mixing time in the subcritical regime, matching that of a static random regular graph. Absorption time of the voter model. It is well-known (see e.g. [23]) that the voter model on static graphs is dual to a random walk model — the n-opinion case on an n-vertex graph is dual to n independent random walks, one starting on each vertex, with distinct walks coalescing into a single 3

walk on collision. The absorption time of the voter model then corresponds to the time at which only one walk remains. As such, upper bounds on absorption time are often proved in terms of random walks and their properties. For example, Hassin and Peleg prove [15] that in static graphs the absorption time is O(tmeet log n), where tmeet is the expected time for two independent random walks p to meet on the base graph; this was recently [18] sharpened to O(tmeet (1+ tmix /tmeet log n)), where tmix is the mixing time of a single random walk. Meanwhile, Cooper et al. [9] bound the expected absorption time in terms of the second-largest eigenvalue of the random walk’s transition matrix and its stationary distribution. None of these bounds are directly comparable to the O(m/(dmin ϕ)) bound from [5]; see their introduction for a more detailed discussion. There is one other general upper bound on absorption in terms of conductance. In [5], in addition to their main result of expected absorption time O(m/(dmin ϕ )) (the one stated in their abstract), Berenbrink et al. also prove expected absorption time O(n log n/ϕ2 ). This is a strictly weaker result for the important case of regular graphs, but can be stronger for graphs which are far from regular and have high conductance. We do not generalise this result to the non-adaptive setting, and consider it an interesting open question — in [5] the result falls out relatively easily from their main proof, but in our setting this approach breaks. Other notions of temporal conductance. DiTursi, Ghosh, and Bogdanov [11] define a temporal conductance for community detection in dynamic networks by aggregating cut and volume over a time interval with a normalisation factor; their definition is motivated by data-mining considerations and differs from ours. Berenbrink et al. [5] and Giakkoupis et al. [14] use per-round conductances as input parameters, with bounds in terms of their minimum or cumulative sum. Our Φ(G) instead optimises the window length automatically, yielding a single intrinsic parameter of the temporal graph.

1.2

The voter model on temporal graphs

As discussed earlier, the dynamic networks we consider in this paper are temporal graphs with fixed degrees, which are arbitrary sequences of graphs on a common vertex set, with the only restriction being that the degree of each vertex does not depend on time. The fixed degree assumption makes stochastic processes on the temporal graph much more well-behaved; for example, the lazy random walk becomes strongly ergodic and has a unique stationary distribution. The same assumption was also made by Berenbrink et al. [5], because without it, the expected consensus time can be exponential in the number of vertices [5, Observation 1]. We give a formal definition next. Definition 1.1 (Temporal graph with fixed degrees). Let G be a sequence (Gt : t ≥ 0) of undirected graphs on a common vertex set V (G), where Gt is the graph at time t. We say G is a temporal graph with fixed degrees if the degree of each vertex v ∈ V (G) in Gt does not depend on t. We denote P this common degree by d(v), and the (time-independent) number of edges of G by m, so that 1 m = 2 v∈V (G) d(v) holds. For convenience, we assume d(v) ≥ 1 for all v ∈ V (G), that is, there are no isolated vertices in G. We remark that the degree of each vertex is fixed across time, but not necessarily constant, that is, the degree of a vertex may depend on the number n of vertices but not on t. In the voter model, each vertex holds an opinion and repeatedly copies the opinion of a randomly chosen neighbour in the current graph; the temporal graph thus governs which interactions are available at each time step.

4

Definition 1.2 (Standard voter model). Let G = (Gt : t ≥ 0) be a temporal graph, let κ be a positive integer, and let σ0 : V (G) → {0, . . . , κ − 1}. The standard κ-opinion voter model on G is a stochastic process (ξt : t ≥ 0), where ξt : V (G) → {0, . . . , κ − 1} is a random function that assigns an opinion to each vertex at time t, and ξ0 = σ0 holds deterministically for the initial state. At each time step t, we sample ξt+1 (v) as follows: every vertex v ∈ V (G) independently and synchronously chooses a neighbour w in Gt uniformly at random, and adopts the opinion ξt (w) with probability 1/2; otherwise, v keeps its current opinion ξt (v). This process continues until all vertices share the same opinion, which is called consensus. The consensus time is the first time t such that ξt is a constant function. Note that (ξt : t ≥ 0) is a time-inhomogeneous Markov chain on the state space of all functions V (G) → {0, . . . , κ − 1}, and that the absorbing states are precisely the constant functions. Although our results extend to arbitrary κ, the proof reduces to the two-opinion case, so we mostly focus on κ = 2. In this setting, we write At for the set ξt−1 (0) of vertices with opinion 0 at time t, and we write At := V (G) \ At for the complement. Consensus is reached when At = ∅ or At = V (G) holds.

1.3

Temporal conductance

Before introducing a temporal analogue of conductance, we begin by recalling the standard definition of conductance for a static graph. For a graph G with m edges and a vertex set S ⊆ V (G), we define the volume of S and the conductance of G, via Vol(S) :=

X

ϕ(G) :=

d(v) ,

min S⊆V (G) 0<Vol(S)≤m

v∈S

eG (S, S) . Vol(S)

(1)

Here Vol(S) counts each internal edge of S twice and each edge between S and S once, so it measures the edge mass incident to S; and eG (S, S) denotes the number of edges of G crossing the cut. We remark that m = 12 Vol(V (G)) holds, so the condition Vol(S) ≤ m is equivalent to Vol(S) ≤ 21 Vol(V (G)). Among other things, the conductance determines how fast opinions can propagate across the cut in the voter model. Now let G = (Gt : t ≥ 0) be a temporal graph with fixed degrees. The volume of a set S ⊆ V (G) is time-invariant, but the edges crossing a cut are not. For disjoint subsets S, N ⊆ V (G), we write et (S, N ) for the number of edges of Gt between S and N , and we abbreviate et (v, N ) := et ({v}, N ) for a single vertex v. The conductance of the set S at time t is: ϕt (S) :=

et (S, S) . Vol(S)

(2)

The conductance of G on an integer interval [a, b] ⊆ N is defined by ϕ[a,b] (G) :=

min

S⊆V 0<Vol(S)≤m

ϕ[a,b] (S)

where

ϕ[a,b] (S) := max ϕt (S) . a≤t≤b

(3)

For a = b = t, we have ϕ[a,b] (G) = ϕ(Gt ). What ϕ[a,b] (S) captures for a < b is the best conductance of S across the interval [a, b]: Indeed ϕ[a,b] (S) ≥ ϕ holds if and only if S has conductance ϕt (S) ≥ ϕ for at least one t ∈ [a, b]. Moreover, ϕ[a,b] (G) ≥ ϕ means that every set S with 0 < Vol(S) ≤ m has conductance ϕt (S) ≥ ϕ for at least one t ∈ [a, b]. Note already here that ϕ[a,b] (G) can be large even if ϕ(Gt ) = 0 holds for all t ∈ [a, b]. 5

Then for any ∆ ≥ 1, we define the ∆-window conductance of G by ϕ∆ (G) := min ϕ[t,t+∆−1] (G). t∈N

(4)

Now ϕ∆ (G) ≥ ϕ means that, for every time interval of length ∆, every set S with 0 < Vol(S) ≤ m has at least one “good step”, that is, it has conductance at least ϕ in at least one graph Gt in that interval. Since ϕ∆ (G) ≤ 1 holds for all ∆, we have ϕ∆ (G)/∆ → 0 as ∆ → ∞, so the supremum of ∆ 7→ ∆ ϕ (G)/∆ is attained at some positive integer ∆∗ . We can therefore define the conductance Φ(G) of the temporal graph G via ϕ∆ (G) . ∆≥1 ∆

Φ(G) := max

(5)

If the temporal graph is static, that is, if we have G1 = G2 = · · · = G, then ∆∗ = 1 and thus Φ(G) = ϕ(G), so the definitions coincide. The motivation for dividing by ∆ in (5) is that the one “good step” in the length-∆ interval may be all we get before S has been changed beyond recognition, and so we must amortise its effect over the entire interval length. At first this may seem like a very pessimistic assumption — however, in the next section we provide a matching lower bound even in the case where we have lower bounds on the average conductance within an interval (rather than the maximum), and so we argue that it is justified. Example. Recall our example from earlier — suppose G = (M1 , M2 , . . . ), where each Mi is a perfect matching drawn independently and uniformly at random. Then with high probability over the Mi ’s, Φ(G) ≥ ϕ3 (G)/3 = Ω(1), even though ϕ(Gt ) = 0 for all t. Effectively, for Φ∆ (G) to be high, we require that every set S will be well-cut by some graph in a length-∆ window, but this “good step” may differ within the window from one set to the next.

1.4

Our Model and Results

We prove bounds on the expected consensus time for the standard voter model in a temporal undirected graph whose vertex degrees are fixed by using our notion of temporal conductance. Main Theorem 1 (Upper bound). There exists a constant b′ > 0 such that the following holds. Consider the standard voter model on an n-vertex temporal graph G with fixed vertex degrees, m edges, and minimum degree dmin , with arbitrary initial state. Then with probability at least 1/2, the consensus time is at most b′ m/(dmin Φ(G)). Main Theorem 1 is our simple bound advertised in the introduction. It is a consequence of the following more general statement, which works with an arbitrary partition of time into windows of lengths ∆0 , ∆1 , . . . and the conductance ϕIj (G) attained on each window. One recovers Main Theorem 1 by choosing the windows that realise Φ(G). Theorem 1.3 (Upper Bound). There exists a constant b > 0 such that the following holds. Consider the standard voter model on a temporal graph G with fixed vertex degrees, m edges, and minimum degree dmin , with arbitrary initial state. Let ∆0 , ∆1 , · · · ≥ 1 be integers, and let ϕ0 , ϕ1 , . . . be real numbers in [0, 1]. For all j ≥ 0, let Ij− = ∆0 + · · · + ∆j−1 , let Ij+ = Ij− + ∆j − 1, and let Pj Ij = [Ij− , Ij+ ]. Suppose that for all j ≥ 0, ϕIj (G) ≥ ϕj . Let J = min{j : ℓ=0 ϕℓ ≥ bm/dmin } (where we require J < ∞). Then with probability at least 1/2, the consensus time is at most ∆0 + · · · + ∆J .

6

These upper bounds are essentially tight: the dependence on Φ(G) cannot be improved in general, as our matching lower bounds show. Main Theorem 2 (Lower bound). There exist arbitrarily large n-vertex 3-regular temporal graphs G, and constant c with the following property. From some initial state, with probability at least 1/2, the standard voter model running on G does not absorb within time cn/Φ(G). The construction behind Main Theorem 2 in fact yields a stronger obstruction: it rules out fast consensus even against a weaker, window-averaged notion of conductance, and for every odd degree d. Theorem 1.4 (Lower bound). There exist c > 0, ϕ : N → R and ∆ : N → N with ϕ(n) = Θ(1/n) and ∆(n) = Θ(n) as n → ∞ such that the following holds. For all odd integers d, there exist arbitrarily large n-vertex d-regular temporal graphs G such that: (i) ForPall time intervals I of length ∆(n) and all sets S ⊆ V (G) with 0 < Vol(S) ≤ m, we have 1 t t∈I ϕ (S) ≥ ϕ(n). |I| (ii) From some initial state, with probability at least 1/2, the standard voter model on G does not absorb within time cn∆(n)/ϕ(n). These results should be read against those of [5]. All their results are proved in the same adversarial model: the adversary is allowed to rewire the entire graph at each time step subject to fixed vertex degrees, and the results apply to the total conductance summed over all time steps. Naturally, their main upper bound of [5, Theorem 1.1(i)] transfers immediately to the non-adaptive setting while their main lower bound of [5, Theorem 1.2] breaks in the non-adaptive setting. This important difference aside, [5, Theorem 1.1(i)] is precisely the restriction of Theorem 1.3 to length-1 intervals, while Main Theorem 1 can be read as a restriction of Theorem 1.3 to ϕ0 = ϕ1 = · · · = ϕ and ∆0 = ∆1 = · · · = ∆, with optimised choices of ϕ and ∆. Meanwhile, [5, Theorem 1.2] provides a graph for which the upper bound is tight with interval length 1, while the interval length of Theorem 1.4 is Θ(n); otherwise, they both provide tight lower bounds in their respective settings. Throughout we retain the fixed-degree assumption of [5].

1.5

Proof sketches

We now sketch the proofs of our two main results. Section 1.5.1 treats the upper bound (Main Theorem 1 and Theorem 1.3): a drift analysis of a Lyapunov potential that generalises the argument of Berenbrink et al. [5] by splitting time into stable and unstable intervals. Section 1.5.2 treats the lower bound (Main Theorem 2 and Theorem 1.4), constructing temporal graphs on which the voter model is slow to reach consensus and explaining why the upper bound remains tight even when the conductance is averaged over each window rather than maximised. 1.5.1

Upper bound

Let G be an n-vertex m-edge temporal graph with fixed vertex degrees and minimum degree dmin . For simplicity, fix ϕ and ∆, divide time into intervals I0 , I1 , . . . of length ∆, and suppose that ϕIℓ (G) ≥ ϕ for all ℓ ≥ 0. Then our goal is to prove that with probability at least 1/2, the standard voter model reaches consensus within time O(m∆/(dmin ϕ)). (Theorem 1.3 allows for arbitrary interval lengths and conductance bounds, but this does not substantially affect the argument.) Again for simplicity, we take only κ = 2 opinions; with some effort the argument of Berenbrink et

7

al. [5] to bootstrap from two opinions to arbitrarily many can be adapted to our setting, so this is the heart of the proof. We first review the ∆ = 1 case treated in [5], which is based on a drift analysis of a Lyapunov potential. (This is a standard method — given a system (Xt : t ≥ 0) with state space Σ, filtration (Ft : t ≥ 0), and a potential function f : Σ → R, the drift at time t refers to E(f (Xt+1 )−f (Xt ) | Ft ). See e.g. [20] for an overview.) Recall from Definition 1.2 that (At : t ≥ 0) is the evolution of the set of vertices with opinion 0 in the two-opinion voter model. In analysing the process, it is convenient to instead follow the minority set St at time t defined via ( At if Vol(At ) ≤ Vol(At ); St := At otherwise. This trades the two absorbing states of (At : t ≥ 0), ∅ and V (G), for a single absorbing state at ∅. Note the minority set is chosen based on Vol(At ), not |At |,pfor reasons we explain shortly. The potential function used in [5] is given by ψ(St ) := Vol(St ). This is motivated by the fact that (Vol(At ) : t ≥ 0) is a martingale absorbing at 0 and Vol(V (G)). Since we define St in terms of volume rather than size, it is not hard to show that (Vol(St ) : t ≥ 0) is a supermartingale absorbing at 0, and this is the reason for the definition. The square root is then a simple concave function which turns a mostly-neutral drift into a negative one; this is quantified in [5, Lemma 2.1], which implies dmin et (st , st ) dmin ϕt (st ) dmin ϕ E[ψ(St+1 ) − ψ(st ) | St = st ] ≤ − = − ≤− √ . 3 32ψ(st ) 32ψ(st ) 32 m √ (Here the last inequality follows since Vol(st ) ≤ Vol(V (G))/2 = m.) Since ψ(S0 ) ≤ m and √ at each step we have expected drift −Ω(dmin ϕ/ m), we should therefore expect absorption in √ √ O( m/(dmin ϕ/ m)) = Θ(m/(dmin ϕ)) time, and it is not hard to make this bound rigorous using standard martingale methods. The difficulty of extending this proof to our setting lies in a subtle but important point. If we could guarantee that for all i ≥ 0, there existed t ∈ Ii such that ϕt (St ) ≥ ϕ, then we would be able √ to use essentially the same argument as in [5]: we would accrue ϕ/ m negative drift from our “one good step” of t ∈ Ii , and at worst accrue no negative drift from the remaining steps in Ii . However, this is not the case. Writing Ii− for the start of interval Ii , we can only guarantee that there exists t ∈ Ii such that ϕt (SI − ) ≥ ϕ; t and Ii− may be far apart and St may be very different from SI − , i i so this is not sufficient. This is not merely a technical difficulty — we will see in Section 1.5.2 that this situation is the P reason why our upper bound is tight even given a lower bound on the average conductances |I1i | t∈Ii ϕt (S) rather than simply the maximum conductances ϕIi (S). We effectively proceed by a case analysis on each interval Ii , conditioned on the state of the ′ process at Ii− . Let t′ ∈ Ii be the “one good step” we are guaranteed with ϕt (SI − ) ≥ ϕ. Very i informally, our cases are: (i) Neither Vol(St ) nor et (St , St ) is likely to change significantly over t ∈ Ii . (ii) Vol(St ) is not likely to change significantly over t ∈ Ii , but et (St , St ) is likely to change significantly over t ∈ Ii . (iii) Vol(St ) is likely to change significantly over t ∈ Ii . ′

′

In case (i), we have ϕt (St′ ) ≈ ϕt (SI − ) and so we may apply the same analysis as in [5]. In case (ii), i

informally, we will prove that when Pvolume is held roughly constant, e(St , St ) can only be likely to change significantly over t ∈ Ii if t∈Ii e(St , St ) is likely to be large; since volume is held roughly 8

P constant, this implies that t∈Ii ϕt (St ) is likely to be large and we again have significant negative drift. In case (iii), while we may or may not have significant negative drift in ψ(St ), it is at least true that Vol(St ) is likely to change significantly; we might expect that absorption should be likely after relatively few such intervals have passed. In order to make these ideas rigorous, in cases (i) and (ii) we will need deterministic bounds on Vol(St ). To obtain these, rather than working with the intervals I0 , I1 , . . . directly, we define stopping times 0 = T0 , T1 , . . . in Definition 3.2 and work with the intervals [Ti , Ti+1 ). By default each stopping time Ti occurs at the start of interval Ii , but it can occur early at time t > Ti−1 if Vol(St ) ∈ / [ 21 Vol(STi−1 ), 32 Vol(STi−1 )]. Thus Vol(St ) is guaranteed to stay near-constant within each interval [Ti , Ti+1 ). Given this formulation, the distinction between cases (i) and (ii) versus case (iii) for a given interval [Ti , Ti+1 ) is whether or not Ti+1 is likely to occur early (i.e. before the start of interval Ii+1 ). We set this out in Definition 3.4, where we define a stable interval [Ti , Ti+1 ) as one with E[|Vol(STi+1 ) − Vol(STi )| | HTi ] < Vol(STi )/8, where Ht generates the filtration of the voter model and is formally defined in Section 2.2. An unstable interval is one for which this does not hold. By Markov’s inequality we see that Ti+1 is unlikely to occur early in a stable interval, as will be required for cases (i) and (ii); for case (iii) in an unstable interval, while the lower bound on expected change in volume is technically weaker than a probabilistic bound, it will turn out to be more natural to work with. We perform a drift analysis on stable intervals with respect to ψ in Section 3.1. Our key result in both cases is Corollary 3.6, which exploits the fact that Vol(St ) cannot change significantly over Ii to bound the backward drift of ψ in terms of h Ti+1 i X−1 := µ E et (St , St ) | HTi . t=Ti

In order for Corollary 3.6 to give meaningful negative drift in ψ, we will need to bound µ below. ′ Recall that by our hypothesis, we are guaranteed “one good step” t′ ∈ Ii for which ϕt (STi ) ≥ ϕ. We bound µ below in Lemma 3.7 via a case distinction on ′ i+1 ,t }−1 h min{TX i µ := E et (St , St ) | HTi .

′

t=Ti

If µ′ is small, then via Lemma 2.8 it can be shown that we are in case (i) — that is, in expectation ′ et′ (St′ , St′ ) ≈ et′ (St , St ) and hence ϕt (St′ ) ⪆ ϕ. (This should match our intuition — if et (St , St ) is small for some t, then we should expect St+1 to be close to St and hence et′ (St+1 , St+1 ) ≈ et′ (St , St ).) We can use this to bound µ below at the t′ term. If instead µ′ is large, then we are in case (ii), and we can bound µ below directly by µ′ . Combining Corollary 3.6 and Lemma 3.7 yields Lemma 3.8, which √ implies that (ψ(STi ) : i ≥ 0) is a supermartingale with drift −Ω(dmin ϕ/ m) whenever [Ti , Ti+1 ) is stable. Having finished with cases (i) and (ii), we next analyse case (iii) (when the interval [Ti , Ti+1 ) is unstable) in Section 3.2. Here we forego an analysis of ψ in favour of a different potential function. Intuitively, if every interval [Ti , Ti+1 ) were unstable, then on average we should expect each Vol(STi+1 ) to differ from Vol(STi ) by at least a constant factor, giving rise to something like a simple random walk on {0, . . . , log(2m)}. We are able to make this idea rigorous by analysing the drift of the potential function χ(St ) := log(1 + Vol(St )). We do so first in a generic setting 9

(Lemma 3.9) before proving in Corollary 3.11 that (χ(STi ) : i ≥ 0) is a supermartingale which has drift −Ω(1) whenever [Ti , Ti+1 ) is an unstable interval. It now remains to combine the stable case with the unstable case, which we do in Section 3.3. Thankfully, we proved that both (ψ(STi ) : i ≥ 0) and (χ(STi ) : i ≥ 0) are supermartingales regardless of which intervals are stable or unstable. As such we can simply normalise and add our two potentials to obtain a final supermartingale √ m Ψi := ψ(STi ) + χ(STi ). dmin When [Ti , Ti+1 ) is stable, Ψ has −Ω(ϕ) drift from ψ, and when [Ti , Ti+1 ) is unstable it has −Ω(1) drift from χ; thus in both cases Ψ has −Ω(ϕ) drift. Since Ψi = (m/dmin ) for all i, applying the optional stopping theorem in the usual way then yields our two-opinion result of Theorem 3.1. We can then bootstrap to our final κ-opinion result in a similar fashion to [5]. (Strictly speaking this requires a bound on absorption time in terms of S0 rather than m, but this does not require significant changes to the proof sketch.) 1.5.2

Lower bound

Let n ≥ 4 be an even integer, and let T ≥ log2 n be an integer. We sketch the construction of a 1-regular n-vertex temporal graph G with ϕ(G) = Ω(1/(nT )), average (static) conductance Ω(1/n) on all intervals of length 3T , and upon which the standard two-opinion voter model may take Ω(T n2 ) time to absorb. This suffices to prove Theorem 1.4 for d = 1, as well as Main Theorem 2 in general. We will then explain how to adapt the construction to other vertex degrees. Let V (G) = [n]. For all i ≥ 0, let Ii = [iT, (i + 1)T − 1]. For all t ∈ I1 ∪ I3 ∪ . . . , let the edge set of Gt be {{1, 2}, {3, 4}, . . . , {n − 1, n}}. For all t ∈ I0 ∪ I2 ∪ . . . , let the edge set of Gt be {{2, 3}, {4, 5} . . . , {n − 2, n − 1}, {n, 1}}. Thus G alternates with period T between the two perfect matchings of an n-vertex cycle; in particular, G is 1-regular as required. We next bound the conductance of G below. Fix S ⊆ V (G) with 0 < Vol(S) ≤ 21 Vol(V (G)) = n/2. Observe that since S ∈ / {∅, V (G)}, S must send out at least one edge throughout either odd or even intervals Ii (or both); suppose without loss of generality that et (S, S) ≥ 1 for all t ∈ Ii with i odd. Then any interval I of length 3T must contain at least one such Ii , and so 1 X t 1 |Ii | 2 1 X t 1 X 1 ϕ (S) ≥ ϕ (S) ≥ ≥ · = . 3T 3T 3T Vol(S) 3T n/2 3n t∈I

t∈Ii

t∈Ii

Thus the required lower bound on average static conductance holds. Moreover, by a similar argument, every length-(T + 1) interval contains at least one step t with ϕt (S) ≥ 2/n, so Φ(G) = Ω(1/(nT )). While not necessary for the proof, it is not hard to show that Φ(G) = O(1/(nT )) also by considering sets S of the form {1, . . . , k} with k = Θ(n) even. Finally, we prove that the standard two-opinion voter model may take Ω(T n2 ) time to absorb. Suppose the initial opinion-0 set is of the form {2, . . . , k} with k = Θ(n) even. Then throughout I0 , the only opinions which can change are those of k and k + 1. Recall that the standard voter model is synchronous and lazy, so at each time step one vertex takes the other’s opinion with probability 1/2; otherwise, either they exchange opinions (with probability 1/4) or do nothing (with probability 1/4). Since |I0 | = T ≥ log2 n, with probability 1 − n−ω(1) , at the end of I0 , k and k + 1 will share the same opinion and the new opinion-0 state will be either {2, . . . , k − 1} or {2, . . . , k + 1}. The process continues to evolve in this manner: with high probability, over the course of each interval Ii , the opinion-0 set changes from one contiguous interval to another, with each endpoint shifting 10

by at most 1 in an unbiased fashion. It is not hard to prove (e.g. using Azuma’s inequality) that with probability at least 1/2, such a system does not absorb until Ω(n2 ) intervals Ii have passed, i.e. Ω(T n2 ) total time. For the more general construction (for arbitrary odd vertex degrees), we blow up each vertex i into a set Vi of size (d − 1)/2 and replace each matching edge {i, i + 1} (modulo n) with a clique on Vi ∪ Vi+1 , obtaining an nd-vertex graph. This construction is defined as G T,k,z in Definition 4.1. The bounds on conductance and absorption time follow by analogous arguments to the d = 1 case in Lemmas 4.4 and 4.6 respectively, and the fundamental behaviour of the construction is similar (with the opinion-0 state being of the form Vi ∪ Vi+1 ∪ · · · ∪ Vj with high probability at the start of every interval).

2

Preliminaries

In this section we introduce the notation, basic definitions and well-known probability results relevant to prove our main theorems. Throughout the paper, upper-case letters such as At denote random variables taking values in subsets of V (G), whereas lower-case letters such as at denote fixed subsets of V (G). We also use the notation a ∧ b := min{a, b} and a ∨ b := max{a, b}. We use log to denote the natural logarithm.

2.1

General Lemmas

Below we state two classical results that will be used repeatedly throughout the paper. Lemma 2.1 (Optional stopping theorem). Let (Xt : t ≥ 0) be a supermartingale with some filtration (Ft : t ≥ 0). Let τ be a stopping time for (Xt : t ≥ 0), suppose that τ is almost surely finite, and let t ≥ 0. Then E(Xτ | Ft ) ≤ Xt . Lemma 2.2 (Azuma’s inequality for martingales). Let (Yt : t ≥ 0) be a martingale w.r.t the filtration (Ft : t ≥ 0). Let n ∈ N and suppose there exist constants c1 , . . . , cn ≥ 0 such that |Yi −Yi−1 | ≤ ci holds almost surely for every i ∈ {1, . . . , n}. Then, for every T ≥ 0, we have:   T2 P[|Yn − Y0 | ≥ T ] ≤ 2 exp − Pn 2 . 2 i=1 ci

2.2

Martingale properties of the volume process

We now show that (Vol(At ) : t ≥ 0) is a martingale and (Vol(St ) : t ≥ 0) is a supermartingale with respect to the standard filtration of the voter model on G, which is defined as follows. Definition 2.3 (Filtration). We define the filtration of the standard voter model as (σ(Ht ) : t ≥ 0) where Ht = (A0 , A1 , . . . , At ) is the random variable that holds the entire history of the process so far and σ(Ht ) is the σ-algebra generated by Ht . A sequence (Xt : t ∈ N) of random variables is a martingale under a filtration (Ft : t ∈ N) if for all t ∈ N, we have E[Xt ] < ∞ and E[Xt+1 | Ft ] = Xt . The sequence is a sub-martingale if instead E[Xt+1 | Ft ] ≥ Xt holds, and it is a super-martingale if instead E[Xt+1 | Ft ] ≤ Xt holds. In the standard voter model with two opinions competing on a temporal graph whose vertexdegrees are fixed, it is equally likely that a vertex with opinion 1 switches to opinion 0 as it is that a vertex with opinion 0 switches to opinion 1. Thus, the evolution of the volume of each opinion is a martingale. 11

Lemma 2.4. Let G be a temporal graph whose vertex-degrees are fixed. Let (At : t ≥ 0) be the evolution of the opinion-0 set in the standard voter model on G. Then, (Vol(At ) : t ≥ 0) and (Vol(At ) : t ≥ 0) are martingales under the filtration (σ(Ht ) : t ≥ 0). Proof. We only show that (Vol(At ) : t ≥ 0) is a martingale; the proof for (Vol(At ) : t ≥ 0) is then immediate. We have to show E[Vol(At+1 ) − Vol(At ) | Ht ] = 0. Note that At and thus Vol(At ) is fully determined by the history Ht , but the randomness used to generate At+1 from At (that is, one synchronous update step of the voter process) is independent from Ht . From the definition of the standard voter model, we thus have   E Vol(At+1 ) − Vol(At ) Ht i h X X d(v) Ht d(v) − =E v∈At+1 \At

=

X

v∈At \At+1

P(v ∈ At+1 | Ht )d(v) −

P(v ∈ At+1 | Ht )d(v)

v∈At

v∈At

=

X

X et (v, At ) 2d(v)

d(v) −

X et (v, At )

2d(v) v∈At
= 12 · et (At , At ) − et (At , At ) = 0.

d(v)

v∈At

The ultimate equality holds because the graph is undirected, which concludes the proof. We now state the standard fact that the minimum of two martingales is a supermartingale. Lemma 2.5. Let (Mt : t ≥ 0) and (Nt : t ≥ 0) be two discrete-time martingales with respect to the same filtration (Ft : t ≥ 0). Then (Xt : t ≥ 0) defined via Xt := min{Mt , Nt } is a supermartingale with respect to (Ft : t ≥ 0). Proof. Since Mt and Nt are Ft -measurable, Xt is Ft -measurable. Moreover, for any t ≥ 0, E[|Mt |] < ∞ and E[|Nt |] < ∞ then E[Xt ] < ∞. Since E[Mt+1 ∧ Nt+1 | Ft ] ≤ E[Mt+1 | Ft ] and likewise for Nt+1 , we have   E Mt+1 ∧ Nt+1 Ft ≤ E[Mt+1 | Ft ] ∧ E[Nt+1 | Ft ]. Since Mt and Nt are martingales, it follows that E[Mt+1 ∧ Nt+1 | Ft ] ≤ Mt ∧ Nt . The result follows. We recall the definition of the minority set from Section 1.5.1. Definition 2.6. Let G be a temporal graph whose vertex-degrees are fixed. Let (At : t ≥ 0) be the evolution of the opinion-0 set in the standard voter model on G. The minority set St at time t is given by ( At if Vol(At ) ≤ Vol(At ); St := At otherwise. Using the previous two lemmas, we show that the evolution of the volume of the minority set is a supermartingale. 12

Corollary 2.7. Let G be a temporal graph whose vertex-degrees are fixed. Let (St : t ≥ 0) be the evolution of the minority set at time t in the standard voter model on G with κ = 2. Then, (Vol(St ) : t ≥ 0) is a supermartingale with respect to (σ(Ht ) : t ≥ 0). Proof. Let At ⊆ V (G) be the set of vertices with opinion 0 at time t and At the set of vertices with opinion 1 at time t. By Lemma 2.4, we have that both Vol(At ) and Vol(At ) are martingales with respect to (σ(Ht ) : t ≥ 0). Observe that Vol(St ) = min{Vol(At ), Vol(At )}, then by Lemma 2.5, Vol(St ) is a supermartingale with respect to (σ(Ht ) : t ≥ 0).

2.3

Edges Crossing the Cut

The following lemma focus on the change in the number of edges between a given set and its complement, in particular, it establishes a bound for the stepwise variation. Lemma 2.8. Suppose that G is a temporal graph whose vertex-degrees are fixed. Let (St : t ≥ 0) be the evolution of the minority set in the standard voter model on G with κ = 2. For any t, j ≥ 0, we have h i E et (Sj+1 , Sj+1 ) − et (Sj , Sj ) Hj ≤ ej (Sj , Sj ). Proof. First observe that for all x, y ≥ 0, ex (Sy , Sy ) = ex (Ay , Ay ); thus it suffices to prove i h E et (Aj+1 , Aj+1 ) − et (Aj , Aj ) Hj ≤ ej (Aj , Aj ). Let Aj ⊖ Aj+1 be the symmetric difference of Aj and Aj+1 . Every single vertex v that swaps from Aj to Aj or vice versa removes at most d(v) edges from the cut. This gives a bound of X et (Aj+1 , Aj+1 ) ≥ et (Aj , Aj ) − d(v). v∈Aj ⊖Aj+1

Likewise, every single vertex v that swaps from Aj to Aj or vice versa adds at most d(v) edges to the cut, giving X d(v). et (Aj+1 , Aj+1 ) ≤ et (Aj , Aj ) + v∈Aj ⊖Aj+1

Therefore, the absolute change is bounded as follows, X

|et (Aj+1 , Aj+1 ) − et (Aj , Aj )| ≤

d(v).

v∈Aj ⊖Aj+1

Hence

h E et (Aj+1 , Aj+1 ) − et (Aj , Aj )

i h Hj ≤ E

X v∈Aj ⊖Aj+1

13

i d(v) Hj .

Moreover, h E

X

i X d(v) Hj = P(v ∈ Aj ⊖ Aj+1 | Hj ) · d(v)

v∈Aj ⊖Aj+1

v∈V

=

X

P(v ∈ Aj+1 | Hj ) · d(v) +

v∈Aj

=

P(v ∈ Aj+1 | Hj ) · d(v)

v∈Aj

X ej (v, Aj ) v∈Aj

X

2d(v)

· d(v) +

X ej (v, Aj ) v∈Aj

2d(v)

· d(v)

1 1 = ej (Aj , Aj ) + ej (Aj , Aj ) 2 2 = ej (Aj , Aj ) . This finishes the proof.

3

Proof of the Main Theorem

In this section, our goal is to prove Theorem 1.3. The heart of the proof is the two-opinion case; given this, we will be able to follow the argument of Berenbrink et al. [5] to extend to the general case. Our result is the following, which is essentially the two-opinion case. Theorem 3.1. There exists a constant b > 0 such that the following holds. Consider the standard two-opinion voter model on a temporal graph G with fixed vertex degrees and minimum degree dmin , with arbitrary initial minority set s0 . Let ∆0 , ∆1 , · · · ≥ 1 be integers, and let ϕ0 , ϕ1 , . . . be real numbers in [0, 1]. For all j ≥ 0, let Ij− = ∆0 + · · · + ∆j−1 , let Ij+ = Ij− + ∆j − 1, and let Ij = [Ij− , Ij+ ]. Suppose that for all j ≥ 0, ϕIj (G) ≥ ϕj . Let j o n X  Vol(s ) 0 J = min j : ϕℓ ≥ b + log(1 + Vol(s0 )) , dmin ℓ=0

where we require J < ∞. Then with probability at least 1/2, the consensus time is at most ∆0 + · · · + ∆J . Note that when Vol(s0 ) = Θ(m) in Theorem 3.1, the log(1 + Vol(s0 )) term is dominated by the m/dmin = Θ(n) term. We will prove Theorem 3.1 in Section 3.3, then prove Theorem 1.3 from Theorem 3.1 in Section 3.4. To this end, until the end of Section 3.3, let the following be defined as in the statement of Theorem 3.1: G, dmin , J, and (for all j) ∆j , ϕj , Ij+ , Ij− and Ij . Let S0 ⊆ V be a fixed initial minority set, and let (St : t ≥ 0) be the minority set of a standard voter model running on G from S0 with κ = 2 opinions. We will bound the likely absorption time of (St ) by considering an embedded voter process. One might expect this voter process to consider times I1− , I2− , . . . , but it will be convenient for us to “stop an interval early” if the volume of (St ) deviates significantly from its initial value. As such we define the following sequence of stopping times. Definition 3.2 (Stopping times). Let T0 = 0. Given T0 , . . . , Tj for some j ≥ 0, we define Tj+1 as follows. Let i h  Tjmin := min t ≥ Tj : Vol(St ) ∈ / 12 Vol(STj ), 23 Vol(STj ) or St = ∅ . 14

Then

n o Tj+1 := min Ij+ + 1, Tjmin .

Observe that Tjmin and Tj are indeed stopping times for all j. Definition 3.3 (Embedded voter process). The embedded voter process is the process ((Tj , STj ) : j ≥ 0) where the minority set is sampled only at the stopping times defined in Definition 3.2. Moreover, the embedded volume process is defined by (Vol(STj ) : j ≥ 0). Observe that the embedded voter process is a Markov chain and that the embedded volume process is a supermartingale, from the corresponding properties of the original voter process (together with the optional stopping theorem). (If Tj were not included in the j’th state, however, then the embedded voter process would not be a Markov chain — indeed, the value of each graph Gt on which the voter process runs in [Tj , Tj+1 − 1] depends on t itself, not only on t − Tj ). Recall from Theorem 1.3 that our goal is to prove likely absorption in (St ) within time ∆0 + · · · + ∆J = IJ+ + 1; since TJ ≤ IJ+ + 1, it will suffice to prove likely absorption within time TJ , and we will focus our efforts on the embedded chain from this point forward. We will analyse the embedded chain by splitting the intervals [Tj , Tj+1 − 1] into two kinds depending on whether or not Vol(St ) is likely to fluctuate significantly over t ∈ [Tj , Tj+1 − 1]. Definition 3.4 (Stable and unstable intervals). Let j ∈ N, and let HTj be a possible value of HTj   such that STj ̸= ∅ whenever HTj = HTj . If E |Vol(STj+1 )−Vol(STj )| HTj = HTj < Vol(STj )/8, we say that both HTj and the interval [Tj , Tj+1 ) are stable. Otherwise, we say they are both unstable. We will analyse stable intervals in Section 3.1, then analyse unstable intervals in Section 3.2, then combine the two cases in Section 3.3.

3.1

Stable intervals

In thissection we prove backwards bias in ψ conditioned on HTj = HTj where HTj is stable, so that E |Vol(STj+1 ) − Vol(STj )| HTj = HTj < 81 Vol(STj ). We do this as Lemma 3.8. We first import the following result from [5] which guarantees backward bias at each step of the standard (non-embedded) voter model. Lemma 3.5. Let t ≥ 0, let Ht be a possible value of Ht , and let st be the value of St determined by Ht . Suppose that st ̸= ∅. Then E[ψ(St+1 ) | Ht = Ht ] ≤ ψ(st ) −

dmin et (st , st ) · . 32 ψ(st )3

Proof. We first import some notation from [5]. For a vertex u ∈ st , let λu,t := et (u, st ), and conversely for a vertex u ∈ st let λu,t := et (u, st ). Then [5, Lemma 2.1] says1 that X λu,t d(u) dmin X E[ψ(St+1 ) | St = st ] ≤ ψ(st ) − ≤ ψ(s ) − λu,t . t 32ψ(st )3 32ψ(st )3 u∈St u∈St P Observe that each edge between st and st is counted exactly once in this sum, so u∈V λu,t = et (st , st ). Moreover, by symmetry of opinions, the conditioning on the value of St in this statement is equivalent to conditioning on the value of (At , At ); since the voter model is Markov, this in turn is equivalent to conditioning on the value of Ht , so the result follows. 1

Actually the sum in the statement of [5, Lemma 2.1] is over v ∈ V rather than v ∈ St , a stronger bound, but this appears to be a typo as can be seen by comparing it to the last line of their proof, so we cite the weaker version for safety. There are no wider implications for the correctness of [5], as they bound by the sum over St everywhere they use Lemma 2.1.

15

It is not hard to turn Lemma 3.5 into a bound on the backward bias of ψ(St ) over a whole interval t ∈ [Tj , Tj+1 ), using the fact that Vol(St ) is approximately constant over t ∈ [Tj , Tj+1 ) by the definition of Tj+1 . Corollary 3.6. Let j, tj ≥ 0, and suppose Htj is a possible value of HTj . Let stj be the value of STj determined by Htj . Let h Tj+1 i X−1 µ := E et (St , St ) HTj = Htj . t=tj

Then E[ψ(STj+1 ) − ψ(stj ) | HTj = Htj ] ≤ −

d √ min µ. 24 6ψ(stj )3

Proof. Observe that if stj = ∅ then µ = 0, Tj+1 = tj , and the result is immediate. Therefore suppose for the rest of the proof that stj ̸= ∅. For brevity, let M := E[ψ(STj+1 ) − ψ(stj ) | HTj = Htj ]. Decomposing the sum into time steps, we have i h Tj+1 X−1 M =E (ψ(St+1 ) − ψ(St )) HTj = Htj t=tj Ij+

=

X   E 1t<Tj+1 (ψ(St+1 ) − ψ(St )) HTj = Htj . t=tj

Applying the tower property to expectations over each Ht (subject to the existing conditioning on HTj ) yields +

Ij i h  X  M= E E 1t<Tj+1 (ψ(St+1 ) − ψ(St )) Ht HTj = Htj .

(6)

t=tj

Let Ht be a possible value of Ht extending Htj . If Ht entails t ≥ Tj+1 then E[1t<Tj+1 (ψ(St+1 ) − ψ(St )) | Ht ] = 0. Otherwise, t < Tj+1 ≤ Tjmin , so Ht determines a value st of St with Vol(st ) ∈ [ 21 Vol(stj ), 32 Vol(stj )] and in particular with st ̸= ∅. Thus by Lemma 3.5,   dmin et (st , st ) dmin et (st , st ) E 1t<Tj+1 (ψ(St+1 ) − ψ(St )) Ht = Ht ≤ − · ≤− · . 3 3/2 32 ψ(st ) ψ(stj )3 32(3/2) √ Observe that 32(3/2)3/2 = 24 6, so combining the two cases yields   dmin et (St , St ) E 1t<Tj+1 (ψ(St+1 ) − ψ(St )) Ht ≤ −1t<Tj+1 √ · . 24 6 ψ(stj )3 Substituting back into (6) then gives I+

M ≤−

j X   E 1t<Tj+1 et (St , St ) HTj = Htj ,

d √ min 24 6ψ(stj )3 t=tj

and so the result follows. 16

PTj+1 −1 In order to apply Corollary 3.6 we will need to bound E[ t=t et (St , St ) | HTj = Htj ] below, j which we do in Lemma 3.7. Informally, the proof will proceed as follows. Write stj for the value of Stj determined by HTj = Htj . Since Ij ⊆ [Tj , Ij+ ], there must be “one good step” t′ ∈ [Tj , Ij+ ] ′ with ϕt (stj ) ≥ ϕj and hence et′ (stj , stj ) ≥ ϕj Vol(stj ). This is promisingly close to a lower bound on et′ (St′ , St′ ), which would give us the required lower bound on the mean assuming t′ < Tj+1 , but not close enough — St′ may be very far from stj . Since [Tj , Tj+1 ) is stable, we expect this to be unlikely, but we must formalise this intuition. We can decompose h Tj+1 i X−1 E et (St , St ) | HTj = Htj ≥ t=tj ′

∧t )−1 h (Tj+1X E et (St , St ) | HTj = Htj ] + E[1t′ <Tj+1 et′ (St′ , St′ ) | HTj = Htj ]. t=tj

If the first term is small, then we will show using Lemma 2.8 that et′ (St′ , St′ ) is close to et′ (stj , stj ), and so the second term must be large. Lemma 3.7. Let j, tj ≥ 0, and suppose Htj is a stable possible value of HTj . Let stj ̸= ∅ be the value of STj determined by HTj = Htj . Then i h Tj+1 X−1 µ := E et (St , St ) HTj = Htj ≥ ϕj Vol(stj )/8.

(7)

t=tj

Proof. Let Htj ∈ HTj be a stable possible value of HTj . By the definition of Tj we know that + tj ≤ Ij−1 + 1 = Ij− . By the hypothesis of Theorem 1.3, ϕIj (G) ≥ ϕj , so there exists t′ ∈ Ij ⊆ [tj , Ij+ ] with et′ (stj , stj ) ≥ ϕj Vol(stj ). Let

′

∧t )−1 h (Tj+1X i µ := E et (St , St ) HTj = Htj . ′

t=tj

It is immediate that µ ≥ µ′ , so if µ′ ≥ ϕj Vol(stj )/8 then (7) holds and we are done. For the rest of the proof, suppose instead µ′ < ϕj Vol(stj )/8. We will bound µ by its term at t = t′ . Observe that I+

j X     µ= E 1t<Tj+1 et (St , St ) HTj = Htj ≥ E 1t′ <Tj+1 et′ (St′ , St′ ) | HTj = Htj .

t=tj

Let E be the event that Tj+1 > t′ and et′ (St′ , St′ ) ≥ ϕj Vol(stj )/4. Then it follows that µ ≥ P(E | HTj = Htj ) · ϕj Vol(stj )/4.

(8)

We break E into two sub-events: E1 , the event that Tj+1 > t′ ; and E2 , the event that et′ (St′ , St′ ) ≥ ϕj Vol(stj )/4. Then


P E | HTj = Htj = 1 − P E1 | HTj = Htj − P E1 ∩ E2 | HTj = Htj . 17

(9)

In order to apply (8), we bound each term of (9) separately, starting with the first. By the definition of Tj+1 ,  {Tj+1 ≤ t′ } ⊆ {Tj+1 ≤ Ij+ } ⊆ |Vol(STj+1 ) − Vol(stj )| ≥ 12 Vol(stj ) . Therefore,
P(E1 | HTj = Htj ) ≤ P |Vol(STj+1 ) − Vol(stj )| ≥ 21 Vol(stj ) HTj = Htj . By Markov’s inequality, it follows that P(E1 | HTj = Htj ) ≤

  E |Vol(STj+1 ) − Vol(stj )| | HTj = Htj 1 2 Vol(stj )

.

Since Htj is stable, E[|Vol(STj+1 ) − Vol(stj )| | HTj = Htj ] ≤ Vol(stj )/8, so P(E1 | HTj = Htj ) ≤ 1/4. For brevity, let p := P(E1 ∩ E2 | HTj = Htj ); then by (9) it follows that P(E | HTj = Htj ) ≥ 3/4 − p .

(10)

We now bound p above. Since E2 and et′ (stj , stj ) ≥ ϕj Vol(stj ) together imply |et′ (St′ , St′ ) − et′ (stj , stj )| ≥ 34 ϕj Vol(stj ),    p ≤ P {Tj+1 > t′ } ∩ |et′ (St′ , St′ ) − et′ (stj , stj )| ≥ 43 ϕj Vol(stj ) HTj = Htj   = P 1Tj+1 >t′ · |et′ (St′ , St′ ) − et′ (stj , stj )| ≥ 34 ϕj Vol(stj ) HTj = Htj . By Markov’s inequality, letting h i ν := E 1Tj+1 >t′ |et′ (St′ , St′ ) − et′ (stj , stj )| HTj = Htj , it follows that ν . 4 ϕj Vol(stj )

p≤ 3

(11)

We next bound ν above. By the triangle inequality applied to a telescoping sum, ′ −1 tX h i ν ≤ E 1Tj+1 >t′ |et′ (St+1 , St+1 ) − et′ (St , St )| HTj = Htj .

t=tj

By the tower property, taking expectations over Ht subject to our existing conditioning on HTj , it follows that ν≤

′ −1 tX

i h   E E 1Tj+1 >t · |et′ (St+1 , St+1 ) − et′ (St , St )| Ht HTj = Htj

t=tj

=

′ −1 tX

h i   E 1Tj+1 >t · E |et′ (St+1 , St+1 ) − et′ (St , St )| Ht HTj = Htj .

t=tj

18

By Lemma 2.8 applied with that lemma’s j and t equal to our t and t′ , respectively, it follows that ν≤

′ −1 tX

  E 1Tj+1 >t · et (St , St ) HTj = Htj

t=tj ′

∧t )−1 h (Tj+1X i =E et (St , St ) HTj = Htj = µ′ ≤ ϕj Vol(stj )/8 . t=tj

Plugging this bound on ν into (11), we obtain p ≤ 1/6. By (10) it follows that P(E | HTj = Htj ) > 1/2, so the result follows from (8). We now prove the main result of the subsection. Lemma 3.8. Let j, tj ≥ 0, and suppose Htj is a possible value of HTj . Let stj be the value of STj determined by HTj = Htj . Then   E ψ(STj+1 ) − ψ(stj ) HTj = Htj ≤ 0. If in addition stj ̸= ∅ and Htj is stable, then   dmin ϕj E ψ(STj+1 ) − ψ(stj ) HTj = Htj ≤ − . 500ψ(stj ) Proof. By Corollary 3.6, taking h Tj+1 i X−1 µ := E et (St , St ) HTj = Htj , t=tj

we have   E ψ(STj+1 ) − ψ(stj ) HTj = Htj ≤ −

d √ min µ. 24 6ψ(stj )3

Since µ ≥ 0, the first part of the result follows. If stj ̸= ∅ and Htj is stable, then by Lemma 3.7 it further follows that   dmin ϕj Vol(stj ) dmin ϕj √ √ E ψ(STj+1 ) − ψ(stj ) HTj = Htj ≤ − =− , 3 8 · 24 6ψ(stj ) 192 6ψ(stj ) as required.

3.2

Case 2: Unstable Intervals

Lemma 3.9. Suppose that (Xt ) is a non-negative integer-valued supermartingale with filtration (σ(Ft ) : t ≥ 0) and initial state x0 := X0 . Fix t ≥ 0, let Ft be a possible value of Ft , let xt be the value of Xt determined by Ft , and suppose ξ ≥ 0 satisfies   E |Xt+1 − xt | Ft = Ft ≥ ξxt . Then E[log(1 + Xt+1 ) − log(1 + Xt ) | Ft = Ft ] ≤ −1xt >0 ξ 2 /96. 19

Proof. For brevity, write ζ(x) := log(1 + x) for all x ≥ 0. If xt = 0 then Xt+1 must equal zero (since Xt+1 ≥ 0 and E[Xt+1 | Ft = Ft ] ≤ xt = 0); thus the result holds. We may therefore assume xt > 0, and hence xt ≥ 1, for the rest of the proof. Let ∆t := Xt+1 − xt , and observe that conditioned on Ft = Ft , ζ(Xt+1 ) − ζ(xt ) = log

1 + X

t+1

1 + xt



 = log 1 +

∆t  . 1 + xt

In this expression, ∆t /(1 + xt ) ≥ −xt /(1 + xt ) > −1. By the Taylor expansion, for all z ∈ (−1, 0) we have log(1 + z) ≤ z − z 2 /2 + z 3 /3 ≤ z − z 2 /6; moreover, for all z ≥ 0 we have log(1 + z) ≤ z. Thus taking z := ∆t /(1 + xt ), we obtain ζ(Xt+1 ) − ζ(xt ) = log(1 + z) ≤

∆t 1∆t <0 ∆2t − . 1 + xt 6(1 + xt )2

Since (Xt ) is a supermartingale, we have E[∆t | Ft = Ft ] ≤ 0, so on taking expectations we obtain   E 1∆t <0 ∆2t | Ft = Ft . E[ζ(Xt+1 ) − ζ(xt ) | Ft = Ft ] ≤ − 6(1 + xt )2 Since xt ≥ 1, we have 1 + xt ≤ 2xt ; moreover, for all real variables Z we have E[Z 2 ] ≥ E[Z]2 , and 1∆t <0 ∆2t = (1∆t <0 ∆t )2 . It follows that  2 E 1∆t <0 ∆t | Ft = Ft E[ζ(Xt+1 ) − ζ(xt ) | Ft = Ft ] ≤ − . 24x2t

(12)

We next bound this expectation by splitting ∆t into positive and negative parts. Let ∆+ t := + − + − + − := ∆t ∨ 0 and ∆− −(∆ ∧ 0), so that: ∆ , ∆ ≥ 0; ∆ = ∆ − ∆ ; |∆ | = ∆ + ∆ ; and t t t t t t t t t t − 1∆t <0 ∆t = −∆t . Rewriting (12) in this notation, we obtain  2 E ∆− t | Ft = Ft E[ζ(Xt+1 ) − ζ(xt ) | Ft = Ft ] ≤ − . 24x2t Since (Xt ) is a supermartingale, − E[∆+ t | Ft = Ft ] − E[∆t | Ft = Ft ] = E[∆t | Ft = Ft ] ≤ 0, + and so E[∆− t | Ft = Ft ] ≥ E[∆t | Ft = Ft ]. Thus by hypothesis, − + 1 1 E[∆− t | Ft = Ft ] ≥ 2 E[∆t + ∆t | Ft = Ft ] = 2 E[|∆t | | Ft = Ft ] ≥ ξxt /2.

Plugging this into (13) then yields E[ζ(Xt+1 ) − ζ(xt ) | Ft = Ft ] ≤ −

ξ2 ξ 2 x2t = − . 96 96x2t

as required. Definition 3.10. For all sets S ⊆ V (G), let χ(S) = log(1 + Vol(S)).

20

(13)

Corollary 3.11. Let j, tj ≥ 0, and suppose Htj is a possible value of HTj . Let stj be the value of STj determined by HTj = Htj . Then   E χ(STj+1 ) − χ(stj ) HTj = Htj ≤ 0. If in addition stj ̸= ∅ and Htj is unstable, then   E χ(Vol(STj+1 )) − χ(Vol(stj )) HTj = Htj ≤ −10−4 . Proof. We apply Lemma 3.9, taking (Xj ) to be the embedded volume process Vol(STj ). For the first part of the statement we take ξ = 0, and for the second part we take ξ = 1/8 (which we can do by the definition of an unstable filtration).

3.3

Interplay Between the Two Cases

Theorem 3.1. There exists a constant b > 0 such that the following holds. Consider the standard two-opinion voter model on a temporal graph G with fixed vertex degrees and minimum degree dmin , with arbitrary initial minority set s0 . Let ∆0 , ∆1 , · · · ≥ 1 be integers, and let ϕ0 , ϕ1 , . . . be real numbers in [0, 1]. For all j ≥ 0, let Ij− = ∆0 + · · · + ∆j−1 , let Ij+ = Ij− + ∆j − 1, and let Ij = [Ij− , Ij+ ]. Suppose that for all j ≥ 0, ϕIj (G) ≥ ϕj . Let j n X  Vol(s ) o 0 J = min j : ϕℓ ≥ b + log(1 + Vol(s0 )) , dmin ℓ=0

where we require J < ∞. Then with probability at least 1/2, the consensus time is at most ∆0 + · · · + ∆J . Proof. If s0 = ∅ then the result is immediate, so suppose s0 ̸= ∅. Let τ := min{t ≥ 0 : St = ∅} ∧ TJ , τ ′ := τ ∧ min{t ≥ 0 : Vol(St ) ≥ 8Vol(s0 )}. Let E be the event that either Vol(Sτ ′ ) ≥ 8Vol(s0 ) or τ ′ = TJ and Sτ ′ ̸= ∅. We will first prove that P(Vol(Sτ ′ ) ≥ 8Vol(s0 )) ≤ 1/8, then prove that P(τ ′ = TJ and Sτ ′ ̸= ∅) ≤ 3/8. Given these two facts, the result will follow easily by a union bound. Bounding P(Vol(Sτ ′ ) ≥ 8Vol(s0 )): By Markov’s inequality, P(Vol(Sτ ′ ) ≥ 8Vol(so )) ≤

E[Vol(Sτ ′ )] . 8Vol(s0 )

(14)

Recall that (Vol(St )) is a supermartingale, and τ ′ is a finite stopping time for it. Thus by the optional stopping theorem, E(Vol(Sτ ′ )) ≤ Vol(s0 ). It therefore follows by (14) that P(Vol(Sτ ′ ) ≥ 8Vol(so )) ≤ 1/8,

(15)

as claimed. Bounding P(τ ′ = TJ and Sτ ′ ̸= ∅): We will first establish downward drift of the following potential. For all j ≥ 0, let ψ(s0 ) Ψj := ψ(STj ) + χ(STj ). dmin 21

Temporarily fix j ≥ 0, and suppose Htj is a possible value of HTj . Let stj be the corresponding value of STj determined by Htj . Then we split into three cases, bounding the drift of Ψj in each case. First suppose Htj is stable and determines tj < τ ′ . This implies stj ̸= ∅, so by Lemma 3.8 and Corollary 3.11,   ψ(s0 )   E ψ(STj+1 ) − ψ(stj ) | HTj = Htj + E Ψj+1 − Ψj | HTj = Htj = dmin   E χ(STj+1 ) − χ(stj ) | HTj = Htj ϕj ψ(s0 ) ≤− + 0. 500ψ(stj ) √ Since tj < τ ′ , ψ(stj ) ≤ 8ψ(s0 ), so it follows that   E Ψj+1 − Ψj | HTj = Htj ≤ −ϕj /2000. Similarly, if instead Htj is unstable and determines tj < τ ′ , then stj ̸= ∅, so by Lemma 3.8 and Corollary 3.11,   E Ψj+1 − Ψj | HTj = Htj ≤ 0 − 10−4 = −10−4 . Finally, if instead Htj determines tj ≥ τ ′ , then by Lemma 3.8 and Corollary 3.11,   E Ψj+1 − Ψj | HTj = Htj ≤ 0 + 0 = 0. Thus on combining all three cases, we obtain that for all j ≥ 0,  ϕ    j −4 ′ := E Ψj+1 − Ψj | HTj ≤ −Dj , where Dj 1Tj <τ . ∧ 10 4000

(16)

Let J ′ = min{j ≥ 0 : Tj ≥ τ ′ }. Since s0 ̸= ∅ we have τ ′ > 0, so J ′ > 0 and TJ ′ −1 < τ ′ ≤ TJ ′ . We will next apply the optional stopping theorem a standard way to argue that the total P in ′ −1 Dℓ , is unlikely to be large; we will exploit accumulation of expected drift up to time TJ ′ , i.e. Jℓ=0 ′ this to bound J above, in order to bound TJ ′ above, in order to finally bound τ ′ above. For all j ≥ 0, let j−1 X Xj := Ψj + Dℓ . ℓ=0

By (16), (Xj ) is a supermartingale under the filtration generated by (HTj ); moreover, J ′ is a finite stopping time for (Xj ). Thus by the optional stopping theorem, E[XJ ′ ] ≤ X0 . Expanding out both sides, we obtain ′ −1 h JX i E[ΨJ ′ ] + E Dℓ ≤ Ψ0 . ℓ=0

Since ΨJ ′ ≥ 0, it follows that E[

PJ ′ −1 ℓ=0

Dℓ ] ≤ Ψ0 . Markov’s inequality then yields

′ −1  JX  P Dℓ ≥ 4Ψ0 ≤ 1/4.

(17)

ℓ=0

We will next use (17) to prove P(J ′ ≥ J) ≤ 1/4. For this, it is enough to prove that 4Ψ0 implies J ′ < J; by the definition of J, this is equivalent to proving

PJ ′ −1 ℓ=0

Dℓ <

′

J X ℓ=0

  Vol(s ) 0 ϕℓ < b + log(1 + Vol(s0 )) . dmin 22

(18)

P ′ −1 Dℓ < 4Ψ0 . By the definition of J ′ , for all ℓ < J ′ we have Tℓ < τ ′ ; To this end, suppose that Jℓ=0 thus by the definition of the Dℓ ’s, ′ −1 JX

Dℓ =

ℓ=0

Since

PJ ′ −1 ℓ=0

′ −1 JX 

ℓ=0

J ′ −1

 X ϕℓ ∧ 10−4 ≥ 10−4 ϕℓ . 4000 ℓ=0

Dℓ < 4Ψ0 by assumption, it follows that ′ −1 JX

ϕj < 4 · 104 Ψ0 = 4 · 104

 Vol(s )

ℓ=0

0

dmin

 + log(1 + Vol(s0 )) ;

on taking b ≥ 8 · 104 this implies (18), and hence J ′ < J as required. We have therefore proved P(J ′ ≥ J) ≤ 1/4.

(19)

We now use (19) to prove P(τ ′ = TJ and Sτ ′ ̸= ∅) ≤ 1/4, our original goal. It suffices to prove that whenever τ ′ = TJ and Sτ ′ ̸= ∅ occurs, J ′ ≥ J. By the definition of J ′ , we have TJ ′ ≥ τ ′ = TJ > TJ ′ −1 , where the final inequality follows since Sτ ′ ̸= ∅. This implies J ′ > J − 1 and hence J ′ ≥ J. It is therefore immediate from (19) that P(τ ′ = TJ and Sτ ′ ̸= ∅) ≤ 1/4 < 3/8.

(20)

Putting everything together: Combining (15) and (20) with a union bound, we see that with probability at least 1/2, E does not occur, it follows that either Vol(Sτ ′ ) < 8Vol(so ) or both τ ′ = TJ and Sτ ′ = ∅. In both cases, τ ′ = τ. By the definition of τ , this is equivalent to saying that τ is the − consensus time. Since by the definitions of τ and TJ we have τ ≤ TJ ≤ IJ+ + 1 = IJ+1 , the result follows.

3.4

Deriving the multi-opinion bound from the two-opinion bound

The following argument to derive a multi-opinion bound from a two-opinion bound follows essentially the same method as Berenbrink et al. [5]; however, since the lengths of our “phases” are more complex, Theorem 3.1 has an additive error term not present in the two-opinion result of [5], and the presentation in [5] is quite abbreviated, we give the argument in full detail. Theorem 1.3 (Upper Bound). There exists a constant b > 0 such that the following holds. Consider the standard voter model on a temporal graph G with fixed vertex degrees, m edges, and minimum degree dmin , with arbitrary initial state. Let ∆0 , ∆1 , · · · ≥ 1 be integers, and let ϕ0 , ϕ1 , . . . be real numbers in [0, 1]. For all j ≥ 0, let Ij− = ∆0 + · · · + ∆j−1 , let Ij+ = Ij− + ∆j − 1, and let Pj Ij = [Ij− , Ij+ ]. Suppose that for all j ≥ 0, ϕIj (G) ≥ ϕj . Let J = min{j : ℓ=0 ϕℓ ≥ bm/dmin } (where we require J < ∞). Then with probability at least 1/2, the consensus time is at most ∆0 + · · · + ∆J . Proof. Let κ be the number of opinions present in the model. The result is immediate if κ = 1, so suppose κ ≥ 2. Let B be a large constant, to be determined later. First, we divide time into phases of deterministic length. Let rmax := ⌊Bm/dmin ⌋. Let ℓ0 = t0 = 0, and for all integers r with 1 ≤ r ≤ rmax , let ℓ−1 n X o ℓr := min ℓ : ϕj ≥ r ,

tr := Iℓ−r = ∆0 + · · · + ∆ℓr −1 .

j=0

23

For all r ≥ 0, we call the interval [tr , tr+1 − 1] the r’th phase. Note that since each ϕj lies in [0, 1], we have t0 < t1 < · · · < trmax ≤ ∆0 + · · · + ∆J < ∞. Following [5], we now group these phases into “metaphases” of random lengths. For all t ≥ 0, let O(t) be the set of opinions remaining in the process at time t. Let R0 = 0, and for all α ≥ 1, let    Rα := min {rmax } ∪ r : |O(tr )| ≤ (5/6)α κ ∨ 1 . Then the α’th metaphase is the interval [tRα , tRα+1 − 1]. Thus ignoring the cap at rmax (past which no more phases are defined), before consensus the end of the α’th metaphase occurs after however many phases it takes for the number of opinions to have dropped by a cumulative factor of (5/6)α , and after consensus all metaphases are empty. Let β := ⌈log6/5 κ⌉, and observe that (5/6)β κ ≤ 1. Thus by definition, if Rβ < rmax then |O(tRβ )| = 1 and so the consensus time is at most tRβ < trmax ≤ ∆0 + · · · + ∆J as required. It therefore suffices to prove that P(Rβ < rmax ) ≥ 1/2. (21) Our next goal is to prove that taken individually, each metaphase ends in few phases with probability bounded away from zero. We will prove the following claim, where we begin in the middle of a metaphase to allow for repeated application later. Claim: Let r, α ≥ 0, let Htr be a possible value of Htr , and suppose that Htr = Htr determines Rα ≤ r < Rα+1 . Let rα and Oα be the values of Rα and O(trα ) determined by Htr , and let l  6m
m ξα := 1 + b . + log 1 + 6m/|Oα | dmin |Oα | Then P(Rα+1 > r + ξα | Htr = Htr ) ≤ 2/3. Proof of Claim: If r + ξα ≥ rmax then Rα+1 ≤ rmax ≤ r + ξα with certainty and the Claim holds immediately, so suppose for the rest of the proof that r + ξα < rmax . Thus
P(Rα+1 > r + ξα | Htr = Htr ) = P |O(tr+ξα )| > (5/6)α+1 κ ∨ 1 | Htr = Htr . (22) Next observe that conditioned on Htr = Htr , since rα < Rα+1 , (5/6)α κ ≥ |Oα | > (5/6)α+1 κ ∨ 1.

(23)

Applying (5/6)α κ ≥ |Oα | in (22), it follows that
P(Rα+1 > r + ξα | Htr = Htr ) ≤ P |O(tr+ξα )| ≥ 65 |Oα | | Htr = Htr .

(24)

Henceforth we will be concerned with this event: that at least 5/6 of the original |Oα | opinions present at the start of the r’th phase remain after ξα further phases have elapsed. We next express the right-hand side of (24) in terms of indicator variables. For each opinion q ∈ Oα , let Xq be the indicator variable of the event that q ∈ O(tr+ξα ) and that O(tr+ξα ) ̸= {q} (i.e. that q has neither vanished nor taken over G within ξα phases starting from tr ). Then by (24),   X (25) P(Rα+1 > r + ξα | Htr = Htr ) ≤ P Xq > 65 |Oα | Htr = Htr . q∈Oα

(Indeed, if this sum is at most 56 |Oα | then by time tr+ξα , either some opinion in Oα has taken over or at least |Oα |/6 opinions have vanished; in either case, at least |Oα |/6 opinions have vanished, so |O(tr+ξα )| ≤ 5|Oα |/6 ≤ (5/6)α+1 κ and hence Rα+1 ≤ r + ξα .) 24

We next restrict the sum in (25) to a subset of opinions in Oα with low volume. For all q ∈ Oα , let aq (tr ) be the set of vertices with opinion q at time tr under Htr = Htr . We say that an opinion q ∈ O(tr ) is small if Vol(aq (tr )) ≤ 6m/|Oα |. Let Ot−r be the set of small opinions in O(tr ), and observe that |Ot−r | ≥ |O(tr )| − |Oα |/3; (26) indeed, if this were not the case, then the remaining (at least) |Oα |/3 opinions would have total volume greater than (6m/|Oα |) · (|Oα |/3) = Vol(V (G)) which is not possible. Moreover, if q ∈ Oα \ O(tr ) then q has already died out by time tr and so Xq = 0. Thus X X X Xq + |O(tr ) \ Ot−r |. Xq ≤ Xq = q∈Oα

Thus whenever

P

q∈O(tr )

q∈Ot−r

5 q∈Oα Xq > 6 |Oα |, we have

X

Xq > 56 |Oα | − |O(tr ) \ Ot−r |.

q∈Ot−r

Thus by (25), it follows that P(Rα+1 > r + ξα | Htr = Htr )   X ≤P Xq ≥ 65 |Oα | − |O(tr )| + |Ot−r | Htr = Htr .

(27)

q∈Ot−r

By Markov’s inequality and (27), P P(Rα+1 > r + ξα | Ht = Ht ) ≤

q∈Ot−r P(Xq = 1 | Ht = Ht ) . − 5 6 |Oα | − |O(tr )| + |Otr |

(28)

To bound the right-hand side of (28), fix a small opinion q ∈ Ot−r . We consider a two-opinion standard voter model on the temporal graph Gt′′ := Gt′ −tr , where one opinion is q with initial state aq (tr ); thus the other opinion (q, say) is formed by grouping all vertices with opinions other than q at time tr in G. This model couples to our present κ-opinion voter model in the natural fashion, with opinion q evolving identically between the two models subject to a time offset of tr . Recall that by definition, tr = ∆0 + · · · + ∆ℓr −1 . Let b be as in Theorem 3.1, and let j n X  Vol(a (t ))
o q r J ′ := min j : ϕℓ ≥ b + log 1 + Vol(aq (tr )) ; dmin ℓ=ℓr

then by Theorem 3.1, with probability at least 1/2, opinions q and q achieve consensus in the two-opinion model within time ∆ℓr + · · · + ∆J ′ . We next bound J ′ above. Note that ℓr+ξα −1

X ℓ=ℓr

ℓr+ξα −1

ϕℓ =

X ℓ=0

ϕℓ −

ℓX r −1

ϕℓ .

(29)

ℓ=0

If 0 (so that ℓr > 0), then applying the definitionPof the phases and the fact that ϕℓr −1 ∈ [0, 1], Prℓr > Pℓr −2 −1 ℓr −1 ℓ=0 ϕℓ = ℓ=0 ϕℓ − ϕℓr −1 ≤ r + 1; otherwise, ℓ=0 ϕℓ = 0 < r + 1. In either case, again 25

applying the definition of the phases, it follows from (29) that ℓr+ξα −1

X

l  ϕℓ ≥ (r + ξα ) − r − 1 = ξα − 1 = b

ℓ=ℓr

m 6m + log 1 + 6m/|Oα | . dmin |Oα |

Since opinion q is small, it follows that ℓr+ξα −1

X ℓ=ℓr

 Vol(a (t ))
 q r ϕℓ ≥ b + log 1 + Vol(aq (tr )) , dmin

and hence that J ′ ≤ ℓr+ξα − 1. Thus in our original κ-opinion model, with probability at least 1/2, opinion q either vanishes or takes over by time tr + ∆ℓr + · · · + ∆ℓr+ξα −1 = tr+ξα ; that is, with probability at least 1/2, Xq = 0. We have just shown that for all q ∈ Ot−r , P(Xq = 1 | Htr = Htr ) ≤ 1/2. Substituting this into (28) yields − 1 2 |Otr | P(Rα+1 > r + ξα | Htr = Htr ) ≤ 5 − . 6 |Oα | − |O(tr )| + |Otr | By the assumption of the claim we have r < Rα+1 , so |O(tr )| > (5/6)α+1 κ; by (23) it follows that |O(tr )| > 56 |Oα |. It follows that the right-hand side of the above equation is non-increasing in |Ot−r |. Since |Ot−r | ≥ |O(tr )| − 31 |Oα | by (26), it follows that 1 1 1 (|O(tr )| − 13 |Oα |) 2 2 (|Oα | − 3 |Oα |) P(Rα+1 > r + ξα | Htr = Htr ) ≤ 2 5 ≤ = . 1 1 3 |O | − |O | |O | α α α 6 3 2

We have therefore proved the Claim. Proof of Theorem from Claim: From the start of metaphase α at phase r (say), the Claim applied to α and r, r + ξα , r + 2ξα , . . . implies that the number of times we have to wait ξα phases before the next metaphase is dominated above by a geometric variable with parameter 1/3. Thus the expected number of phases before the next metaphase satisfies  6m  
 E Rα+1 − Rα HtRα ≤ 3ξα ≤ 6b + log 1 + 6m/|Oα | . dmin |Oα | We now bound this expectation above by exposing HtRα . Let Htrα be a possible value of HtRα which entails Rα+1 > rα (or the expectation is zero conditioned on HtRα = Htrα ). Then by the definition of Rα , conditioned on HtRα = Htrα we have (5/6)α+1 κ < |O(trα )| ≤ (5/6)α κ exactly as in (23). Thus by the tower property,    E Rα+1 − Rα ] = E E[Rα+1 − Rα | HtRα ]    6m 6m ≤ 6b . (30) + log 1 + (5/6)α+1 dmin κ (5/6)α+1 κ We now exploit (30) to bound Rβ . Recall our final goal of (21). By Markov’s inequality, P(Rβ ≥ rmax ) ≤

E(Rβ ) , rmax

(31)

where by (30), E(Rβ ) =

β−1 X α=0

β−1

β−1

α=0

α=0

  X 36bm X 1 6m E(Rα+1 − Rα ) ≤ log 1 + + 6b . dmin κ (5/6)α+1 (5/6)α+1 κ 26

Reparameterising the left sum by γ := β − 1 − α and bounding all terms of the right sum uniformly gives β−1

E(Rβ ) ≤

 X 6m  36bm γ (5/6) + 6bβ log 1 + . κdmin (5/6)β (5/6)β κ γ=0

By the definition of β, (5/6)β ≥ (5/6)/κ > 1/(2κ), and so β−1

E(Rβ ) ≤

72bm X (5/6)γ + 6bβ log(1 + 12m). dmin γ=0

P P∞ γ γ Observe that β−1 γ=0 (5/6) < γ=0 (5/6) = 6, β ≤ log6/5 κ+1 ≤ 10 log n (where we use n ≥ κ ≥ 2), and log(1 + 12m) ≤ log(13n2 ) ≤ 10 log n. Thus E(Rβ ) ≤

432bm + 600b log2 n. dmin

Observe that m/dmin ≥ n/2 = ω(log2 n) as n → ∞, so it follows that for a suitable constant B ′ > 0, E(Rβ ) ≤ B ′ m/dmin . Thus by (31), P(Rβ ≥ rmax ) ≤

B ′ m/dmin B ′ m/dmin . = rmax ⌊Bm/dmin ⌋

Take B = 4B ′ . Since no vertex in G is isolated, m/dmin ≥ n/2 ≥ 1, so ⌊Bm/dmin ⌋ ≥ Bm/(2dmin ); thus P(Rβ ≥ rmax ) ≤ 2B ′ /B = 1/2. We therefore obtain our goal of (21), as required. Main Theorem 1 (Upper bound). There exists a constant b′ > 0 such that the following holds. Consider the standard voter model on an n-vertex temporal graph G with fixed vertex degrees, m edges, and minimum degree dmin , with arbitrary initial state. Then with probability at least 1/2, the consensus time is at most b′ m/(dmin Φ(G)). ′

Proof. Let ∆′ be such that ϕ(G) = ϕ∆ (G)/∆′ (recalling that such a ∆′ exists by the definition of ′ ϕ(G)), and let ϕ′ := ϕ∆ (G). Let ∆j = ∆′ , and ϕj = ϕ′ for all j ≥ 0; we will apply Theorem 1.3 to ∆0 , ∆1 , . . . and ϕ0 , ϕ1 , . . . . By the definition of Φ(G), for all j ≥ 0, ϕIj ≥ ϕj = ϕ′ holds. Therefore, by Theorem 1.3, with probability at least 1/2 the consensus time is at most J∆′ with J = ⌈bm/(dmin ϕ′ )⌉ − 1. Thus, with probability at least 1/2 the consensus time is at most J∆′ ≤

bm bm ∆′ = dmin ϕ′ dmin Φ(G)

The result follows by taking b′ = b.

4

Lower Bound on Absorption Time

In this section, we prove Main Theorem 2. In order to do so, we construct a specific temporal graph where consensus is reached only slowly. The idea is to construct a temporal graph G such that with high probability, the opinion-zero set of G sampled at appropriate stopping times is a blown-up contiguous interval on a length-z cycle. The endpoints of this interval sampled at the 27

same stopping times will then evolve independently according to an unbiased random walk with bounded step size; it is then not hard to show that this interval requires Ω(z 2 ) steps to reach the empty interval or the whole cycle, i.e. consensus. Essentially, our temporal graph alternates between G0 and G1 , which are disjoint unions of z/2 cliques on 2k vertices, arranged in a cycle. See Fig. 2 for an illustration. Definition 4.1. Let T, k, z ≥ 1 be integers with z even. Then the temporal graph G T,k,z is defined as follows. Let V (G) be a disjoint union of sets V1 , . . . , Vz of k vertices each. For all i ∈ [z], let Hi be a 2k-vertex clique spanning Vi and Vi+1 (modulo z). Let [ [ Hi . Hi , G1 = G0 = i∈[z] : i is odd

i∈[z] : i is even

For all j ≥ 1, let Ij = {(j − 1)T, . . . , jT − 1}. Then G is the temporal graph which, throughout each time interval Ij , takes value Gj mod 2 . Remark 4.2. Let T, k, z ≥ 1 be integers with z even. Then G T,k,z is (2k − 1)-regular and has n = kz vertices. We first bound the conductance of any interval of size 3T for any possible minority set S ⊆ V (G T,k,z ) below in Lemma 4.4. After that, we bound its absorption time in Lemma 4.6, then choose specific values of T , k and z and derive Main Theorem 2 as an easy consequence.

Figure 2: At even intervals the blue edges are active forming a 2k-vertex clique. At odd intervals the red edges are active forming a 2k-vertex clique. In order to bound the conductance of any interval of size 3T for any half-volume set S ⊆ V (G T,k,z ) below in Lemma 4.4, we will need the following well-known (and trivial) bound. Lemma 4.3. For all k ≥ 1, the complete graph on 2k vertices has conductance greater than 1/2. Proof. Let K2k be the complete graph with 2k vertices. For any set S ⊆ V (K2k ) with 0 < Vol(S) ≤ Vol(K2k )/2, we have 0 < |S| ≤ k, and thus ϕ(S) =

e(S, S) |S| · (2k − |S|) 2k − |S| k 1 = = ≥ > . Vol(S) |S| · (2k − 1) 2k − 1 2k − 1 2

By definition, ϕ(K2k ) = minS ϕ(S) > 1/2. 28

Next, we show that any interval of size 3T has conductance at least T /4z for any minority set S ⊆ V (G T,k,z ). Lemma 4.4. Let T, k, z ≥ 1 be integers with z even. Then for any interval I ⊆ N of length 3T and any set S ⊆ V (G T,k,z ) with 0 < |S| ≤ n/2, we have X

ϕt (S) =

t∈I

X et (S, S) Vol(S)

t∈I

≥ T /4z .

Proof. Throughout, let G = G T,k,z and n = kz = |V (G)|. Let S ⊆ V (G) with 0 < |S| ≤ n/2. Since G is regular, this implies 0 < Vol(S) ≤ 12 Vol(V (G)). We split into two cases depending on S. Case 1: For all x ∈ [z], we have |S ∩ Vx | ≤ k/2. In this case, let t ∈ I be arbitrary, and let C1 , . . . , Cr be the cliques present in G at time t. Then for all i ∈ [r], we have |S ∩ V (Ci )| ≤ k. Thus by Lemma 4.3, r

et (S, S) 1 X ϕ (S) = = e(Vx ∩ V (Ci ), V (Ci ) \ S) Vol(S) Vol(S) t

i=1

≥

r X Vol(S ∩ V (Ci ))

1 Vol(S)

i=1

2

1 = . 2

Thus, since I has length 3T , X et (S, S) t∈I

Vol(S)

≥

3T T > . 2 4z

(32)

P Case 2: There exists x ∈ [z] with |S ∩ Vx | > k/2. Since y∈[z] |S ∩ Vy | = |S| ≤ kz/2, there also exists y ∈ [z] with |S ∩ Vy | ≤ k/2; hence there exists ℓ ∈ [z] with |S ∩ Vℓ | ≤ k/2 and |S ∩ Vℓ+1 | > k/2 (modulo z). Since I is of length 3T and the intervals Ij are of length T , I must contain two successive intervals Ij and Ij+1 ; throughout one of these intervals, say I ′ , the clique C spanned by Vℓ and Vℓ+1 is a component of G. Let S ′ = S ∩ V (C); then for all t ∈ I ′ , we have et (S, S) ≥ et (S ′ , V (C) \ S ′ ). Observe that since |S ∩ Vℓ | ≤ k/2 and |S ∩ Vℓ+1 | > k/2, we have k/2 ≤ |S ′ | ≤ 3k/2. Let X be whichever of S ′ and V (C) \ S ′ has size at most k, so that et (S ′ , V (C) \ S ′ ) = et (X, V (C) \ X); then by Lemma 4.3, it follows that et (S, S) ≥ Vol(X)/2. Again since k/2 ≤ |S ′ | ≤ 3k/2, we have Vol(X) ≥ k(2k − 1)/2, and Vol(S) is at most Vol(V (G)) = n(2k − 1); thus X et (S, S) X k(2k − 1)/4 Tk T ≥ ≥ = . (33) Vol(S) n(2k − 1) 4n 4z ′ t∈I

t∈I

The result now follows immediately on combining (32) from Case 1 and (33) from Case 2. Our next goal is to bound the likely absorption time of the voter model on G T,k,z below in Lemma 4.6. To do so, we first re-prove a (well-known) upper bound on absorption time for the clique; this will allow us to show that within an interval Ij with j odd (say), in every clique component of G1 , the voter model reaches consensus before the end of Ij with high probability.

29

Lemma 4.5. There exists a positive integer Γ such that, for all positive integers k and α, the following holds: From any initial state, with probability at least 1 − 2−α , the standard voter model on the (static) clique on 2k vertices reaches consensus within Γαk time. Proof. By Lemma 4.3, the clique H on 2k vertices has conductance at least 1/2. It follows, for example, from [5, Theorem 1.1(i)] that there exists Γ′ ≥ 1 such that with probability at least 1/2, from any initial state, the standard voter model on H absorbs within time at most Γ′ |V (H)|/ϕ(H) ≤ 4Γ′ k ≤ Γk. We apply this fact α times to obtain the result. Lemma 4.6. There exists Γ ≥ 1 such that the following holds. Let T, k, z ≥ 1 be integers with z even and z ≥ 20, and suppose T ≥ 10Γk log z. Then there exists s0 ⊆ V (G T,k,z ) such that with probability at least 1/2, the standard voter model on G T,k,z with initial minority set s0 does not absorb within time T z 2 /128. Proof. Throughout, let G = G T,k,z . Let Γ be the constant of Lemma 4.5. Let s0 = V1 ∪ · · · ∪ Vz/2 . In the voter model (At ) from initial state s0 , let τ be the earliest time t divisible by T at which At is not precisely a set of the form Vi ∪ Vi+1 ∪ · · · ∪ Vj (modulo z); thus τ is the earliest start of an interval Ij in which the opinions do not form two contiguous intervals in V1 , . . . , Vz . For all i ≥ 0, define ( |{j ∈ [z] : Vj ⊆ AiT }| if iT < τ , Wi = Wi−1 otherwise. Thus W0 = z/2, and if iT < τ and Wi ∈ / {0, z} then AiT ∈ / {∅, V (G)} (and so the voter model has not absorbed by time iT ). Our proof will now proceed in two parts. Let ℓ = ⌈z 2 /128⌉. First, we claim that (Wi ) is a martingale, and so by applying Azuma’s inequality it is likely that Wℓ ∈ / {0, z}. Second, we argue it is likely that τ > ℓT . Put together with a union bound, the two claims will immediately imply the result. Claim 1: With probability at least 7/10, Wℓ ∈ / {0, z}. Let Mi = (A0 , AT , . . . , AiT ). We first establish that (Wi ) is a martingale with filtration σ(Mi ). Fix i ≥ 0, and let Mi be a possible value of Mi . If Mi = Mi determines iT ≥ τ , then E(Wi+1 | Mi = Mi ) = Wi as required, so suppose not. Let aiT be the value of AiT determined by Mi . Throughout the interval Ii+1 , G is constant and either one or two cliques in G contain vertices of both opinions. Moreover, in each such clique, exactly half of the vertices have each opinion in aiT . Thus by symmetry, each opinion is equally likely to dominate in each clique within the interval Ii+1 . It follows that |Wi+1 − Wi | ≤ 2, P(Wi+1 = Wi + 1 | Mi = Mi ) = P(Wi+1 = Wi − 1 | Mi = Mi ), and P(Wi+1 = Wi + 2 | Mi = Mi ) = P(Wi+1 = Wi − 2 | Mi = Mi ). Thus once again, E(Wi+1 | Mi = Mi ) = Wi . We conclude that (Wi ) is indeed a martingale with filtration σ(Mi ). We now apply Azuma’s inequality (Lemma 2.2) to (Wi ), taking ci = 2 for all i and taking the T of Lemma 2.2 to be our z/2. Since z ≥ 20, ℓ = ⌈z 2 /128⌉ ≤ z 2 /64; thus we obtain 2

P(Wℓ ∈ {0, z}) = P(|Wℓ − W0 | ≥ z/2) ≤ 2e−(z/2) /8ℓ ≤ 2/e2 < 3/10.

(34)

Claim 2: With probability at least 4/5, τ > ℓT . We will apply a union bound over all intervals Ij with j ∈ [ℓ]. To this end, fix i ≥ 0, let Mi be a possible value of Mi , and suppose 30

Mi determines iT < τ . Then as in Claim 1, throughout the interval Ii+1 , G is constant and either one or two cliques in G contain vertices of both opinions. By Lemma 4.5 applied with α = ⌈3 log2 z⌉ < 10 log z, each clique absorbs within Ii+1 with probability at least 1−2−α ≥ 1−1/z 3 . Taking a union bound over all (one or two) cliques in Ii+1 with vertices of both opinions, we see that P(τ > (i + 1)T | Mi = Mi ) ≥ 1 − 2/z 3 . Taking a union bound over i ∈ [ℓ], it follows that P(τ ≤ ℓT ) ≤ 2ℓ/z 3 < 1/5.

(35)

The result now follows from a union bound over (34) and (35), together with the fact that if ℓT < τ and Wℓ ∈ / {0, z} then AℓT ∈ / {∅, V (G)}: P(AℓT ∈ {∅, V (G)}) ≤ P(ℓT ≥ τ ) + P(Wℓ ∈ {0, z}) ≤ 1/2.

We are now ready to prove the main result of the section. √ Theorem 4.7. Let d(x) : N → N such that, for all x ∈ N, 1 ≤ d(x) ≤ x/ log x and d(x) is odd. Then there exist a constant c, functions ϕ : N → R and ∆ : N → N such that ϕ(x) = Θ(d(x)/x) and ∆(x) = Θ(x/d(x)) as x → ∞ and the following holds. For infinitely many values of x, there exist an n-vertex temporal graph G and s0 ⊆ V (G) with the following properties. (i) G is d(x)-regular and x ≤ n ≤ 2x. (ii) ForPall time intervals I of length ∆(x) and all sets S ⊆ V (G) with 0 < Vol(S) ≤ Vol(V (G))/2, 1 t t∈I ϕ (S) ≥ ϕ(x). |I| (iii) There exists s0 ⊆ V (G) such that with probability at least 1/2, the standard voter model on G with initial minority set s0 does not absorb within time cx∆(x)/(d(x)ϕ(x)). Proof. Let x be suitably large (to be determined later), let k := (d(x) + 1)/2, let z := ⌈x/k⌉, and √ let n := kz. Observe that x ≤ n ≤ 2x as required by (i) since d(x) ≤ x/ log x and x is large. Let T := 4z. Let G := G T,k,z , and observe that G is a d(n)-regular graph as required by (i). 1 Let ϕ(x) := 12z and ∆(x) := 3T , observing that ϕ(x) = Θ(d(x)/x) and ∆(x) = Θ(x/d(x)) as x → ∞ as required in the statement. By Lemma 4.4, for all half-volume sets S ⊆ V (G), 1 X t ϕ (S) ≥ 1/(12z) = ϕ(x), 3T t∈Ii

as required by (ii). pLet Γ > 0 be as in Lemma 4.6. √Observe that since n = Θ(x), k = Θ(d(x)), and d(x) = o( x/ log x), we have z = n/k = ω( x log x); thus since x is sufficiently large, we have z ≥ 20 and T = 4z ≥ 20Γk log x ≥ 10Γk log z as required by Lemma 4.6. Hence, Lemma 4.6 applies to G; let s0 ⊆ V (G) be the minority set from the lemma statement, and observe that with probability at least 1/2, the standard voter model on G with initial state s0 does not absorb within time T z 2 /128. It remains to prove that T z 2 /128 ≥ cn∆(x)/(d(x)ϕ(x)) for a suitable choice of c. Since ϕ(x) = 1/(12z) we have that z = 1/(12ϕ(x)), and T = ∆(x)/3; thus T z 2 /128 ≥ ∆(x)z/(104 ϕ(x)). Moreover, z = n/k ≥ x/d(x), so it follows that ∆(x)x T z2 ≥ 4 . 128 10 ϕ(x)d(x) On taking c = 1/104 , (iii) follows, and thereby so does the result. 31

Theorem 1.4 (Lower bound). There exist c > 0, ϕ : N → R and ∆ : N → N with ϕ(n) = Θ(1/n) and ∆(n) = Θ(n) as n → ∞ such that the following holds. For all odd integers d, there exist arbitrarily large n-vertex d-regular temporal graphs G such that: (i) ForPall time intervals I of length ∆(n) and all sets S ⊆ V (G) with 0 < Vol(S) ≤ m, we have 1 t t∈I ϕ (S) ≥ ϕ(n). |I| (ii) From some initial state, with probability at least 1/2, the standard voter model on G does not absorb within time cn∆(n)/ϕ(n). Proof. We apply Theorem 4.7, taking d(x) = d for all x. Take c′ , ϕ′ and ∆′ to be the c, ϕ and ∆ of Theorem 4.7, let x be suitably large, let G be a temporal graph satisfying Theorem 4.7(i)–(iii) for x, and let n := |V (G)| so that x ≤ n ≤ 2x and in particular n is suitably large. We define ϕ(n) := ϕ′ (x), ∆(n) := ∆′ (x), and c := 2c′ . Observe that since n = Θ(x), ϕ′ (x) = Θ(d(x)/x) and ∆′ (x) = Θ(x/d(x)), ϕ and ∆ have the correct growth rates. Moreover: G is d-regular by Theorem 4.7(i); (i) of the statement is immediate from Theorem 4.7(ii); and (ii) of the statement follows from Theorem 4.7(iii) together with x ≥ n/2 and c = 2c′ . Main Theorem 2 (Lower bound). There exist arbitrarily large n-vertex 3-regular temporal graphs G, and constant c with the following property. From some initial state, with probability at least 1/2, the standard voter model running on G does not absorb within time cn/Φ(G). Proof. Let ϕ(n) and ∆(n) be as in Theorem 1.4, then by the definition of conductance it holds that Φ(G) ≥ ϕ(n)/∆(n), therefore cn∆/(d(n)ϕ(n)) ≥ cn/(d(n)Φ(G)) The result follows by choosing d = 3, and C = c/3.

References [1] Noga Alon and V. D. Milman. λ1 , isoperimetric inequalities for graphs, and superconcentrators. J. Comb. Theory B, 38(1):73–88, 1985. doi:10.1016/0095-8956(85)90092-9. [2] Sara Ansari, Jobst Heitzig, Laura Brzoska, Hartmut HK Lentz, Jakob Mihatsch, Jörg Fritzemeier, and Mohammad R Moosavi. A temporal network model for livestock trade systems. Frontiers in veterinary science, 8:766547, 2021. [3] Sanjeev Arora, Satish Rao, and Umesh V. Vazirani. Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2):5:1–5:37, 2009. doi:10.1145/1502793.1502794. [4] Chen Avin, Michal Koucký, and Zvi Lotker. Cover time and mixing time of random walks on dynamic graphs. Random Struct. Algorithms, 52(4):576–596, 2018. doi:10.1002/RSA.20752. [5] Petra Berenbrink, George Giakkoupis, Anne-Marie Kermarrec, and Frederik Mallmann-Trenn. Bounds on the voter model in dynamic networks. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, July 11-15, 2016, volume 55 of LIPIcs, pages 146:1–146:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. doi:10.4230/LIPICS.ICALP.2016.146. 32

[6] Claudio Castellano, Santo Fortunato, and Vittorio Loreto. Statistical physics of social dynamics. Reviews of Modern Physics, 81(2):591–646, 2009. doi:10.1103/RevModPhys.81.591. [7] Andrea E. F. Clementi, Claudio Macci, Angelo Monti, Francesco Pasquale, and Riccardo Silvestri. Flooding time of edge-markovian evolving graphs. SIAM J. Discret. Math., 24(4):1694– 1712, 2010. doi:10.1137/090756053. [8] Peter Clifford and Aidan Sudbury. A model for spatial conflict. Biometrika, 60(3):581–588, 1973. doi:10.1093/biomet/60.3.581. [9] Colin Cooper, Robert Elsässer, Hirotaka Ono, and Tomasz Radzik. Coalescing random walks and voting on connected graphs. SIAM J. Discret. Math., 27(4):1748–1758, 2013. doi:10.1137/120900368. [10] Colin Cooper, Alan M. Frieze, and Tomasz Radzik. Multiple random walks in random regular graphs. SIAM J. Discret. Math., 23(4):1738–1761, 2009. doi:10.1137/080729542. [11] Daniel J. DiTursi, Gaurav Ghosh, and Petko Bogdanov. Local community detection in dynamic networks. In Vijay Raghavan, Srinivas Aluru, George Karypis, Lucio Miele, and Xindong Wu, editors, 2017 IEEE International Conference on Data Mining, ICDM 2017, New Orleans, LA, USA, November 18-21, 2017, pages 847–852. IEEE Computer Society, 2017. doi:10.1109/ICDM.2017.103. [12] John Fernley and Marcel Ortgiese. Voter models on subcritical scale-free random graphs. Random Struct. Algorithms, 62(2):376–429, 2023. arXiv:1911.13187, doi:10.1002/rsa.21107. [13] Andreas Galanis, Leslie Ann Goldberg, and Xandru Mifsud. Logarithmic mixing of random walks on dynamical random cluster models, 2026. arXiv:2605.06511. [14] George Giakkoupis, Thomas Sauerwald, and Alexandre Stauffer. Randomized rumor spreading in dynamic graphs. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II, Lecture Notes in Computer Science, pages 495–507. Springer, 2014. doi:10.1007/978-3-662-43951-7˙42. [15] Yehuda Hassin and David Peleg. Distributed probabilistic polling and applications to proportionate agreement. Information and Computation, 171(2):248–268, 2001. doi:10.1006/inco.2001.3088. [16] Richard A. Holley and Thomas M. Liggett. Ergodic theorems for weakly interacting infinite systems and the voter model. The Annals of Probability, 3(4):643–663, 1975. doi:10.1214/aop/1176996306. [17] Mark Jerrum and Alistair Sinclair. Conductance and the rapid mixing property for Markov chains: the approximation of the permanent resolved (preliminary version). In Janos Simon, editor, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA, pages 235–244. ACM, 1988. doi:10.1145/62212.62234. [18] Varun Kanade, Frederik Mallmann-Trenn, and Thomas Sauerwald. On coalescence time in graphs: When is coalescing as fast as meeting? ACM Trans. Algorithms, 19(2), April 2023. doi:10.1145/3576900.

33

[19] Gregory F. Lawler and Alan D. Sokal. Bounds on the L2 spectrum for Markov chains and Markov processes: A generalization of Cheeger’s inequality. Transactions of the American Mathematical Society, 309(2):557–580, 1988. doi:10.2307/2000925. [20] Johannes Lengler. Drift analysis. In Benjamin Doerr and Frank Neumann, editors, Theory of Evolutionary Computation - Recent Developments in Discrete Optimization, Natural Computing Series, pages 89–131. Springer, 2020. doi:10.1007/978-3-030-29414-4˙2. [21] David A. Levin and Yuval Peres. Markov Chains and Mixing Times. MBK. American Mathematical Society, 2017. doi:10.1090/mbk/107. [22] Thomas M. Liggett. Stochastic Interacting Systems: Contact, Voter and Exclusion Processes, volume 324 of Grundlehren der mathematischen Wissenschaften. Springer, 1999. doi:10.1007/978-3-662-03990-8. [23] Thomas Milton Liggett and Thomas M Liggett. Springer, 1985.

Interacting particle systems, volume 2.

[24] Milena Mihail. Conductance and convergence of Markov chains—A combinatorial treatment of expanders. In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 526–531. IEEE Computer Society, 1989. doi:10.1109/SFCS.1989.63529. [25] Thomas Sauerwald and Luca Zanetti. Random walks on dynamic graphs: Mixing times, hitting times, and return probabilities. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, Patras, Greece, July 9-12, 2019, LIPIcs, pages 93:1–93:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPICS.ICALP.2019.93. [26] Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing Markov chains. Inf. Comput., 82(1):93–133, 1989. doi:10.1016/0890-5401(89)90067-9. [27] V. Sood and S. Redner. Voter model on heterogeneous graphs. Phys. Rev. Lett., 94:178701, 2005. arXiv:cond-mat/0412599, doi:10.1103/PhysRevLett.94.178701. [28] Guillaume St-Onge, Laurent Hébert-Dufresne, and Antoine Allard. Nonlinear bias toward complex contagion in uncertain transmission settings. Proceedings of the National Academy of Sciences, 121(1):e2312202121, 2024.

34