[Facets-of-complexity] Invitation to Monday Lecture & Colloquium - July 2nd 2018

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

You are cordially invited to our next Monday Lecture & Colloquium on July 2nd 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, July 2nd - 14:15 h

Lecture: Benjamin Burton  (University of Queensland, Australia)

Title: From parameterised to non-parameterised algorithms in knot theory

Abstract:

We describe some recent developments in treewidth-based algorithms for knots, which exploit the structure of the underlying 4-valent planar graph. In particular, we show how these led to the first general sub-exponential-time algorithm for the HOMFLY-PT polynomial, and we describe some recent progress on parameterised algorithms for unknot recognition.

Coffee & Tea Break

Time: Monday, July 2nd - 16:00 h

Colloquium: Laith Rastanawi (Freie Universität Berlin)

Title: On the Dimension of the Realization Spaces of Polytopes

Abstract:

The study of realization spaces of convex polytopes is one of the oldest subjects in Polytope Theory. Most likely, it goes back to Legendre (1794).  A lot of progress took place since that time. However, many questions remained open. In general, computing the dimension of the realization space $\mathcal{R}(P)$ of a d-polytope $P$ is hard, even for $d = 4$, as shown by Mnëv (1988) and Richter-Gebert (1996).In this presentation, we will discuss two criteria to determine the dimension of the realization space, and use them to show that $\dim \mathcal{R}(P) = f_1(P) + 6$ for a 3-polytope $P$, and $\dim \mathcal{R}(P) = df_{d-1}(P)$ (resp. $\dim \mathcal{R}(P) = df_0(P)$ ) for a simple (resp. simplicial) $d$-polytope $P$. We will also discuss the realization spaces of some interesting 2-simple 2-simplicial 4-polytopes. Namely, we will consider the realization space of the 24-cell and of a 2s2s polytope with 12 vertices which was found by Miyata (2011), and give a better bound for/determine its dimension.

-- 
Graduiertenkolleg 'Facets of Complexity' www.facetsofcomplexity.de/monday