26. SEG Workshop "Kombinatorik, Graphentheorie und Algorithmen"

Am 17. Januar 2023, ab 15:30 Uhr laden wir Sie herzlich zum 26. SEG Workshop "Kombinatorik, Graphentheorie und Algorithmen" ein. Wir treffen uns im Hörsaal 2/N101 (Orangerie), Reichenhainer Straße 90, 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: tobias.hofmann@math.tu-chemnitz.de

Programm

Abstracts

Fractal Penrose Rhombs, Dr. Frank Göring
The talk is concerned with the construction of various fractal versions of Penrose rhombs using those IFS graphs that yield the Penrose rhomb tiling. In particular, the construction of the IFS graphs from the original tiling will be discussed.

3-Colourability and Diamonds, Prof. Dr. Ingo Schiermeyer
The 3-colourability problem is an NP-complete problem which remains NP-complete for claw-free graphs and for graphs with maximum degree four. In this talk we will consider induced subgraphs, among them are the claw (K_1,3), the bull (a triangle with two pendent edges), and the diamond (the graph K₄-e). Our main result is a complete characterization of all 3-colourable (claw,bull)-free graphs. We will present a description of all non 3-colourable (claw,bull)-free graphs in terms of diamonds. Moreover, we will show extensions of this characterization to larger graph classes by taking supergraphs of the claw or the bull.

Convexification of Bilinear and Multilinear Functions, Prof. Dr. Thomas Kalinowski
We consider the problem of constructing convex relaxations for sets that can be described by bilinear polynomials. This is relevant, for instance, in blending and pooling problems, and due to the large scale of the problems that have to be solved in practice, it is crucial to have strong relaxations that can be computed efficiently. The combinatorial structure of such a bilinear polynomial can be represented by its co-occurence graph where the vertices correspond to the variables and the edges to products of two variables that occur in the function with a non-zero coefficient. We demonstrate how in some cases the graph structure can be used to derive convex hull characterizations. The proofs make use of an intuitive geometric method proposed by Zuckerberg in 2016. We extend the idea to multilinear functions, where we have to use hypergraphs instead of graphs to represent the structure of the function. In this context we obtain simpler proofs and stronger variants of some recent decomposition results.

The Frustration Dimension of a Graph, Dr. Uwe Schwerdtfeger
We provide a new minor monotone graph parameter called the frustration dimension. It is based on an embedding problem for signed graphs. We provide forbidden minor characterizations for graphs of small frustration dimension.

Non-Rectangular Convolutions and (Sub-)Cadences with Three Elements, Julian Pape-Lange
The discrete acyclic convolution is an operation that takes two vectors a and b of length n and calculates the 2n + 1 sums of the form a_i · b_k-i. It is well-known that the convolution can be calculated by fast Fourier transform or fast number theoretic transform in O(n log n) operations. For a given convex polygon P, we can similarly calculate the non-zero sums of the form a_i · b_k-i over all pairs (a_i, b_k-i) inside the polygon. We prove that if P has k vertices and perimeter p, this non-rectangular convolution only needs O(k + p(log p)² log k) operations. We also show that the non-rectangular convolution can be used to efficiently count the number of a string pattern called 3-cadence. A 3-cadence is an arithmetic subsequence {i, i + d, i + 2d} corresponding to equal letters such that both i - d and i + 3d are no valid indices of the underlying string.