Frank Sottile - Texas A&M University

Polytopes and Polynomial Systems

Abstract: The exponent of a monomial involving n variables is an integer vector in Z^n. The set of exponents in a polynomial in n variables is its support, and their convex hull is its Newton polytope. Many questions and answers concerning zeroes of multivariate polynomials are best expressed in terms of the discrete structures of support and Newton polytope. The same is true for algorithms and constructions involving multivariate polynomials.

In this talk for a general audience from discrete mathematics, I will explain some of this relation between polynomials and polytopes, and give examples of how these structures are used to answer questions involving zeroes of multivariate polynomials.

Colloquium - 16:00

Stephan Kreutzer - Humboldt-Universität zu Berlin

DAG-Width and Parity Games

Abstract: Tree-width is a well-known metric on undirected graphs that measures how tree-like a graph is and gives a notion of graph decomposition that proves useful in algorithm development. Tree-width is characterised by a game known as the cops-and-robber game where a number of cops chase a robber on the graph. We consider the natural adaptation of this game to directed graphs and show that monotone strategies in the game yield a measure with an associated notion of graph decomposition that can be seen to describe how close a directed graph is to a directed acyclic graph (DAG). This promises to be useful in developing algorithms on directed graphs. In particular, we show that the problem of determining the winner of a parity game is solvable in polynomial time on graphs of bounded DAG-width. We also consider the relationship between DAG-width and other measures such as entanglement and directed tree-width. One consequence we obtain is that certain NP-complete problems such as Hamiltonicity and disjoint paths are polynomial-time computable on graphs of bounded DAG-width.