论文标题
彩虹和单色电路以及二进制曲线的切割
Rainbow and monochromatic circuits and cuts in binary matroids
论文作者
论文摘要
鉴于矩阵以及其地面套件的着色，如果没有两个元素具有相同的颜色，则其元素的一部分被称为彩虹颜色。我们表明，如果等级$ r $的二进制矩阵颜色恰好是$ r $颜色，则$ m $要么包含彩虹色电路或单色切割。由于二进制型矩阵的类别是在二进制下关闭的，因此这立即意味着，如果$ m $恰好用$ n-r $颜色颜色，则$ m $要么包含彩虹彩色切割或单色电路。作为副产品，我们从分区矩阵的减少方面给出了二元基矩阵的特征。 在Bérczi等人的猜想中，我们还分析了二进制矩阵的覆盖数量与最大颜色数量或无彩虹无电路色彩的最大颜色尺寸或最大尺寸之间的关系。对于简单的图形矩阵，我们表明存在一种无彩虹电路的着色，只有在图形为$（2,3）$ - 稀疏时，它最多只能使用每种颜色两次，也就是说，它在$ 2 $维的刚性刚度刚度刚度均可矩阵中是独立的。此外，我们给出了承认这种着色的最小刚性图的完整表征。
Given a matroid together with a coloring of its ground set, a subset of its elements is called rainbow colored if no two of its elements have the same color. We show that if a binary matroid of rank $r$ is colored with exactly $r$ colors, then $M$ either contains a rainbow colored circuit or a monochromatic cut. As the class of binary matroids is closed under taking duals, this immediately implies that if $M$ is colored with exactly $n-r$ colors, then $M$ either contains a rainbow colored cut or a monochromatic circuit. As a byproduct, we give a characterization of binary matroids in terms of reductions to partition matroids. Motivated by a conjecture of Bérczi et al., we also analyze the relation between the covering number of a binary matroid and the maximum number of colors or the maximum size of a color class in any of its rainbow circuit-free colorings. For simple graphic matroids, we show that there exists a rainbow circuit-free coloring that uses each color at most twice only if the graph is $(2,3)$-sparse, that is, it is independent in the $2$-dimensional rigidity matroid. Furthermore, we give a complete characterization of minimally rigid graphs admitting such a coloring.
