Curvature of basis exchange walks
January 01, 1970
Abstract
We prove both lower and upper bounds on the Ollivier-Ricci curvature of the basis exchange walk on a matroid. We give several examples of non-negatively curved basis exchange walks and negatively curved basis exchange walks.
1 Introduction↩︎
In this note, we consider the discrete Ollivier-Ricci curvature of a specific class of Markov chains, basis exchange walks on matroids. Ollivier–Ricci curvature on metric spaces was first introduced in [1], as an analog to Ricci curvature on manifolds. This definition allowed for several natural extensions of results in geometry, such as Bonnet-Myers theorem and a lower bound on the spectral gap (both of which apply only to spaces with non-negative curvature). Notably, non-negative discrete curvature also implies bounds on the mixing time of a Markov chain (see [2] on path coupling for more details).
Basis exchange walks on matroids are a well-studied class of Markov chains which exhibit many desirable properties: lower bounded spectral gap and lower bounded modified log Sobolev constant [3], spectral independence, and fast mixing [4]. We note that all of these properties are implied by non-negative Ollivier-Ricci curvature and pose the natural follow-up question:
We answer this question negatively: despite the many desirable properties uniformly exhibited by basis exchange walks, there exist both negatively and non-negatively curved basis exchange walks. Furthermore, we show even among standard classes of matroids, such as linear matroids or graphic matroids, there exist both matroids with negatively and non-negatively curved basis exchange walks. This work reinforces the idea that non-negative curvature is a somewhat delicate phenomenon, which cannot be guaranteed by a strongly log-concave stationary distribution (a feature of all basis exchange walks) or the representability of the matroid.
We highlight in particular the implication this has for the connection between spectral independence and Ollivier-Ricci curvature, both local certificates of expansion. Concurrent works [5] and [6] prove non-negative Ollivier-Ricci curvature implies spectral independence (see either work for precise, quantified statements). The validity of the converse to this statement was not previously known, but this work disproves it: basis exchange walks are uniformly 1-spectrally independent, but we establish several examples with negative Ollivier-Ricci curvature.
1.1 Techniques and overview↩︎
To prove the lower bound on curvature (Theorem 1), we analyze a natural coupling of two walks starting from adjacent bases: in the down step, both walks drop the same element if possible, and in the up-step, they add the same element if possible. For the upper bound (Theorem 2), we prove a lower bound on the expected distance of two walks starting from adjacent bases for all possible couplings. We do so by exhaustively considering all events where the distance can drop to 0, and upper bounding the probability that the distance goes to 0 under any coupling. We then consider events where the distance must be at least 2 for any coupling and lower bound this probability.
In Section 2 we give relevant preliminaries. In Section 3 we give a coupling of the down-up walk and use this to prove a lower bound on curvature; we use the same coupling in Section 4 to show non-negative curvature for several examples. In Section 5 we prove an upper bound on curvature, and in Section 6 we give examples of basis exchange walks with negative curvature.
2 Preliminaries↩︎
2.1 Matroids and basis exchange walk↩︎
Definition 1 (Matroid). A matroid \(\mathcal{M} = (E, \mathcal{B})\) is a set \(E\) and a non-empty collection of its subsets \(\mathcal{B}\), called bases, satisfying the following:
no proper subset of a basis is itself a basis, and
for any \(B_1, B_2 \in \mathcal{B}\), if \(b_1 \in B_1 \backslash B_2\), there exists a \(b_2 \in B_2 \backslash B_1\) such that \(B_1 - b_1 + b_2 \in \mathcal{B}\).
The second condition is known as the basis exchange property.
Definition 2 (Rank). The rank of a matroid \(\mathcal{M} = (E, \mathcal{B})\) is the size of any basis \(B \in \mathcal{B}\). Note that by the basis exchange property, all bases must be the same size.
A particularly interesting class of matroids are those induced by a graph \(G\), known as graphic matroids. We consider several graphic matroids as examples, so we define them here.
Definition 3 (Graphic matroids). A graphic matroid induced by a graph \(G\) is a matroid whose basis sets are the spanning forests of \(G\). If \(G\) is connected, the basis sets are the spanning trees of \(G\).
Definition 4 (Down-up walk). The down-up walk or the basis exchange walk is a Markov chain on the bases of a matroid. Starting from a basis \(S \in \mathcal{B}\), the random walk proceeds by dropping an element \(u \in S\) uniformly at random, then moving to a basis containing \(S-u\) uniformly at random.
We note that the above describes the basis exchange walk on a set of bases given by the uniform distribution (i.e., the uniform distribution over all bases will be the stationary distribution). Given a distribution \(\pi\) over \(\mathcal{B}\), one can define the corresponding down-up walk, but for the purposes of this note, we will only be concerned with the uniform case.
2.2 Ollivier–Ricci curvature↩︎
We are interested in the curvature of this walk, in particular the Ollivier–Ricci curvature. In order to define Ollivier–Ricci curvature, we first define the Wasserstein distance.
Definition 5 (Wasserstein distance). Let \(\mu, \nu\) be two probability distributions over some metric space \((X, d)\). The Wasserstein distance between \(\mu\) and \(\nu\) is defined as \[\mathcal{W}(\mu, \nu) = \min_{X \sim \mu, Y \sim \nu} \mathbb{E} d(X, Y),\] where the minimum is over all possible couplings of \(\mu\) and \(\nu\).
Definition 6 (Ollivier–Ricci curvature). For a Markov chain \(P\) over a metric space \((X, d)\), we define the Ollivier–Ricci curvature of \(P\) as the minimum \(\kappa\) such that for all \(S, T \in X\) \[\mathcal{W}(P(S, \cdot), P(T, \cdot)) \leq (1-\kappa)\cdot d(S,T).\]
Note if \(d\) is the metric induced by \(P\), i.e., \(d(S,T) := \inf \{t : P^t(S,T) > 0\}\), we can consider the minimum over only adjacent \(S,T \in X\) in the above definition (see [1] for further details). Throughout, we will take \(d\) to be the metric induced by \(P\).
3 A candidate coupling and a lower bound↩︎
3.1 Coupling↩︎
We define a candidate coupling, which we call the down-step coupling, for the down-up walk starting from any adjacent bases \(S, T\). The following will be useful to denote all possible “up-steps" of a given down-step:
Definition 7. If \(B\) is a basis and \(u \in B\), let \(N(B - u) = \{x \in E : B - u + x \text{ is a basis}\}.\)
Definition 8 (Down-step coupling). Let \(S = \{s, u_1, \ldots, u_{k-1}\}\), \(T = \{t, u_1, \ldots, u_{k-1}\}\) be bases of a rank-\(k\) matroid. Let \(P\) be the basis exchange walk, \(X \sim P(S, \cdot)\), and \(Y \sim P(T, \cdot)\). We couple \(X\) and \(Y\) by first matching the down-steps when possible, then matching the up-steps when possible. More concretely:
If \(S\) drops \(s\), then \(T\) drops \(t\). Since \(S-s = T-t\), we can always couple the up steps to be the same.
If \(S\) drops \(u_i\), then \(T\) drops \(u_i\). Without loss of generality, suppose \[\#N(S-u_i) \geq \#N(T-u_i).\] We couple the up steps in the following way:
If \(S-u_i\) adds \(t\), \(T-u_i\) adds \(s\) (note if \(t \in N(S-u_i)\), then \(s \in N(T-u_i)\) since \(S-u_i +t = T-u_i + s\)).
If \(S-u_i\) adds \(v \in N(S-u_i) \cap N(T-u_i)\), \(T-u_i\) adds \(v\).
If \(S-u_i\) adds \(v \notin N(S-u_i) \cap N(T-u_i)\) with \(v \neq t\), then \(T-u_i\) adds a random element from \(N(T-u_i)\) with any distribution preserving the desired marginal across \(N(T-u_i)\).
The distribution mentioned in the last line is simply a distribution such that the up-step for \(T-u_i\) is uniform across \(N(T-u_i)\); such a distribution will always be possible given that \(\#N(S-u_i) \geq \#N(T-u_i)\). Note that with this coupling, the walks are at distance at most \(2\) by the basis exchange property.
Remark 1. We remark that while this coupling might not be optimal, coupling different down steps for \(S\) and \(T\) can only decrease \(\mathbb{E}d(X,Y)\) in a small number of cases. For example, consider \(S = \{s, u, u'\}\) and \(T = \{t,u,u'\}\). Suppose \(S\) drops \(u\) and adds \(a\), while \(T\) drops \(u'\) and adds \(b\), so \(S\) moves to \(\{s,u,a\}\) and \(T\) moves to \(\{t,b,u'\}\). We are only in a better position (i.e., at a distance less than 2) if: (1) \(a = t\) and \(b = s\), in which case the distance is 1, or (2) \(a = u'\) and \(b = u\), in which case the distance is also 1. We see that for most possible up-steps, it is more advantageous to couple based on the down-step.
We make this more precise with an upper bound on curvature in Section 5.
3.1.0.1 Example:
We give an example of this coupling on the graphic matroid induced by \(K_4\). Let \(S\) and \(T\) be the following spanning trees, respectively:
Figure 1: 
.
Figure 2: 
.
The following table shows how walks would move from \(S\) and \(T\) in the down-step coupling, where \(s\) is the bottom edge and \(t\) is the diagonal edge from the upper left to bottom right. For clarity, we group outcomes under which element is dropped in the down step of the down-up walk.
3.2 Lower bound↩︎
Our first theorem provides a lower bound on the curvature of the basis exchange walk in terms of the rank and the size of the ground set.
Theorem 1. The basis exchange walk of a rank-\(k\) matroid over a set of size \(n > k+1\) satisfies \[\kappa \geq -1 + \frac{2}{k} + \frac{3(k-1)}{k(n- k+ 1)}.\] If \(n=k+1\), the basis exchange walk satisfies \(\kappa \geq 1/k\).
Proof. We show that the above coupling gives us the desired bound.
First note if \(S\) drops \(s\) and \(T\) drops \(t\) (which occurs with probability \(\frac{1}{k}\)) we have \[\mathbb{E} \left (d(X,Y)|s,t \text{ dropped in down step}\right ) = 0.\]
Now we consider what happens when we drop \(u_i\). Letting \(U' = \{u_1,\ldots, u_{i-1}, u_{i+1}, \ldots, u_{k-1}\}\), we have two cases:
3.2.0.1 Case 1:
\(U' + s + t \notin \mathcal{B}\).
We claim \(N(S - u) = N(T-u)\) by the basis exchange property. Let \(x \in N(S-u)\) and \(y \in N(T-u)\), so \[S - u + x = U'+s+x \in \mathcal{B}, \qquad T - u + y = U' + t + y \in \mathcal{B}.\] Applying the basis exchange property to \(U'+s+x, U' + t + y,\) and \(x\), we must have \(U' + s + y \in \mathcal{B}\) since \(U' + s + t \notin \mathcal{B}\), so \(y \in N(S-u)\). Similarly, we can see that \(U' + t + x \in \mathcal{B}\), so \(x \in N(T-u)\).
Since \(N(S-u) = N(T-u)\), we can couple these walks to have the same up-step and in this case \[\mathbb{E}\left (d(X,Y)|u_i \text{ dropped} \right )= 1.\]
3.2.0.2 Case 2:
\(U' + s + t \in \mathcal{B}\)
In this case, we can couple the walks to both move to \(U' + s + t\) with some probability and the distance will be 0. Note that \(N(S-u), N(T-u) \leq n-(k-1)\) since \((S -u) \cap N(S-u) = \emptyset\) (and similarly for \(T\)), so \[\min\{\mathbb{P}(U'+s \rightarrow U' + s + t), \mathbb{P}(U' + t \rightarrow U' + s + t)\} \geq \frac{1}{n-k+1}\] where \(\mathbb{P}(U'+s \rightarrow U' + s + t)\) denotes the probability of adding \(t\) on the up-step, given \(u_i\) was dropped on the down-step (i.e., \(1 / N(S-u_i)\)). Similarly, we can couple the walks to stay at \(S\) and \(T\) respectively, which also occurs with probability \(\geq \frac{1}{n-k+1}\), and the distance is 1. Otherwise, the distance is always less than or equal to 2 since \[U' + s + x \sim U' + s + t \sim U' + t + y.\] All together then we have \[\mathbb{E}\left (d(X,Y)| u_i \text{ dropped}\right ) \leq 2 \cdot \left (1 - \frac{2}{n-k+1} \right ) + \frac{1}{n-k+1} = 2 - \frac{3}{n-k+1}.\]
If \(n > k+1\), in either case we have \[\mathbb{E}\left (d(X,Y) | u_i \text{ dropped} \right ) \leq 2 - \frac{3}{n-k+1}.\] Then we have \[\mathcal{W}(P(S, \cdot), P(T, \cdot)) \leq \frac{(k-1)}{k} \cdot \left (2 - \frac{3}{n-k+1} \right ).\] By definition of \(\kappa,\) we have: \[\begin{align} \kappa &\geq 1 - \frac{(k-1)}{k}\cdot \left (2 - \frac{3}{n-k+1} \right ) \\ & = 1 - \frac{2(k-1)}{k} + \frac{3(k-1)}{k(n-k+1)} \\ & = -1 + \frac{2}{k} + \frac{3(k-1)}{k(n-k+1)}. \end{align}\]
If \(n = k+1\), then in either case \(\mathbb{E}(d(X,Y) | u_i \text{ dropped}) \leq 1\), so we have \(\kappa \geq 1/k.\) ◻
By more carefully tracking which case we are in, we can sharpen this bound. We define the set of elements we can drop that would place us in case two from above:
Definition 9. Let \(J = \{u : t \in N(S-u) \text{ and } u\neq s\}.\)
Corollary 1. The basis exchange walk over any matroid satisfies \[\kappa \geq \min_{S\sim T}\left \{ -\frac{\#J}{k} + \frac{1}{k} + \frac{1}{k}\sum_{u \in J} \frac{2 + \#(N(S-u) \cap N(T-u))}{\max\{\#N(S-u), \#N(T-u)}\}\right \}.\]
Proof. This follows immediately from the down-step coupling and definitions. ◻
While this expression is not particularly friendly, it makes explicit the idea that if there is a high overlap between \(N(S-u)\) and \(N(T-u)\) for all \(u\), the basis exchange walk will be positively curved. In the following examples, we directly analyze the coupling, which is equivalent to applying this corollary (although we refrain from referring to this expression).
4 Examples of non-negatively curved basis exchange walks↩︎
4.1 Non-negative curvature from smallness↩︎
We have the following corollaries to Theorem 1 for rank-2 matroids, matroids over small ground sets, and graphic matroids over small graphs:
Corollary 2. The basis exchange walk on any rank-\(2\) matroid is positively curved.
Corollary 3. The basis exchange walk on any matroid with \(n \leq 7\) is non-negatively curved.
Corollary 4. The basis exchange walk on any graphic matroid induced by a simple graph \(G = (V,E)\) with \(\#V \leq 4\) is non-negatively curved.
4.2 Uniform matroid↩︎
Lemma 1. The basis exchange walk over the rank-\(k\) uniform matroid with size \(n\) ground set satisfies \[\kappa \geq 1 - \frac{(k-1)(n-k)}{k(n-k+1)}.\]
Proof. The down-step coupling gives \[\mathbb{E}d(X,Y) = \frac{1}{k}\cdot 0 + \frac{k-1}{k}\left (\frac{1}{n-k+1}\cdot 0 + \frac{n-k}{n-k+1}\cdot 1 \right ).\] ◻
4.3 Vámos matroid↩︎
The Vámos matroid is a rank-\(4\) matroid over a ground set of size \(8\) that cannot be represented as a matrix over any field. However, this matroid is close, in some sense, to a uniform matroid; it includes 65 of the possible 70 subsets of size \(4\) as bases. The excluded sets are the shaded parallelograms in Figure 22.
The following lemma shows that the Vámos matroid is positively curved. We can interpret this as a consequence of how close the Vámos matroid is to the rank-\(4\) uniform matroid over \(8\) elements.
Lemma 2. The basis exchange walk over the Vámos matroid is positively curved.
Proof. Again we show the down-step coupling demonstrates positive curvature.
Let \(S = \{a,b,c,s\}\) and \(T = \{a,b,c,t\}\) for some distinct elements \(a,b,c,s,t.\) For \(u \neq s, t\) we consider the possibilities for \(N(S-u)\) and \(N(T-u)\). By definition of the Vámos matroid, for any \(S \in \mathcal{B}\) and any \(u \in S\), \(\#N(S-u) = 5\) or \(4\) (i.e., it either contains all the elements not in \(S -u\) or one less). We compute the expected distance in each case.
Suppose \(\#N(S-u) = \# N(T-u) = 5\). Since \(t \in N(S-u)\), the down-step coupling in this case gives \[\mathbb{E}\left (d(X,Y)|u \text{ dropped} \right ) = \frac{4}{5}.\]
Suppose \(\#N(S-u) = 5\) and \(\#N(T-u) = 4\). Again since \(t \in N(S-u)\), in this case we have \[\mathbb{E}\left (d(X,Y)|u \text{ dropped} \right ) \leq \frac{1}{5} \cdot 0 + \frac{3}{5}\cdot 1 + \frac{1}{5} \cdot 2 = 1.\]
Suppose \(\#N(S-u) = \#N(T-u) = 4\). As seen in the proof of Theorem 1, if \(S-u + t \notin \mathcal{B}\), we can couple so the distance is always 1, so we assume \(t \in S-u\) and \(s \in T-u\). Then we must have \(\{u, d\} \subseteq N(S-u) \cap N(T-u)\) for some \(d\). Conditioned on being in this case, we have \[\mathbb{E}\left (d(X,Y)|u \text{ dropped} \right ) \leq \frac{1}{4} \cdot 0 + \frac{1}{2}\cdot 1 + 2 \cdot \frac{1}{4} = 1.\]
In all cases with \(u \neq s, t\) the expected distance is less than or equal to 1, so we see the basis exchange walk on this matroid has positive curvature. ◻
4.4 Graphic matroids↩︎
Now we consider a specific class of graphic matroids that induce positively curved basis exchange walks. This shows that in addition to having non-negatively curved basis exchange walks on graphic matroids induced by sufficiently small graphs, one can have non-negatively curved basis exchange walks on graphic matroids induced by arbitrarily large graphs.
Lemma 3. Basis exchange walks over graphic matroids induced by graphs with edge-disjoint cycles are positively curved.
Proof. We express the graph as a union of cycles, \(C_i\), and edges with effective resistance 1, \(G'\): \[G = C_1 + \ldots + C_k + G'.\] Any spanning tree \(S\) of the graph must be a union of spanning trees \(S_i\) of each cycle and \(G'\) so we have \[S = S_1 + \ldots + S_k + G'.\] Any adjacent spanning tree \(T\) must differ in only one spanning tree of one cycle. Without loss of generality we assume the different spanning tree is in the cycle labeled as \(C_1\), so \[T = T_1 + S_2 + \ldots + S_k + G'.\]
We must show for any \(u \in S \cap T\), we can couple walks from \(S\) and \(T\) conditioned on dropping \(u\) so that the expected distance is not greater than 1. We consider different cases for \(u\).
Suppose \(u \in G'\). For any \(B \in \mathcal{B}\) we have \(N(B-u) = \{u\}\) (i.e, the only edge that can be added on the up step is \(u\)). For this case, we have \[\mathbb{E}\left (d(X,Y)|u \text{ dropped} \right ) = 1.\]
Suppose \(u \in S_i\) with \(i \neq 1\), then \(N(S-u) = N(T-u) = \{u,u'\}\) where \(\{u'\} = C_i \backslash S_i\). We can always add the same element to each of \(S-u\) and \(T-u\), so we again have \[\mathbb{E}\left (d(X,Y)|u \text{ dropped} \right ) = 1.\]
Suppose \(u \in S_1\), then \(N(S-u) = \{u, t\}\) and \(N(T-u) = \{u, s\}\) where \(t = C_1 \backslash S_1\) and \(s = C_1 \backslash T_1\) (similar to previous notation, \(s\) is simply the edge included in \(S\) but not in \(T\)). Since \(S_1 = C_1 - t\) and \(T_1 = C_1 - s\), \(S_1 - u + t = T_1 - u + s\). We couple by adding \(u\) to both \(S\) and \(T\) or adding \(t\) to \(S\) and \(s\) to \(T\). In this case, we have \[\mathbb{E}\left (d(X,Y)|u \text{ dropped} \right ) = 1/2.\]
This covers all cases, so the basis exchange walk is positively curved. ◻
5 Upper bound on curvature↩︎
We now give an upper bound on the curvature of the basis exchange walk (we note the main function of this bound will be to prove specific examples have negative curvature). In order to state this bound, we fix any \(S \sim T\) and define the following notation.
Definition 10. Let \(J = \{u : t \in N(S-u) \text{ and } u\neq s\}.\)
Definition 11. For any \(u \in J\), let \(A_u = (N(S-u) - t) \backslash N(T-u)\), i.e., the elements that are not \(t\) and that can be added to \(S-u\) but cannot be added to \(T-u\).
Remark 2. These sets will be to identify neighbors of \(S\) that are all far from all but a small number of neighbors of \(T\) (see Proposition 3 for a more precise statement). If \(t \notin N(S-u)\), then as seen in the proof of Theorem 1, \(N(S-u) = N(T-u)\). In this case, every neighbor of \(S\) induced by dropping \(u\) has a unique neighbor of \(T\) induced by dropping \(u\).
Theorem 2. Consider any bases \(S \sim T\) of a matroid \(\mathcal{M}\). Then the basis exchange walk on \(\mathcal{M}\) satisfies \[\kappa \leq \frac{1}{k} + \frac{1}{k}\cdot\sum_{u\in J}\left (\frac{1}{\#N(T-u)} - \frac{\#A_u}{\#N(S-u)} \right ).\]
Proof. Let \(S\) and \(T\) be adjacent bases with \(S = \{s, u_1, \ldots, u_{k-1}\}\) and \(T = \{t, u_1, \ldots, u_{k-1}\}\). Let \(X \sim P(S,\cdot)\) and \(Y \sim P(T, \cdot)\). Note for any coupling we have \[\begin{align} \mathbb{E}d(X,Y) &\geq 0 \cdot \mathbb{P}(d(X,Y) = 0) + 1 \cdot \mathbb{P}(d(X,Y) = 1) + 2 \cdot \mathbb{P}(d(X,Y) \geq 2) \\ &= (1-\mathbb{P}(d(X,Y) = 0) - \mathbb{P}(d(X,Y) \geq 2)) + 2 \cdot \mathbb{P}(d(X,Y) \geq 2) \\ &= 1 - \mathbb{P}(d(X,Y) = 0) + \mathbb{P}(d(X,Y) \geq 2). \end{align}\] Recalling the definition of curvature, we see then \[\kappa \leq \mathbb{P}(d(X,Y) = 0) - \mathbb{P}(d(X,Y) \geq 2).\] We will upper bound this quantity for any coupling.
We start by considering events where \(d(X,Y) \geq 2\). In particular, we want to identify neighbors of \(S\) that are from most neighbors of \(T\). The following proposition shows that any neighbor of \(S\) of the form \(S-u + a\) for some \(u \in J\) and some \(a \in A_u\) is far from almost all neighbors of \(T\).
Proposition 3. For any \(u \in J\) and \(a \in A_u\), \(S-u+a\) is at distance at least 2 from any neighbor of \(T\) aside from \(T-u+s,\) \(T-t+s,\) or \(T-t+a\) (if these sets are bases).
Proof. Without loss of generality, let \(u = u_1\). Then \(S-u+a = \{s, a, u_2, \ldots, u_{k-1}\}\). We proceed by cases on which element \(T\) drops.
Case 1: \(T\) drops \(u_1\) and adds some element \(b\), so \(T-u_1 + b = \{t, b, u_2, \ldots, u_{k-1}\}\).
Recall by definition of \(A_{u_1}\), \(b \notin N(T-u_1)\) so \(b \neq a\). Since \(a \neq u_1,t\), these are at distance 2 unless \(b = s\).
Case 2: \(T\) drops \(t\) and adds some element \(b\), so \(T-t + b = \{b, u_1, \ldots, u_{k-1}\}\).
Since \(a \neq u_1\), these are at distance 2 unless \(b = s\) or \(b = a\).
Case 3: \(T\) drops \(u_i \neq u_1\) and adds \(b\).
Then \(T-u_i+b\) contains \(t\) and \(u_1\), neither of which are contained in \(S-u_1+a\), so \(T-u_i+b\) is at distance at least 2 from \(S-u_1+a\). ◻
We define the following relevant events: \[\begin{align} \mathcal{F}_{u,a} &:= \{S \text{ drops } u \text{ and adds } a \in A_u\} &&\text{for any } u \in J, a \in A_u\\ \mathcal{B}_u &:= \{T \text{ drops } u \text{ and adds } s\} &&\text{for any }u \in J,\\ \mathcal{E}_a&:= \{T \text{ drops } t \text{ and adds } a\} &&\text{for any }a \in N(T-t). \end{align}\] The above proposition shows \[\begin{align} \label{eq:probtwo} \mathbb{P}(d(X,Y) \geq 2) \geq \sum_{u \in J} \sum_{a \in A_u} \mathbb{P}(\mathcal{F}_{u,a}) - \mathbb{P}(\mathcal{F}_{u,a} \cap \mathcal{B}_u) - \mathbb{P}(\mathcal{F}_{u,a} \cap \mathcal{E}_s) - \mathbb{P}(\mathcal{F}_{u,a} \cap \mathcal{E}_a). \end{align}\tag{1}\]
Now we consider events where \(d(X,Y) = 0\). The following table gives all possible pairs of exchanges by \(S\) and \(T\) so that \(d(X,Y) = 0\).
| Exchange by \(S\) | Exchange by \(T\) |
|---|---|
| \(S\) drops \(s\), adds \(t\) | \(T\) drops \(u\), adds \(u\) for any \(u \in T\) |
| \(S\) drops \(s\), adds \(a \neq t\) | \(T\) drops \(t\), adds \(a\) |
| \(S\) drops \(u \neq s\), adds \(u\) | \(T\) drops \(t\), adds \(s\) |
| \(S\) drops \(u \in J\), adds \(t\) | \(T\) drops \(u\), adds \(s\) |
We define the additional relevant events, based on the exchange made by \(S\): \[\begin{align} \mathcal{C}_{1,a} &:= \{S \text{ drops } s, \text{ adds } a\}, \\ \mathcal{C}_{2,u} &:= \{S \text{ drops } u, \text{ adds } u\} && \text{for any } u \in S, u \neq s,\\ \mathcal{C}_{3,u} &:= \{S \text{ drops } u, \text{ adds } t\} && \text{for any } u \in J. \end{align}\] Then we have \[\begin{align} \label{eq:probzero} \mathbb{P}(d(X,Y) = 0) \leq \mathbb{P}(\mathcal{C}_{1,t}) + \sum_{a \neq t} \mathbb{P}(\mathcal{C}_{1,a} \cap \mathcal{E}_{a}) + \sum_{\substack{u \in S \\ u \neq s}} \mathbb{P}(\mathcal{C}_{2,u} \cap \mathcal{E}_s) + \sum_{u \in J} \mathbb{P}(\mathcal{C}_{3,u} \cap \mathcal{B}_u) \end{align}\tag{2}\]
Now we want to combine these two expressions. First note that if we collect some of the terms in the difference between 2 and 1 , we can simplify as follows: \[\begin{align} \mathbb{P}(\mathcal{C}_{1,t}) + \sum_{a \neq t} \mathbb{P}(\mathcal{C}_{1,a} \cap \mathcal{E}_{a}) + \sum_{\substack{u \in S \\ u \neq s}} \mathbb{P}(\mathcal{C}_{2,u} \cap \mathcal{E}_s) + \sum_{u \in J} \sum_{a \in A_u} (\mathbb{P}(\mathcal{F}_{u,a} \cap \mathcal{E}_s) + \mathbb{P}(\mathcal{F}_{u,a} \cap \mathcal{E}_a)) \\ \leq \mathbb{P}(\mathcal{C}_{1,t}) + \sum_{\substack{a \in N(T-t) \\ a \neq t}} \mathbb{P}(\mathcal{E}_a) = \frac{1}{k} \cdot \left (\frac{1}{\#N(S-s)} + \frac{\#N(S-s) - 1}{\#N(S-s)} \right )= \frac{1}{k}. \end{align}\] Passing to the full expression we have \[\begin{align} \mathbb{P}(d(X,Y) = 0) - \mathbb{P}(d(X,Y) \geq 2) &\leq \frac{1}{k} + \sum_{u \in J} \mathbb{P}(\mathcal{C}_{3,u} \cap \mathcal{B}_u) + \sum_{u \in J} \sum_{a \in A_u} \mathbb{P}(\mathcal{F}_{u,a} \cap \mathcal{B}_u) - \sum_{u \in J} \sum_{u \in A_u} \mathbb{P}(\mathcal{F}_{u,a}) \\ &\leq \frac{1}{k} + \sum_{u \in J} \mathbb{P}(\mathcal{B}_u) - \sum_{u \in J}\sum_{u \in A_u} \mathbb{P}(\mathcal{F}_{u,a}). \end{align}\] Explicitly computing these probabilities, we have \[\begin{align} \kappa &\leq \frac{1}{k} + \frac{1}{k}\sum_{u\in J}\left (\frac{1}{\#N(T-u)} - \frac{\#A_u}{\#N(S-u)} \right ). \end{align}\] ◻
An immediate corollary of the above is a sufficient condition for negative curvature:
Corollary 5. The basis exchange walk on \(\mathcal{M}\) is negatively curved if there exist bases \(S \sim T\) such that \[\sum_{u\in J}\left (\frac{\#A_u}{\#N(S-u)} - \frac{1}{\#N(T-u)} \right ) > 1.\]
6 Examples of negatively curved basis exchange walks↩︎
By Corollary 2, all basis exchange walks over rank-\(2\) matroids are positively curved. However, as soon as we move to rank-\(3\) matroids, this is no longer true as shown in Section 6.1. One might then hope that certain classes of matroids, for example regular matroids, induce non-negatively curved basis exchange walks. In Section 6.2, we show this is not the case: we give a graphic matroid (thus also a regular matroid) with a negatively curved basis exchange walk.
6.1 Rank-3 matroid↩︎
The bound from Theorem 2 says that in order to ensure negative curvature, it suffices to have \(S\) and \(T\) so that \(N(S-u)\) is very different from \(N(T-u)\) for many \(u\). We construct a matroid with this property.
Let \(E = \{s, t, u, u', v_1, \ldots, v_5, w_1, \ldots, w_5\}\). We define a matroid over \(E\) by defining the bases:
\(S = \{s,u,u'\}\),
\(T = \{t,u,u'\}\),
\(\{s,t,u\}, \{s,t,u'\}\),
\(\{s, u, v_i\}, \{s, u', v_i\}\) for all \(i\),
\(\{t, u, w_i\}, \{t, u', w_i\}\) for all \(i\),
\(\{u,u',v_i\}, \{u,u',w_i\}\) for all \(i\), and
\(\{u, v_i, w_j\}, \{u', v_i, w_j\}\) for all \(i, j\).
This is a \(\mathbb{R}\)-linear matroid, with the elements identified with the following vectors in \(\mathbb{R}^3\): \[s = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix},t = \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix},u = \begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix},u' = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix},v_i = \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix},w_i = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}.\]
We have \(J = \{u, u'\}\), \(\#A_j = 5\), and \(N(S-j) = N(T-j)= 7\) for \(j \in J\), so by Theorem 2 \[\begin{align} \kappa \leq \frac{1}{3} + \frac{1}{3} \cdot \left (\frac{2}{7} - \frac{2\cdot 5}{7} \right ) = -\frac{1}{21}. \end{align}\]
6.2 Graphic matroid↩︎
We want to construct a graphic matroid with spanning trees \(S\) and \(T\) so that \(N(S-u)\) and \(N(T-u)\) are very different for many \(u\). We look at the graphic matroid induced by \(K_6\); in order to make the set \(J\) as large as possible, we choose \(S\) and \(T\) to be paths. We label the “outer" edges of \(K_6\) as in Figure 3, and consider the spanning trees \(S = \{s,1,2,3,4\}\) and \(T = \{t, 1,2,3,4\}\).
We count the relevant quantities for Theorem 2. In the following table, let \(i\) be the element dropped in the “down" step of the down-up walk.
| \(i\) | \(\# N(S-i)\) | \(\# N(T-i)\) | \(\# A_i\) |
|---|---|---|---|
| 1 | \(2 \cdot 4\) | \(1 \cdot 5\) | 5 |
| 2 | \(1 \cdot 5\) | \(2 \cdot 4\) | 2 |
| 3 | \(1 \cdot 5\) | \(2 \cdot 4\) | 2 |
| 4 | \(2 \cdot 4\) | \(1 \cdot 5\) | 5 |
By Theorem 2 we have \[\begin{align} \kappa &\leq \frac{1}{5} + \frac{1}{5} \left (\frac{2}{5} + \frac{2}{8} - \frac{2 \cdot 5}{8} - \frac{2\cdot 2}{5} \right ) = -\frac{2}{25}. \end{align}\]
Acknowledgements↩︎
The author would like to thank Nikhil Srivastava for introducing her to this question and Zack Stier for helpful conversations and comments.