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.

__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. --------------A613DC86E2A4D1F5C56584B8-- From i.brunke@inf.fu-berlin.de Fri Jan 18 16:50:31 2019 Received: from outpost1.zedat.fu-berlin.de ([130.133.4.66]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (envelope-from

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

__Location__**: **

Technische Universität Berlin

Straße des 17. Juni 136

10623 Berlin

__Time__: **Monday, January 21st - 14:15 h**

__Lecture__: Maria Bras Amorós (Universitat Rovira i
Virgili Tarragona**)**

__Title__: On numerical semigroups

A numerical semigroup is a subset of the positive integers (**N**)
together with 0, closed under addition, and with a finite
complement in **N**∪{0}.

The number of gaps is its genus. Numerical semigroups arise
in algebraic geometry, coding theory, privacy models, and in
musical analysis. It has been shown that the sequence counting
the number of semigroups of each given genus *g*,
denoted (*n _{g}*)

We will explain some classical problems on numerical semigroups as well as some of their applications to other fields and we will explain the approach of counting semigroups by means of trees.

**R****oom MA 316 - Third Floor**** [British Reading]
**

__Colloquium__: Torsten Mütze (Technische Universität
Berlin**)**

__Title__: On symmetric chains and Hamilton cycles

The

In this talk I will present several new constructions of SCDs
in the *n*-cube. Specifically, we construct five
pairwise edge-disjoint SCDs in the *n*-cube for all *n*≥90,
and four pairwise orthogonal SCDs for all *n*≥60, where
orthogonality is a slightly stronger requirement than
edge-disjointness. Specifically, two SCDs are called orthogonal
if any two chains intersect in at most a single element, except
the two longest chains, which may only intersect in the unique
minimal and maximal element (the empty set and the full set).
This improves the previous best lower bound of three orthogonal
SCDs due to Spink, and is another step towards an old problem of
Shearer and Kleitman from the 1970s, who conjectured that the *n*-cube
has ⌊*n*/2⌋+1 pairwise orthogonal SCDs.

We also use our constructions to prove some new results on the
central levels problem, a far-ranging generalization of the
well-known middle two levels conjecture (now theorem), on
Hamilton cycles in subgraphs of the (2*n*+1)-cube induced
by an even number of levels around the middle. Specifically, we
prove that there is a Hamilton cycle through the middle four
levels of the (2*n*+1)-cube, and a cycle factor through
any even number of levels around the middle of the (2*n*+1)-cube.

This talk is based on two papers, jointly with Sven Jäger, Petr Gregor, Joe Sawada, and Kaja Wille (ICALP 2018), and with Karl Däubel, Sven Jäger, and Manfred Scheucher, respectively.

You are cordially invited to our last Monday Lecture &
Colloquium for this term on February 11th at 14:15 h & 16:00 h
at FU Berlin.

__Location__**: **

Freie Universität Berlin

Takustr. 9

14195 Berlin

__Time__: **Monday, February 11th - 14:15 h**

__Lecture__: Sergio Cabello (University** of
Ljubljana)**

__Title__: Computational geometry, optimization and Shapley
values

I will discuss three unrelated sets of results combining
geometry and algorithms. First we will see classes of graphs
defined using the intersection of geometric objects in the
plane, and discuss classical optimization problems for them.
Then we will consider approximation algorithms for the potato
peeling problem: find a maximum-area convex body inside a given
polygon. The problem amounts to finding a maximum clique in the
visibility graph of random samples of points inside the polygon,
and results from stochastic geometry are used to bound the size
of the samples. Finally, we will discuss the efficient
computation of Shapley values for coalitional games defined by
the area of usual geometric objects, such as the convex hull or
the minimum axis-parallel bounding box.

__Time__: **Monday, ****February 11th**** -
16:00 h s.t.**

__Colloquium__: Matías Bender (Sorbonne Université Paris**)**

__Title__: Solving sparse polynomial systems using Gröbner
basis

Solving systems of polynomial equations is one of the oldest and most important problems in computational mathematics and has many applications in several domains of science and engineering. It is an intrinsically hard problem with complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. For example, several problems in computer-aided design, robotics, computer vision, molecular biology and kinematics involve polynomial systems that are sparse that is, only a few monomials have non-zero coefficients.

We focus on exploiting the sparsity of the Newton polytopes of the polynomials to solve the systems faster than the worst case estimates. In this talk, I will present a Gröbner basis approach to solve sparse 0-dimensional systems whose input polynomials have different Newton polytopes. Under regularity assumptions, we can have an explicit combinatorial bound for the complexity of the algorithm.

This is joint work with Jean-Charles Faugère and Elias Tsigaridas. --------------7A8DED23764FBEF5A501C5C9--