Springe direkt zu Inhalt

Colloquium by Lukas Kühne (Hebrew University of Jerusalem): Matroid representations by c-arrangements are undecidable

Jan 06, 2020 | 04:00 PM s.t.

A matroid  is a combinatorial object based on an abstraction of linear independence in vector spaces and forests in graphs. It is a classical question to determine whether a given matroid is representable as a vector configuration over a field. Such a matroid is called linear.

This talk is about a generalization of that question from vector configurations to c-arrangements.
A c-arrangement for a fixed c is an arrangement of dimension c subspaces such that the dimensions of their sums are multiples of c. Matroids representable as c-arrangements are called multilinear matroids.

We prove that it is algorithmically undecidable whether there exists a c such that a given matroid has a c-arrangement representation. In the proof, we introduce a non-commutative von Staudt construction to encode an instance of the uniform word problem for finite groups in matroids of rank three.

The talk is based on joint work with Geva Yashfe.

Time & Location

Jan 06, 2020 | 04:00 PM s.t.

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
Room 005 (Ground Floor)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)