Let $M$ be a [matroid](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Matroid#Bases_and_circuits) 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](https://www.ams.org/journals/tran/1977-234-02/S0002-9947-1977-0468931-6/)).


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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Covering_relation) $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$.)



Toggles for non-broken-circuit sets in matroids
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$.


