#Introduction

We describe colored matroids as families of words satisfying cyclic exchange. We begin with classical matroids, where two-color words are indicator vectors of bases, and then pass to words with any number of colors.

#Classical matroids

Definition (Matroid bases).

A matroid \(M\) on a finite ground set \(E\) may be specified by a nonempty equicardinal family \(\mathcal B(M)\) of bases satisfying basis exchange: for \(B,C\in\mathcal B(M)\) and \(e\in B\setminus C,\) there is an \(f\in C\setminus B\) such that \[(B\setminus\{e\})\cup\{f\}\in\mathcal B(M).\] The dual matroid \(M^*\) has bases \[\mathcal B(M^*)=\{E\setminus B:B\in\mathcal B(M)\}.\]

Example (A rank-three matroid on seven elements).

Let \(E=[7],\) partitioned into the three sets \[\{1,2\},\qquad \{3,4\},\qquad \{5,6,7\}.\] Let \(\mathcal B(M)\) consist of the triples that contain one element from each set. This is the basis family of a rank-three matroid: if \(e\in B\setminus C,\) replace \(e\) by the element of \(C\) that belongs to the same set as \(e.\)

Each basis gives an ordered partition \((B,E\setminus B).\) Color the elements of the basis \(1\) and the elements of its complement \(0.\) The twelve ordered partitions are \[\begin{array}{c|c|c} \text{word}&\text{Color }1&\text{Color }0\\ \hline \mathtt{1010100}&\{1,3,5\}&\{2,4,6,7\}\\ \mathtt{1010010}&\{1,3,6\}&\{2,4,5,7\}\\ \mathtt{1010001}&\{1,3,7\}&\{2,4,5,6\}\\ \mathtt{1001100}&\{1,4,5\}&\{2,3,6,7\}\\ \mathtt{1001010}&\{1,4,6\}&\{2,3,5,7\}\\ \mathtt{1001001}&\{1,4,7\}&\{2,3,5,6\}\\ \mathtt{0110100}&\{2,3,5\}&\{1,4,6,7\}\\ \mathtt{0110010}&\{2,3,6\}&\{1,4,5,7\}\\ \mathtt{0110001}&\{2,3,7\}&\{1,4,5,6\}\\ \mathtt{0101100}&\{2,4,5\}&\{1,3,6,7\}\\ \mathtt{0101010}&\{2,4,6\}&\{1,3,5,7\}\\ \mathtt{0101001}&\{2,4,7\}&\{1,3,5,6\} \end{array}\] The Color 1 sets are the rank-three bases of \(M.\) Their complements, shown in the Color 0 column, are the rank-four bases of \(M^*.\) Each word is the indicator vector of its Color 1 basis. Thus, with two colors, the words are simply the bases written in position notation; the Color 0 positions simultaneously record the bases of the dual matroid.

Take \(u=\mathtt{1010100}\) and \(v=\mathtt{0101010}.\) The Color 1 set of \(u\) contains \(1\) but not \(2,\) while the Color 1 set of \(v\) contains \(2\) but not \(1.\) Exchanging these two elements gives the bases \(\{2,3,5\}\) and \(\{1,4,6\}.\) In the colored words, the pairs at positions \(1\) and \(2\) are \((1,0)\) and \((0,1),\) forming the cycle \[1\longrightarrow 0\longrightarrow 1.\] The highlighted columns show the exchange. The first two rows are the original words, and the last two are obtained by switching positions \(1\) and \(2\) in both words:

