Let $M$ be a matroid with ground set $E$. If $t$ is a total order on $E$, and if $S$ is a nonempty subset of $E$, then $\max_t S$ will mean the $t$-largest element of $S$ (that is, the maximum of $S$ with respect to the order $t$). If $t$ is a total order on $E$, then

  • a $t$-broken circuit of $M$ will mean a set of the form $C \setminus \max_t C$, where $C$ is a circuit of $M$.

  • we let $\operatorname{NBC}\left( t\right)$ be the set of all subsets of $E$ which contain no $t$-broken circuits of $M$.

Note that $\operatorname{NBC}\left( t\right)$ is known as the broken-circuit complex of $M$ with total order $t$ (see, e.g., Tom Brylawski, The broken-circuit complex, Trans. Amer. Math. Soc. 234 (1977), pp. 417--433).

If $t_1$ and $t_2$ are two total orders on $E$, then we say that $t_1$ and $t_2$ are adjacent if there exists only one pair $\left(e, e^{\prime}\right)$ of elements of $E$ such that $e < e^{\prime}$ with respect to $t_1$ but $e > e^{\prime}$ with respect to $t_2$. This relation "adjacent" is a symmetric relation on the set of all total orders on $E$. (If you encode total orders as permutations by fixing an "initial" total order on $E$, then this relation simply becomes the "differ by a simple transposition" relation that constructs the edges of the permutohedron.)

Let $t_1$ and $t_2$ be two adjacent total orders on $E$. Let $\left(e, e^{\prime}\right)$ be the unique pair of elements of $E$ such that $e < e^{\prime}$ with respect to $t_1$ but $e > e^{\prime}$ with respect to $t_2$. Note that this pair automatically has the property that $e^{\prime}$ covers $e$ with respect to $t_1$, and $e$ covers $e^{\prime}$ with respect to $t_2$. Note also that every nonempty subset $S$ of $E$ satisfies $\max_{t_2} S = \max_{t_1} S$, unless we have $\max_{t_1} S = e^{\prime}$ and $\max_{t_2} S = e$.

It is well-known that the size of $\operatorname{NBC}\left( t\right) $ does not depend on the total order $t$ (and is actually the dimension of the Orlik-Solomon algebra of $M$). This can be shown combinatorially by devising a bijection $\phi_{t_1, t_2} : \operatorname{NBC}\left( t_1\right) \to \operatorname{NBC}\left( t_2\right) $. Here is how I do this:

Let $K\in\operatorname{NBC}\left( t_1\right) $. If there is no circuit $C$ of $M$ that satisfies $\max_{t_1} C = e^{\prime}$ and $C\setminus\left\{ e\right\} \subseteq K$, then $\phi_{t_1, t_2}\left(K\right) = K$. If such a circuit $C$ exists, then $\phi_{t_1, t_2}\left(K\right) = K\setminus\left\{ e^{\prime}\right\} \cup\left\{ e\right\} $ (notice that $e^{\prime}$ belongs to $K$ in this case, but $e$ does not). The following is not hard to see:

Proposition 1. The map $\phi_{t_1, t_2} : \operatorname{NBC}\left( t_1\right) \to \operatorname{NBC}\left( t_2\right)$ is well-defined and bijective. Its inverse is the map $\phi_{t_2, t_1}$ constructed in the same way.

Note that the definition of the map $\phi_{t_2, t_1}$ is the same as that of the map $\phi_{t_1, t_2}$, but with $e$ and $e^{\prime}$ trading roles (and, of course, $t_1$ and $t_2$ trading roles as well). The proof of Proposition 1 is not difficult (it uses the circuit exchange axiom for matroids).

