31. SEG Workshop "Kombinatorik, Graphentheorie und Algorithmen"

Am 04. Februar 2026, ab 15:00 Uhr laden wir Sie herzlich zum 31. SEG Workshop "Kombinatorik, Graphentheorie und Algorithmen" ein. Wir treffen uns im Seminarraum C46.638, Reichenhainer Straße 39, 09126 Chemnitz.

Nach den Vorträgen ist ein gemeinsames Abendessen im Turmbrauhaus, Neumarkt 2, 09111 Chemnitz, geplant.

Wir freuen uns auf Ihre Teilnahme.
Ihre Arbeitsgruppe Algorithmische und Diskrete Mathematik.

Kontakt: kurt.klement.gottwald@math.tu-chemnitz.de oder sebastian.debus@math.tu-chemnitz.de

Zur Registrierung senden Sie uns bitte bis zum 25.01.2026 eine E-Mail mit der Angabe, ob Sie einen Vortrag halten möchten und ob Sie beim Abendessen teilnehmen.

Programm

Abstracts

Speed and size of dominating sets in domination games, Yannick Mogge

We consider Maker-Breaker domination games, a variety of positional games, in which two players (Dominator and Staller) alternately claim vertices of a given graph. Dominator's goal is to fully claim all vertices of a dominating set, while Staller tries to prevent Dominator from doing so, or at least tries to delay Dominator's win for as long as possible.
We prove a variety of results about domination games, including the number of turns Dominator needs to win and the size of a smallest dominating set that Dominator can occupy. We also show that speed and size can be arbitrarily far apart, and we prove further non-intuitive statements about the general behaviour of such games.

A Ramsey theorem for matroids representable over a given finite field, Matthew Eliot Kroeker

In this talk I will present on the following characterization of the “unavoidable flats” in matroids representable over a given finite field: for a finite field F and positive integer k, every simple F-representable matroid of sufficiently high rank contains a rank-k flat which is either independent, or a projective or affine geometry.  As a corollary, we get the following Ramsey theorem: given an F-representable matroid of sufficiently high rank and any two-colouring of its points, there is a monochromatic rank-k flat.

Diameter-2-Graphs, 3-Colorability, and a colorful version of VC dimension, Dominik Scheder

Given a graph of diameter 2, is it 3-colorable? The computational complexity of this problem is open. In this ongoing joint work with Christoph Brause I will present some ideas, results, and conjectures tying this question to a coloring notion of VC dimension. 

Locally positive semidefinite matrices, Sebastian Debus

A real symmetric matrix of size n is called d-locally positive semidefinite if all its principal submatrices of size d are positive semidefinite. We study the geometry of the set of eigenvalue vectors arising from such matrices. We present several equivalent optimization problems which solutions shed light into the geometry. 
This is joint work with Jose Acevedo, Greg Blekherman and Cordian Riener.