\(\text{position}\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \( u\) \(1\) \(0\) \(1\) \(0\) \(1\) \(0\) \(0\) \( v\) \(0\) \(1\) \(0\) \(1\) \(0\) \(1\) \(0\) \( u'\) \(0\) \(1\) \(1\) \(0\) \(1\) \(0\) \(0\) \( v'\) \(1\) \(0\) \(0\) \(1\) \(0\) \(1\) \(0\)

Thus \(u'=\mathtt{0110100}\) and \(v'=\mathtt{1001010},\) which are again rows of the table. Basis exchange appears as a two-color cycle exchange, simultaneously in the matroid and its dual.

Each word therefore records the ordered partition \((B,E\setminus B),\) placing the matroid and its dual in the two color classes.

#Colored matroids

We now generalize this set-partition viewpoint. Instead of dividing \(E\) into a basis and its complement, we divide it into an ordered list of \(k\) color classes. Their sizes remain fixed, but no single class determines all the others. The exchange rule must therefore move several colors compatibly.

Fix colors \(1,\dotsc,k\) and nonnegative integers \(r_1,\dotsc,r_k\) with sum \(n.\) We represent an ordered partition of \([n]\) by a word \(u=u_1\dotsm u_n\) that is a permutation of \[1^{r_1}2^{r_2}\dotsm k^{r_k}.\] The symbols are the colors, and we write \[B(u,c)=\{i:u_i=c\}\] for the positions carrying color \(c.\) The tuple \[(B(u,1),\dotsc,B(u,k))\] is the corresponding ordered set partition of \([n].\) For example, \(\mathtt{1213}\) represents \((\{1,3\},\{2\},\{4\})\) for the ordered colors \((1,2,3).\) These words play the role of bases.

#Cyclic exchange

Basis exchange replaces one element of a basis by another. For several color classes, changing one position may force further changes in other classes. Consider the following two words with four colors: \[u=\mathtt{123412},\qquad v=\mathtt{234121}.\] In positions \(1,2,3,4,\) the pairs of symbols are \[(1,2),\qquad(2,3),\qquad(3,4),\qquad(4,1).\] They follow the cycle \(1\to 2\to 3\to 4\to 1.\) Interchanging the entries of \(u\) and \(v\) in these four positions gives the last two rows below.

\(\text{position}\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \( u\) \(1\) \(2\) \(3\) \(4\) \(1\) \(2\) \( v\) \(2\) \(3\) \(4\) \(1\) \(2\) \(1\) \( u'\) \(2\) \(3\) \(4\) \(1\) \(1\) \(2\) \( v'\) \(1\) \(2\) \(3\) \(4\) \(2\) \(1\)

Thus \(u'=\mathtt{234112}\) and \(v'=\mathtt{123421}.\)

Definition (Cyclic exchange).

In general, let \(u,v\) be two permutations of \(1^{r_1}\dotsm k^{r_k}.\) A cyclic exchange consists of distinct positions \(i_1,\dotsc,i_m,\) where \(m\geq 2,\) and distinct colors \(c_1,\dotsc,c_m\) such that \[\begin{aligned} (u_{i_1},v_{i_1})&=(c_1,c_2),\\ (u_{i_2},v_{i_2})&=(c_2,c_3),\\ &\ \vdots\\ (u_{i_m},v_{i_m})&=(c_m,c_1). \end{aligned}\] We interchange \(u_{i_j}\) and \(v_{i_j}\) for every \(j,\) leaving all other positions unchanged. The resulting words are again permutations of \(1^{r_1}\dotsm k^{r_k}.\)

Definition (Colored matroids).

A colored matroid is a nonempty family \(\mathcal F\) of words, each a permutation of \(1^{r_1}\dotsm k^{r_k},\) satisfying symmetric cycle exchange: for every \(u,v\in\mathcal F\) and every position \(i\) with \(u_i\ne v_i,\) there is a cyclic exchange containing \(i\) such that both resulting words belong to \(\mathcal F.\)

This generalizes symmetric basis exchange by allowing the compensating changes to pass through several colors.

The condition is imposed at every position where the two words differ, and both resulting words must belong to \(\mathcal F.\) With two colors, a cyclic exchange uses two positions and recovers ordinary matroid exchange. With three colors, it uses either two or three positions.

Proposition (Two colors).

Let \(\mathcal F\) be a nonempty family of binary words with \(r\) symbols \(1\) and \(n-r\) symbols \(0.\) Then \(\mathcal F\) is a colored matroid if and only if there is a rank-\(r\) matroid \(M\) on \([n]\) such that \[\mathcal F =\{u\in\{0,1\}^n:B(u,1)\in\mathcal B(M)\}.\] Under this correspondence, the color-\(1\) classes are the bases of \(M,\) and the color-\(0\) classes are the bases of \(M^*.\)

Proof

Suppose first that \(\mathcal F\) is a colored matroid. Take \(u,v\in\mathcal F\) and \(e\in B(u,1)\setminus B(v,1).\) With two colors, a cyclic exchange containing \(e\) uses one further position \(f\in B(v,1)\setminus B(u,1).\) The resulting word in \(\mathcal F\) has color-\(1\) class \[(B(u,1)\setminus\{e\})\cup\{f\}.\] Thus the color-\(1\) classes satisfy basis exchange. They all have cardinality \(r,\) so they are the bases of a matroid \(M.\) Since \(B(u,0)=[n]\setminus B(u,1),\) the color-\(0\) classes are the bases of \(M^*.\)

Conversely, let \(M\) be a matroid on \([n]\) and form \(\mathcal F\) by assigning color \(1\) to the elements of a basis and color \(0\) to the remaining elements. Take \(u,v\in\mathcal F\) and a position \(e\) where they disagree. After interchanging \(u\) and \(v\) if needed, we may assume that \(e\in B(u,1)\setminus B(v,1).\) The symmetric basis-exchange theorem gives an \(f\in B(v,1)\setminus B(u,1)\) such that both \[(B(u,1)\setminus\{e\})\cup\{f\} \qquad\text{and}\qquad (B(v,1)\setminus\{f\})\cup\{e\}\] are bases of \(M.\) Exchanging positions \(e\) and \(f\) between the two words gives two words in \(\mathcal F.\) Hence \(\mathcal F\) is a colored matroid.

Proposition (Color projections).

Let \(\mathcal F\) be a colored matroid and fix a color \(c.\) Then \[\defin{\mathcal B_c}=\{B(u,c):u\in\mathcal F\}\] is the set of bases of a rank-\(r_c\) matroid on \([n].\)

Proof

The family \(\mathcal B_c\) is nonempty, and each of its members has cardinality \(r_c.\) Take \(X,Y\in\mathcal B_c\) and \(e\in X\setminus Y,\) and choose \(u,v\in\mathcal F\) such that \(X=B(u,c)\) and \(Y=B(v,c).\) In a cyclic exchange containing \(e,\) the pair at \(e\) starts with \(c.\) The cycle returns to \(c\) at a position \(f\) whose pair ends with \(c.\) Hence \(f\in Y\setminus X.\)

Let \(u'\) be the word obtained from \(u\) by this exchange. Since the colors in the cycle are distinct, the exchange removes \(e\) from the color-\(c\) positions and adds \(f.\) Therefore \[B(u',c)=(X\setminus\{e\})\cup\{f\}.\] Symmetric cycle exchange gives \(u'\in\mathcal F,\) so \(B(u',c)\in\mathcal B_c.\) Thus \(\mathcal B_c\) satisfies basis exchange.

