BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: A matroid is a combinatorial object based on an abstraction o
f linear independence in vector spaces and forests in graphs. It is a class
ical question to determine whether a given matroid is representable as a ve
ctor configuration over a field. Such a matroid is called linear. This tal
k is about a generalization of that question from vector configurations to
c-arrangements. A c-arrangement for a fixed c is an arrangement of dimensio
n c subspaces such that the dimensions of their sums are multiples of c. Ma
troids 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. T
he talk is based on joint work with Geva Yashfe.
DTSTAMP:20191202T145400
DTSTART:20200106T160000
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9
\n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:Lukas Kühne (Hebrew University of Jerusalem): Matroid representatio
ns by c-arrangements are undecidable
UID:95692836@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20200106-C-Kuehne.html
END:VEVENT
END:VCALENDAR