I doubt I am the first to discover Proposition 1 -- Sam Hopkins suspects that Tutte has done the same in the 40s, and it also feels like the apparently fairly commonplace question of what happens to the Gröbner basis of a polynomial ideal when the underlying monomial order slightly changes. (Though I don't know what is known about said question -- matroids are more about its linear case.)

Question (rough version). So we have toggle-like bijections between $\phi_{t_1, t_2} : \operatorname{NBC}\left( t_1\right) \to \operatorname{NBC}\left( t_2\right)$ for all pairs $\left(t_1, t_2\right)$ of adjacent total orders on $E$. What can we say about those? When do they commute? When do they satisfy braid relations? (Not always, but maybe order $6$ ?) What can we say about their longest-word-like compositions?

Let me make this a bit more concrete, at the expense of possibly barking up a wrong tree.

Let $n = \left|E\right|$. If $i \in \left\{1,2,\ldots,n-1\right\}$, and if $t$ is a total order on $E$, then we can define $t s_i$ to be the total order that differs from $t$ only in that the $i$-th smallest element of $t$ trades places with the $\left(i+1\right)$-st smallest element of $t$. Of course, the total orders $t$ and $t s_i$ are then adjacent, and conversely, any pair $\left(t_1, t_2\right)$ of adjacent total orders has the property that $t_2 = t_1 s_i$ for some $i \in \left\{1,2,\ldots,n-1\right\}$.

Let $\mathcal{N}$ be the disjoint union of the sets $\operatorname{NBC}\left(t\right)$ over all the $n!$ total orders $t$ on $E$. For each $i \in \left\{1,2,\ldots,n-1\right\}$, we define a map $\phi_i : \mathcal{N} \to \mathcal{N}$ by combining the maps $\phi_{t, t s_i} : \operatorname{NBC}\left(t\right) \to \operatorname{NBC}\left(t s_i\right)$ for all total orders $t$. These maps $\phi_i$ are involutions (i.e., satisfy $\phi_i^2 = \operatorname{id}$) by Proposition 1.

Concrete question 2. Do we have $\phi_i \circ \phi_j = \phi_j \circ \phi_i$ whenever $\left|i-j\right| > 1$ ?

Concrete question 2 has been answered positively by Fedor Petrov below.

Concrete question 3. The uniform matroid of dimension $k$ shows that we do not generally have $\phi_i \circ \phi_{i+1} \circ \phi_i = \phi_{i+1} \circ \phi_i \circ \phi_{i+1}$ for all $i \in \left\{1,2,\ldots,n-2\right\}$. But do we have Coxeter-group-like identities such as $\left(\phi_i \circ \phi_{i+1}\right)^6 = \operatorname{id}$ ?

Note that each $i \in \left\{1,2,\ldots,n-2\right\}$ and each $x \in \mathcal{N}$ satisfy either $\left(\phi_i \circ \phi_{i+1}\right)^6\left(x\right) = x$ or $\left(\phi_i \circ \phi_{i+1}\right)^9\left(x\right) = x$. (This is not hard to prove: Consider any element of $\mathcal{N}$ as a pair $\left(t, K\right)$ of a total order $t$ on $E$ and a set $K \in \operatorname{NBC}\left(t\right)$. Then, the map $\left(\phi_i \circ \phi_{i+1}\right)^3$ preserves the first entry of the pair, and thus can be regarded as a permutation of $\operatorname{NBC}\left(t\right)$ for each fixed $t$. This permutation can only have orbits of size $1$, $2$ or $3$, since it can only toggle the $i$-th smallest, $\left(i+1\right)$-st smallest and $\left(i+2\right)$-nd smallest elements of $t$ in/out of the subset $K$.)

  • $\begingroup$ In theory you could try to construct such toggles for any class of subsets of edges determined by fixing activities (here I'm talking about generalized activities in the sense of Gordon and Traldi sciencedirect.com/science/article/pii/0012365X9090019E) $\endgroup$ Feb 25, 2019 at 2:32
  • $\begingroup$ What is this group, by the way (generated by relations from Questions 2,3)? $\endgroup$ Mar 4, 2019 at 22:25
  • $\begingroup$ @FedorPetrov: Some infinite Coxeter group. I know that the same group governs many other toggles, but I don't know much about it otherwise. $\endgroup$ Mar 5, 2019 at 0:16

1 Answer 1


In Concrete question 2, I think $\phi_i$ and $\phi_j$ commute, also due to matroid circuit change axiom. Let's see. Take an order $t$ and $K\in \operatorname{NBC}(t)$. We say that $K$ is $i$-sensitive for $t$, if there exists a circuit $C$ containing $[t]_i$ (the $i$-th smallest element of $t$) and $[t]_{i+1}$ but not containing $t$-greater elements such that $C\setminus [t]_i\subset K$. What is your bijection $\phi_i$, which changes the order $t$ to the order $ts_i$? It preserves $K$ if $K$ is not $i$-sensitive and replaces $K$ to $(K\setminus [t]_{i+1})\cup [t]_{i}$ if $K$ was $i$-sensitive. In the latter case $K$ remains $i$-sensitive. In the former case, $K$ remains not $i$-sensitive.

Now assume that $|i-j|>1$. Perform $\phi_i$, after that perform $\phi_j$. On the first step we either preserve $K$ or replace $[t]_{i+1}$ onto $[t]_i$ in dependence on $i$-sensitivity, similarly on the second. What does it mean that $\phi_i$ and $\phi_j$ commute? That if $K$ was $j$-sensitive, then so is $\phi_i (K)$, and viceversa. Let us prove it. Assume the contrary, for example, that $K$ was $j$-sensitive but $\phi_i(K)$ is not $j$-sensitive (the case when $K$ was not $j$-sensitive but became reduce to this case by replacing $t$ to $ts_i$). If $j\leqslant i-2$ this is of course not possible, since the circuit of $j$-sensitivity was not touched by $\phi_i$. Assume that $j\geqslant i+2$ and there were the circuits $C_i$ of $i$-sensitivity and $C_j$ of $j$-sensitivity. By matroid circuit change axiom there exists a circuit $C$ contained in $(C_j\cup C_i)\setminus [t]_{i+1}$. Note that all elements of $C$ except possibly $[t]_j$ belong to $\phi_i(K)$ (since $[t]_i\in \phi_i(K)$, $C_i\setminus [t]_i\subset K$, $C_j\setminus [t]_j\subset K$). It implies that $[t]_j\in C\setminus \phi_i (K)$ and that the $st_i$-maximum of $C$ belongs to $\phi_i(K)$, and this maximum is $[t]_{j+1}=[st_i]_{j+1}$. Otherwise $\phi_i(K)$ would not belong to $\operatorname{NBC}(st_i)$. Therefore $\phi_i(K)$ is still $j$-sensitive, a contradiction.

Now I try to answer in positive to Concrete question 3 by proving that $(\phi_i\circ \phi_{i+1})^6=\operatorname{id}$.

Fix $t$ and a set $K\in \operatorname{NBC}(t)$ and an $i \in \left\{1,2,\ldots,n-2\right\}$ and consider what the map $\psi:=\phi_i\circ \phi_{i+1}$ does with $K$ (note that we perfectly understand what it does with $t$). First of all, $K\setminus \{t_i,t_{i+1},t_{i+2}\}$ (where we write $t_j$ for $[t]_j$) is preserved both by $\phi_i$ and $\phi_{i+1}$, thus by $\psi$ (and the set $T:=\{t_i,t_{i+1},t_{i+2}\}$ is also preserved when we consecutively apply $\phi_i,\phi_{i+1}$ to $t$).

Next, $m:=|K\cap T|$ is also preserved. If $m=0$ or $m=3$, $K$ does not change at all, and we have $\psi^3 K=K$, thus $\psi^6K=K$ since also $\psi^3t=t$.

Call a subset $R\subset T$ of size $|R|=m$ admissible if $K_R:=(K\setminus T)\sqcup R\in \operatorname{NBC}(t)$. Note that $\psi^3(K)$ must be of the form $K_R$ for some admissible $R$. Therefore if we have at most 2 admissible subsets $R$, the bijection $\psi^3$ acts either as $\operatorname{id}$ or as an involution on the set of $K_R$ with admissible $R$. In both cases we get $\psi^6 K=K$.

It remains to consider the case when $m=1$ or $m=2$ and all subsets of $T$ of size $m$ are admissible. It means that every circuit $C$ contained in $(K\cap \{t_1,\dots,t_{i-1}\})\cup T$ contains the whole $T$, and $m=1$ (otherwise take an admissible subset $R \subset T$ that contains the at-most-$m$-element set $(T\cap C)\setminus \max_t(C)$, and then $K_R$ would contain $C \setminus \max_t(C)$, which would contradict $K_R \in \operatorname{NBC}(t)$). But in this case the operations $\phi_i$ and $\phi_{i+1}$ do not change $K$ and again $\psi^6K=K$.

  • $\begingroup$ Nice proof! Though I'm wondering if the word "sensible" should perhaps be "sensitive", if the motivation behind it is what I think it is :) $\endgroup$ Feb 27, 2019 at 2:51
  • 1
    $\begingroup$ @darijgrinberg probably yes, changed. Math is difficult but English is difficulter. I see they have also "sensing". $\endgroup$ Feb 27, 2019 at 6:30
  • $\begingroup$ Great job! I'm posting a bounty since these are really two answers in one. $\endgroup$ Feb 28, 2019 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.