Clonal cores and flexipaths in matroids

Abstract

A partitioned matroid $(M,\{X_1,X_2,\dots ,X_n\})$ consists of a matroid $M$ and a partition $\{X_1,X_2,\dots ,X_n\}$ of its ground set. As such structures arise frequently in structural matroid theory, this paper introduces a general technique for analyzing those special properties of partitioned matroids that depend solely on the values of the connectivities $\hat{I}»(X_i)$, the local connectivities $\sqcap ({\cup }_{j\in J}{X}_j,{\cup }_{k\in K}{X}_k,)$, and the dual local connectivities ${\sqcap }^{\ast }({\cup }_{h\in H}{X}_h,{\cup }_{g\in G}{X}_g)$. In particular, we consider those partitioned matroids in which each $X_i$ is an independent, coindependent set of clones of cardinality $\hat{I}»(X_i)$. Calling such partitioned matroids clonal-core matroids, we show that special results of the above type for partitioned matroids can be verified in general by proving them just for clonal-core matroids. Aiming at the long-term goal of finding the unavoidable minors of $4$-connected matroids, we illustrate this technique by studying $4$-paths. These are sequences $(L,P_1,P_2,\dots ,P_n,R)$ of sets that partition the ground set of a matroid so that the union of any proper initial segment of parts is $4$-separating. Viewing the ends $L$ and $R$ as fixed, we call such a partition a $4$-flexipath if $(L,Q_1,Q_2,\dots ,Q_n,R)$ is a $4$-path for all permutations $(Q_1,Q_2,\dots ,Q_n)$ of $(P_1,P_2,\dots ,P_n)$. A straightforward simplification enables us to focus on $(4,c)$-flexipaths for some $c$ in $\{1,2,3\}$, that is, those $4$-flexipaths for which $\hat{I}»(Q_i)=c$ and $\hat{I}»(Q_i\cup Q_j)>c$ for all distinct $i$ and $j$. Our main result for $4$-paths is that the only non-trivial case that arises here is when $c=2$. In that case, there are essentially only two possible dual pairs of $(4,c)$-flexipaths when $n\ge 5$.

42 pages, 3 figures