[Facets-of-complexity] Invitation to Monday Lecture & Colloquium - January 14th 2019

[Ita Brunke <i.brunke@inf.fu-berlin.de>]

You are cordially invited to our next Monday Lecture & Colloquium on January 14th at 14:15 h & 16:00 h at FU Berlin.

Location:

Room 005 - Ground Floor
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

Abstract:

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

Abstract:
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.