#Examples with three or more colors

Example (A 3-matroid on five elements).

Consider the family \[\mathcal F=\{\mathtt{12312},\mathtt{12321}, \mathtt{23112},\mathtt{23121}\}.\] Each word is obtained by choosing either \(\mathtt{123}\) or \(\mathtt{231}\) in positions \(1,2,3,\) and independently choosing either \(\mathtt{12}\) or \(\mathtt{21}\) in positions \(4,5.\) A disagreement belongs to one of these two blocks, and exchanging that block produces two words in \(\mathcal F.\) Hence \(\mathcal F\) is a 3-matroid.

Take \(u=\mathtt{12312}\) and \(v=\mathtt{23121}.\) The words differ on both blocks. For the prescribed position \(1,\) exchange positions \(1,2,3\):

\(\text{position}\) \(1\) \(2\) \(3\) \(4\) \(5\) \( u\) \(1\) \(2\) \(3\) \(1\) \(2\) \( v\) \(2\) \(3\) \(1\) \(2\) \(1\) \( u'\) \(2\) \(3\) \(1\) \(1\) \(2\) \( v'\) \(1\) \(2\) \(3\) \(2\) \(1\)

Thus \(u'=\mathtt{23112}\) and \(v'=\mathtt{12321}\); neither is one of the two original words.

