Combinatorics: Lukas Kuhne (HUJI)

Speaker: Lukas Kuhne (HUJI)

Title:  Matroids doing Algebra


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 addresses generalisations of such representations over division rings or matrix rings which are called skew linear and multilinear matroids respectively. Multilinear matroids also appear in computer science in the context of linear network coding.

I will describe the von Staudt constructions that encode non-commutative equations in matroids. This construction yields a reduction of word problem instances to skew linear or multilinear matroid representations. Furthermore I will present examples of matroids distinguishing these classes based on algebraic phenomena. If time permits I will outline possible extensions of this work to approximate matroid representations and representations coming from entropy functions.

The talk is based on joint work with Rudi Pendavingh and Geva Yashfe.


Mon, 22/06/2020 - 11:00 to 13:00