You are cordially invited to our next Monday Colloquium on June
4th at 14:15 h at TU Berlin.

__Speaker__: Andrew Newman (Ohio State University**)**

__Title__: **Small simplicial complexes with large
torsion in homology**

__Time__: **Monday, June 4th - 14:15 h**

__Location__**: **

Technische Universität Berlin

Straße des 17. Juni 136

10623 Berlin

From Kalai's classic paper generalizing Cayley's tree-enumeration formula to simplicial complexes, it is known that simplicial complexes on a small number of vertices can have enormous torsion in homology. Moreover, in a random setting one may find instances of this phenomenon such as, for example, a 3-dimensional simplicial complex on 30 vertices with the torsion subgroup of the second homology group having order larger than 10^

-- Graduiertenkolleg 'Facets of Complexity' www.facetsofcomplexity.de/monday--------------04C44352AB8EDDD114375975-- From i.brunke@inf.fu-berlin.de Wed Jun 06 14:34:34 2018 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:DHE-RSA-AES256-GCM-SHA384:256) (envelope-from

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

__Location__**: **

Freie Universität Berlin

Takustr. 9

14195 Berlin

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

__Lecture__: John Bamberg (University** of Western
Australia, Perth)**

__Title__: Bruck nets, metric planes, and their friends

In 1967, F. Arthur Sherk gave a simple proof that the finite
metric planes (of Bachmann and Schmidt) are precisely the affine
planes of odd order. Moreover, Sherk’s proof holds for a more
general class of incidence structures that do not involve the
‘three-reflection theorem’ whatsoever, and thus yields a
beautiful characterisation of the finite affine planes of odd
order. By relaxing the first of Sherk’s axioms to ‘every pair of
points lies on at most** **one line’, we can study
what we call *partial Sherk planes*. In this talk, we
outline our characterisation of these incidence structures as *Bruck
nets*, in the same vein as Sherk’s result, and what it
means for connected combinatorial objects such as mutually
orthogonal latin squares.

(Joint work with Joanna Fawcett and Jesse Lansdown)

__Time__: **Monday, June 11th - 16:00 h**

__Colloquium__: Anurag Bishnoi (Freie Universität Berlin**)**

__Title__: New upper bounds on some cage numbers

The cage problem asks for the smallest number c(k, g) of
vertices in a k-regular graph of girth g. The (k, g)-graphs
which have c(k, g) vertices are known as cages. While cages are
known to exist for all integers k > 1 and g > 2, an
explicit construction is known only for some small values of k,
g and three infinite families for which g is 6, 8 or 12 and k −
1 is a prime power: corresponding to the generalized g/2-gons of
order k − 1.

To improve the upper bounds on c(k, 6), c(k, 8) and c(k, 12),
when k - 1 is not a prime power, one of the main techniques that
has been used so far is to construct small (k, g) graphs by
picking a prime power q ≥ k and then finding a small k-regular
subgraph of the incidence graph of a generalized g/2-gon of
order q. In this talk I will present new constructions in
generalized quadrangles and hexagons which improve the known
upper bound on c(k, 8) when k = p^{2h} and c(k, 12) when k =
p^h, where p is an arbitrary prime. Moreover, we will see a
spectral lower bound on the number of vertices in a k-regular
induced subgraph of an arbitrary regular graph, which in
particular will prove the optimality of a known construction in
projective planes.

-- Graduiertenkolleg 'Facets of Complexity' www.facetsofcomplexity.de/monday--------------A58EC9E00751370622B5C668-- From i.brunke@inf.fu-berlin.de Thu Jun 14 13:31:28 2018 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:DHE-RSA-AES256-GCM-SHA384:256) (envelope-from

You are cordially invited to our next Monday Lecture on June 18th
at 14:15 h at TU Berlin.

__Speaker__: Rico Zenklusen (ETH Zürich**)**

__Title__: **At the Interface of Combinatorial
Optimization and Integer Programming
**

__Time__: **Monday, June 18th - 14:15 h**

__Location__**: **

Technische Universität Berlin

Straße des 17. Juni 136

10623 Berlin

In this talk, I will show how techniques from Combinatorial Optimization and Combinatorics can be leveraged to achieve progress on a well-known question in Integer Programming, namely how to solve integer linear programs (ILPs) with bounded subdeterminants. More precisely, I will present an efficient (even strongly polynomial) algorithm to solve ILPs defined by a constraint matrix whose subdeterminants are all within {-2,-1,0,1,2}. This problem class naturally extends the well-known class of ILPs with a totally unimodular (TU) constraint matrix, i.e., where subdeterminants are within {-1,0,1}, and captures some open problems. We employ a variety of techniques common in Combinatorial Optimization, including polyhedral techniques, matroids, and submodular functions. In particular, using a polyhedral result of Veselov and Chirkov, we reduce the problem to a combinatorial one with a so-called parity constraint. We then show how a seminal, purely combinatorial result of Seymour on decomposing TU matrices, which is tightly related to regular matroids and was originally developed in this context, can be used algorithmically to break the problem into smaller ones. Finally, these smaller problems are amenable to combinatorial optimization techniques like parity-constrained submodular minimization. Additionally, I will highlight some of the many open problems in this field and discuss recent related results.

-- Graduiertenkolleg 'Facets of Complexity' www.facetsofcomplexity.de/monday--------------E60464890C6FDF33777A62BC-- From i.brunke@inf.fu-berlin.de Thu Jun 21 16:03:16 2018 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:DHE-RSA-AES256-GCM-SHA384:256) (envelope-from

You are cordially invited to our next **two** Monday Lectures
on June 25th at 14:15 h & 16:00 h at TU Berlin.

__Location of the two Lectures__**: **

Technische Universität Berlin

Straße des 17. Juni 136

10623 Berlin

__Time__: **Monday, June 25th - 14:15 h**

__Lecture__: Antoine Deza (Université Paris Sud)

__Title__: On lattice polytopes, convex matroid
optimization, and degree sequences of hypergraphs

We introduce a
family of polytopes, called primitive zonotopes, which can be seen
as a generalization of the permutahedron of type $B_d$. We discuss
connections to the largest diameter of lattice polytopes and to
the computational complexity of multicriteria matroid
optimization. Complexity results and open questions are also
presented. In particular, we answer a question raised in 1986 by
Colbourn, Kocay, and Stinson by showing that deciding whether a
given sequence is the degree sequence of a 3-hypergraph is
computationally prohibitive. Based on joint works with Asaf Levin
(Technion), George Manoussakis (Ben Gurion), Syed Meesum (IMSc
Chennai), Shmuel Onn (Technion), and Lionel Pounin (Paris XIII).

Technische Universität Berlin

Straße des 17. Juni 136

10623 Berlin

__Time__: **Monday, June 25th - 16:00 h**

__Lecture__: Matthias Beck

__Title__: Binomial Inequalities of Chromatic, Flow, and
Ehrhart Polynomials

A famous and
wide-open problem, going back to at least the early 1970's,
concerns the classification of chromatic polynomials of graphs.
Toward this classification problem, one may ask for necessary
inequalities among the coefficients of a chromatic polynomial, and
we contribute one such set of inequalities when a chromatic
polynomial $\chi_G(n) = \chi^*_0 \binom {n+d} d + \chi^*_1 \binom
{n+d-1} d + \dots + \chi^*_d \binom n d$ is written in terms of a
binomial-coefficient basis. More precisely, we prove that
$\chi^*_{d-2}+\chi^*_{d-3}+\dots+\chi^*_{d-j-1} \ \ge \
\chi^*_1+\chi^*_2+\dots+\chi^*_j $, for $1 \le j \le \lfloor
\frac{ d }{ 2 } \rfloor - 1$. A similar result holds for flow
polynomials enumerating either modular or integral nowhere-zero
flows of a graph. Our theorems follow from connections among
chromatic, flow, order, and Ehrhart polynomials, and the fact that
the latter satisfy a decomposition formula into symmetric
polynomials due to Stapledon.

(This is joint work with Emerson Le\'on.)

*Exceptionally, there will be two** **lectures
and *no *colloquium**.*

(This is joint work with Emerson Le\'on.)

-- Graduiertenkolleg 'Facets of Complexity' www.facetsofcomplexity.de/monday--------------80C7536509466062F2E8F378-- From rolf.niedermeier@tu-berlin.de Mon Jun 25 19:35:08 2018 Received: from relay1.zedat.fu-berlin.de ([130.133.4.67]) by list1.zedat.fu-berlin.de (Exim 4.85) for facets-of-complexity@lists.fu-berlin.de with esmtps (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (envelope-from

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

__Location__**: **

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

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.

__Time__: **Monday, July 2nd - 16:00 h**

__Colloquium__: Laith Rastanawi (Freie Universität Berlin**)**

__Title__: On the Dimension of the Realization Spaces of
Polytopes

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--------------6042C6795519D85BC69FF2AF--