Example (A 3-matroid on eight elements).

The same block construction gives a larger example. Let \(E=[8],\) and consider permutations of \(1^3 2^3 3^2.\) On the positions \(\{1,2,3\}\) choose either \(\mathtt{123}\) or \(\mathtt{231},\) on \(\{4,5,6\}\) choose either \(\mathtt{123}\) or \(\mathtt{231},\) and on \(\{7,8\}\) choose either \(\mathtt{12}\) or \(\mathtt{21}.\) Taking all eight choices gives the following family. The three color columns record each ordered partition. \[\begin{array}{c|c|c|c} \text{word}&\text{Color }1&\text{Color }2&\text{Color }3\\ \hline \mathtt{12312312}&\{1,4,7\}&\{2,5,8\}&\{3,6\}\\ \mathtt{12312321}&\{1,4,8\}&\{2,5,7\}&\{3,6\}\\ \mathtt{12323112}&\{1,6,7\}&\{2,4,8\}&\{3,5\}\\ \mathtt{12323121}&\{1,6,8\}&\{2,4,7\}&\{3,5\}\\ \mathtt{23112312}&\{3,4,7\}&\{1,5,8\}&\{2,6\}\\ \mathtt{23112321}&\{3,4,8\}&\{1,5,7\}&\{2,6\}\\ \mathtt{23123112}&\{3,6,7\}&\{1,4,8\}&\{2,5\}\\ \mathtt{23123121}&\{3,6,8\}&\{1,4,7\}&\{2,5\} \end{array}\]

This family satisfies symmetric cycle exchange. A position where two words differ belongs to one of the three displayed blocks. On a three-position block, the pairs of symbols form the cycle \(1\to 2\to 3\to 1\) or its reverse; on the last block they form \(1\to 2\to 1.\) Exchanging the positions in that block changes one allowed choice into the other, so both resulting words remain in the family.

Here is one exchange in full. Take \(u=\mathtt{12312312}\) and \(v=\mathtt{23123112},\) and prescribe position \(1.\) At positions \(1,2,3\) the pairs of symbols form a three-cycle. Interchanging the highlighted columns gives

\(\text{position}\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \(8\) \( u\) \(1\) \(2\) \(3\) \(1\) \(2\) \(3\) \(1\) \(2\) \( v\) \(2\) \(3\) \(1\) \(2\) \(3\) \(1\) \(1\) \(2\) \( u'\) \(2\) \(3\) \(1\) \(1\) \(2\) \(3\) \(1\) \(2\) \( v'\) \(1\) \(2\) \(3\) \(2\) \(3\) \(1\) \(1\) \(2\)

Thus \(u'=\mathtt{23112312}\) and \(v'=\mathtt{12323112},\) both of which belong to \(\mathcal F.\)

Here are two other exchanges in this family.

  • For the two words in the displayed exchange, if position \(4\) is prescribed, we switch positions \(4,5,6\) and obtain the same two resulting words in the opposite order.

  • The words \(\mathtt{12312312}\) and \(\mathtt{23123121}\) differ on all three blocks. For the prescribed position \(7,\) switching positions \(7,8\) gives \(\mathtt{12312321}\) and \(\mathtt{23123112}.\) For the prescribed position \(1,\) switching positions \(1,2,3\) gives \(\mathtt{23112312}\) and \(\mathtt{12323121}.\)

Example (A switch inside a larger family).

Consider the family \[\mathcal F=\{\mathtt{1123},\mathtt{1213},\mathtt{1321}, \mathtt{2113},\mathtt{3121},\mathtt{2311},\mathtt{3211}\}.\] Take \(u=\mathtt{2311}\) and \(v=\mathtt{1123}.\) At positions \(1\) and \(3,\) the pairs of symbols are \((2,1)\) and \((1,2).\) Interchanging those positions gives \[u'=\mathtt{1321},\qquad v'=\mathtt{2113},\] which are again members of \(\mathcal F.\) Unlike the previous example, the resulting words are different from the original two words.