Staying close in theme to last month’s post, this month I’m writing about decomposing matroids into independent sets.<\/p>\n\n\n\n
The colouring number (or covering number), $\\text{col}(M)$ of a matroid $M$ is defined as the smallest $t$ for which the ground set of $M$ can be partitioned into $t$ independent sets. I’ve written before<\/a> about how I like the term colouring number since it highlights the analogy with the chromatic number of graphs<\/a> (which is the smallest number of vertex-independent sets in which the graph can be partitioned). For this blog post, though, it is more illuminating to compare the colouring number to the edge-chromatic number of a graph.<\/p>\n\n\n\n The chromatic number for graphs has many variations that are studied for their own sake, such as the list-chromatic number<\/a>. Similarly, there is a list-colouring version of the colouring number, which is defined as follows.<\/p>\n\n\n\n Definition.<\/strong> Let $M$ be a loopless matroid, and suppose that for each element $e$ of $M$ we are given a list $L(e)$ of colours available to element $e$. An $L$-colouring of $M$ is a function $c$ that maps each element $e$ of $M$ to an element of $L(e)$, with the additional property that $c^{-1}(i)$ is an independent set of $M$ for all $i \\in \\bigcup_{e} L(e)$. The matroid $M$ is $k$-list-colourable if it has an $L$-colouring whenever $|L(e)| \\ge k$ for each $e$. We write $\\text{col}_\\ell(M)$ for the smallest $k$ such that $M$ is $k$-list-colourable.<\/p>\n\n\n\n When $L(e) = \\{1,2,\\ldots,k\\}$ for each $e$, $L$-colouring corresponds to colouring the matroid with $k$ colours. This implies that $\\text{col}_\\ell(M) \\ge \\text{col}(M)$. For graphs the gap between chromatic number and list-chromatic number can be arbitrarily large. Surprisingly, the colouring and list-colouring numbers for matroids are equal, as shown by Seymour<\/a> (using an application of matroid union!).<\/p>\n\n\n\n Theorem (Seymour).<\/strong> $\\text{col}_\\ell(M) = \\text{col}(M)$ for all loopless matroids $M$.<\/p>\n\n\n\n It is clear from this theorem that nothing is to be gained by considering the list-colouring problem for matroids instead of the colouring problem.<\/p>\n\n\n\n However, it is not known if an analogue of Seymour’s result holds for matroid intersections. Let $M_1$ and $M_2$ be two matroids on a common ground set $E$. The colouring number $\\text{col}(M_1 \\wedge M_2)$ is the smallest $t$ for which $E$ can be partitioned into $k$ sets that are independent in both $M_1$ and $M_2$ (here, $M_1 \\wedge m_2$ refers to the matroid intersection of $M_1$ and $M_2$). The list-colouring number for $\\chi_\\ell(M_1 \\wedge M_2)$ is similarly obtained as a generalisation of the list-colouring number for matroids.<\/p>\n\n\n\n As in the case of (list-)colouring matroids, a straightforward argument shows that $\\text{col}_\\ell(M_1 \\wedge M_2) \\ge \\text{col}(M_1 \\wedge M_2)$, but it is not known if equality holds for all matroid intersections.<\/p>\n\n\n\n A 1-partition matroid is a matroid whose ground set can be partitioned into subsets such that the independent sets of the matroid contain at most one element from each of the subsets. In other words, a loopless matroid $M$ is a 1-partition matroid if and only if it is the direct sum of $r(M)$ parallel classes.<\/p>\n\n\n\n Such matroids arise naturally in matching theory. A bipartite graph $G$ with bipartition $L \\cup R$ comes with two 1-partition matroids on $E$: one in which the parallel classes are formed by the edges incident with each of the vertices in $L$, and one whose parallel classes similarly correspond to the vertices in $R$. In fact, the matchings of $G$ are precisely the common independent sets of these two matroids.<\/p>\n\n\n\n Galvin showed<\/a> that the list-edge-chromatic number and the edge-chromatic number of bipartite graphs coincide, which is equivalent to the following result.<\/p>\n\n\n\n Theorem (Galvin).<\/strong> $\\text{col}_\\ell(M_1 \\wedge M_2) = \\text{col}(M_1 \\wedge M_2)$ for all loopless 1-partition matroids.<\/p>\n\n\n\n It is natural to ask if the conclusion of the theorem still holds when the 1-partition matroids are replaced by matroids that are the direct sum of uniform matroids whose rank may be larger than 1 (such matroids are called partition matroids). It turns out that the answer is ‘yes’, a result that was proved only a few months ago by Guo<\/a>.<\/p>\n\n\n\n Theorem (Guo).<\/strong> $\\text{col}_\\ell(M_1 \\wedge M_2) = \\text{col}(M_1 \\wedge M_2)$ for all loopless partition matroids.<\/p>\n\n\n\n In light of Seymour’s theorem for the list-colouring number of matroids and the above results by Galvin and Guo, it is tempting to ask whether the list-colouring number is always equal to the colouring number for matroid intersections \u2013 as Kir\u00e1ly did<\/a>.<\/p>\n\n\n\n Question (Kir\u00e1ly).<\/strong> Is it always true that $\\text{col}_\\ell(M_1 \\wedge M_2) = \\text{col}(M_1 \\wedge M_2)$?<\/p>\n\n\n\n Very little appears to be known about this problem, with the exception of the results by Galvin and Guo and the following result by Kir\u00e1ly and Pap<\/a>.<\/p>\n\n\n\n Theorem (Kir\u00e1ly and Pap).<\/strong> $\\text{col}_\\ell(M_1 \\wedge M_2) = \\text{col}(M_1 \\wedge M_2)$ in each of the following cases:<\/p>\n (The third case of of their result actually extends to the situation where $M_1$ is a rank-2 matroid and $M_2$ is an arbitrary matroid.)<\/p>\n\n\n\n As a step towards resolution of Kir\u00e1ly’s question, the following problem may be more accessible:<\/p>\n\n\n\n Question.<\/strong> Is it true that $\\text{col}_\\ell(M_1 \\wedge M_2) = \\text{col}(M_1 \\wedge M_2)$ for all loopless rank-3 matroids $M_1$ and $M_2$?<\/p>\n","protected":false},"excerpt":{"rendered":" Colouring and list-colouring Staying close in theme to last month’s post, this month I’m writing about decomposing matroids into independent sets. The colouring number (or covering number), $\\text{col}(M)$ of a matroid $M$ is defined as the smallest $t$ for which … Continue reading 1-partition matroids and Galvin’s theorem<\/h1>\n\n\n\n
When is $\\text{col}_\\ell(M_1 \\wedge M_2) = \\text{col}(M_1 \\wedge M_2)$?<\/h1>\n\n\n\n
\n