Jochen Harant, TU Ilmenau: On the independence number in subcubic graphs

For a connected subcubic graph $G\neq K_1$ let $V_i(G) = \{v \in V(G) ~|~ d_G(v)=i\}$ for $1 \leq i \leq 3.$ Given $c_1, c_2, c_ 3 \in \mathbb{R}^+$ and $ d \in \mathbb{R}$, we show several results of type $\alpha(G) \geq c_1|V_1(G)| + c_2|V_2(G)| + c_3|V_3(G)| - d.$ We also derive classes of graphs $G$ showing sharpness of these lower bounds on the independence number $\alpha(G)$ of $G$.

William Joseph Turner, TU Freiberg: A graph minors approach to temporal sequences

This work investigates an analogue of planarity for sequences of graphs. We develop a structural approach to determining the simultaneous embeddability of temporal sequences. We identify five classes of obstruction to simultaneous embeddability and show that every temporal sequence of 2-connected graphs is either simultaneously embeddable or admits a sequence of improvements leading to an obstruction. Furthermore, the assumption of 2-connectivity is necessary since without it the problem becomes NP-hard.

Peter Tittmann, HS Mittweida: Graph Polynomials and Local Graph Operations

This presentation provides an overview of local graph operations, recursions and reductions that are used when computing graph polynomials. It also presents a list of new results, including new local graph operations and their applications, as well as recursive relations for known graph polynomials. Furthermore, it defines more general graph polynomials, which allow the derivation of new recursions for domination, edge cover, acyclic and covered component polynomials. Graph polynomials are considered as generating functions for sequences of the number of certain (induced, spanning, or general) subgraphs of a graph. A local graph operation assigns to any graph $G$ another graph $H$ such that $G$ and $H$ differ only in the neighborhood of a vertex or an edge. Local graph operations occur in recursive relations for graph polynomials. They also form the basis for graph reductions. This contribution is partly a review of graph polynomials and local graph operations, but also contains some new results and open problems.

Sebastian Debus, TU Chemnitz: The wonderful geometry of the Vandermonde map

We investigate the image of a probability simplex under a map consisting of power sum polynomials. This Vandermonde cell is clearly not a polytope, but we show that it has the combinatorial type of a cyclic polytope. By letting the number of variables tend to infinity, we obtain an image at infinity that has the combinatorial type of a cyclic polytope with infinitely many facets. This is based on joint work with Jose Acevedo, Greg Blekherman and Cordian Riener.

Thomas Jahn, FSU Jena: Minkowski chirality: a measure of reflectional asymmetry of convex bodies

For triangles and parallelograms, we quantify their asymmetry with respect to reflections across straight lines. To do so, we compute the minimal dilation factor which is needed to cover the triangle/parallelogram by a translate of any of its mirror images, dilated by that factor. In the first part of the talk, I am going to present the brute-force algorithmic approach (i.e., solving thousands of linear optimization problems) that led us to our hypotheses on what the optimal reflection axes and dilation factors are. In the second part, I am going to discuss the combinatorial aspects of the analytic proofs which emerge from optimization theory. This is joint work with Andrei Caragea, Katherina von Dichter, Kurt Klement Gottwald, Florian Grundbacher, and Mia Runge.

Johannes Tantow, TU Chemnitz: Finding locally optimal bitstrings under permutations

We are given a bit string and a set of permutations. We can apply a permutation to the bit positions and obtain a new string. We are interested in finding a bitstring that is generated by applying these permutations such that no application of a permutation creates a lexicographically smaller string. Such a string must always exist and this is therefore a total search problem. We show PLS-completeness for the general case. Open problems are the Abelian case and the case where the number of permutations is constant.

Thomas Böhme, TU Ilmenau: Nash Equilibria and Associated Games

We consider $n$-player games in strategic form and examine cases where the Nash equilibrium fails to provide a convincing prediction of player behavior. Well-known examples—such as Basu's Traveler's Dilemma and a two-player game introduced by Aumann and Maschler illustrate how equilibria can be both unintuitive and fragile. In the latter case, the game has a unique mixed-strategy equilibrium in which both players receive their maxmin payoffs; yet, paradoxically, neither player's equilibrium strategy guarantees this outcome, while some non-equilibrium strategies do. In this talk, we propose a refinement of strategic reasoning based on the idea of associated games, in which each player evaluates a strategy profile by considering only rational (i.e., self-improving) deviations by others. This framework yields payoff profiles that are often more robust and strategically plausible than standard equilibria. We illustrate how this approach explains behavior in repeated and one-shot games where traditional equilibrium analysis falls short.