Toggles for non-broken-circuit sets in matroids

Question

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$.)

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$.