Representability of Matroids by c-Arrangements is Undecidable

DOI10.1007/S11856-022-2345-ZMaRDI QIDQ6331015arXivFDO

Authors Lukas Kühne, Geva Yashfe

Publication date 12 December 2019

Published in arXiv

Full work available at URL https://doi.org/10.1007/S11856-022-2345-Z

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Graph representations (geometric and intersection representations, etc.) (05C62) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40)

arXiv classification

math.CO

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.

This page was built for publication: Representability of Matroids by c-Arrangements is Undecidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6331015)