Representability of Matroids by c-Arrangements is Undecidable

Abstract

For a natural number $c$, a $c$-arrangement is an arrangement of dimension $c$ subspaces satisfying the following condition: the sum of any subset of the subspaces has dimension a multiple of $c$. Matroids arising as normalized rank functions of $c$-arrangements are also known as multilinear matroids. We prove that it is algorithmically undecidable whether there exists a $c$ such that a given matroid has a $c$-arrangement representation, or equivalently whether the matroid is multilinear. It follows that certain network coding problems are also undecidable. In the proof, we introduce a generalized Dowling geometry to encode an instance of the uniform word problem for finite groups in matroids of rank three. The $c$-arrangement condition gives rise to some difficulties and their resolution is the main part of the paper.

Improved exposition and added application to network coding

Cited by in corpus (2)

• Undecidability of Network Coding, Conditional Information Inequalities, and Conditional Independence Implication
• Von Staudt Constructions for Skew-Linear and Multilinear Matroids