论文标题
关于分解二进制成型的不可能
On the Impossibility of Decomposing Binary Matroids
论文作者
论文摘要
我们表明，存在$ k $ - 颜色的矩阵，而不是$（b，c）$ - $ b $和$ c $是常数时可分解的。 Matroid为$（b，c）$ - 分解，如果将其元素的接地集划分为集合$ x_1，x_2，\ ldots，x_l $，以及以下两个属性。每组$ x_i $最多都有$ ck $。此外，对于所有集合$ y $，以便$ | y \ cap x_i | \ leq 1 $是$ y $是$ b $ - 颜色的情况。 a $（b，c）$ - 分解是对分区分解的严格概括，因此，我们的结果反驳了从arxiv：1911.10485v2的猜想。
We show that there exist $k$-colorable matroids that are not $(b,c)$-decomposable when $b$ and $c$ are constants. A matroid is $(b,c)$-decomposable, if its ground set of elements can be partitioned into sets $X_1, X_2, \ldots, X_l$ with the following two properties. Each set $X_i$ has size at most $ck$. Moreover, for all sets $Y$ such that $|Y \cap X_i| \leq 1$ it is the case that $Y$ is $b$-colorable. A $(b,c)$-decomposition is a strict generalization of a partition decomposition and, thus, our result refutes a conjecture from arXiv:1911.10485v2 .
