You are cordially invited to our next Monday Lecture &
Colloquium on January 14th at 14:15 h & 16:00 h at FU Berlin.
Location: Freie Universität Berlin Takustr. 9 14195 Berlin Time: Monday, January 14th - 14:15 h Lecture: Penny Haxell (University of Waterloo) Title: Algorithms for independent transversals vs.
small dominating sets An independent transversal (IT) in a vertex-partitioned graph G
is an independent set in G consisting of one vertex in each
partition class. There are several known criteria that guarantee
the existence of an IT, of the following general form: the graph
G has an IT unless the subgraph GS of G, induced by the union of
some subset S of vertex classes, has a small dominating set.
These criteria have been used over the years to solve many
combinatorial problems. The known proofs of these IT theorems do
not give efficient algorithms for actually finding an IT or a
subset S of classes such that GS has a small dominating set.
Here we present appropriate weakenings of such results that do
have effective proofs. These result in algorithmic versions of
many of the original applications of IT theorems. We will
discuss a few of these here, including hitting sets for maximum
cliques, circular edge colouring of bridgeless cubic graphs, and
hypergraph matching problems. Coffee & Tea Break Room 134 Time: Monday, January 14th - 16:00 h s.t. Colloquium: Carlos Amendola (Technische Universität München) Title: Max-Linear Graphical Models via Tropical
Geometry Motivated by extreme value theory, max-linear graphical models have been recently introduced and studied as an alternative to the classical Gaussian or discrete distributions used in graphical modeling. We present max-linear models naturally in the framework of tropical geometry. This perspective allows us to shed light on some known results and to prove others with algebraic techniques. In particular, we rephrase parameter estimation for max-linear models in terms of cones in the tropical eigenspace fan. This is joint work with Claudia Klüppelberg, Steffen Lauritzen and Ngoc Tran. |