You are cordially invited to our next Lecture on **Thursday,**
**July 5th,** at 14:15 h at FU Berlin.

__Speaker__: Akihiro Higashitani (Kyoto San**gyo
University)**

__Title__: Finding a new universal condition in Ehrhart
theory

__Time__: **THURSDAY, July 5th - 14:15 h**

__Location__**: **

Freie Universität Berlin

Institut für Mathematik

Arnimallee 2

14195 Berlin

Recently, Balletti and I proved that for the h^*-polynomial h_0^*+h_1^*t+... of a lattice polytope, if we assume h_3^*=0, then (h_1^*, h_2^*) satisfies (i) h_2^*=0; or (ii) h_1^* \leq 3h_2^* + 3; or (iii) (h_1^*,h_2^*)=(7,1). These conditions derive from Scott's theorem (1976), who characterized the possible h^*-polynomials of 2-dimensional lattice polytopes, and Scott's theorem is also essentially valid for lattice polytopes with degree at most 2 (Treutlein (2010)). On the other hand, we proved that it also holds under the assumption h_3^*=0. Since the assumption h_3^*=0 is independent of both dimension and degree of polytopes, we call the conditions (i), (ii), (iii) universal. In this talk, towards finding a new universal condition, we investigate the possibility for the polynomial h_0^*+h_1^*t+... to be the h^*-polynomial of some lattice polytope under the assumption that some of h_i^*'s vanish.

-- Graduiertenkolleg 'Facets of Complexity' www.facetsofcomplexity.de/monday--------------B4ED3332CA327538C159649D-- From i.brunke@inf.fu-berlin.de Thu Jul 05 15:57:21 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 July 9th 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, July 9th - 14:15 h**

__Lecture__: Jeroen Zuiddam (CWI, Amsterdam)

__Title__: Asymptotic spectra of tensors and graphs: matrix
multiplication exponent and Shannon capacity

Matrix rank is well-known to be multiplicative under the Kronecker product, additive under the direct sum, normalised on identity matrices and non-increasing under multiplying from the left and from the right by any matrices. In fact, matrix rank is the only real matrix parameter with these four properties. In 1986 Strassen proposed to study the extension to tensors: find all maps from k-tensors to the reals that are multiplicative under the tensor Kronecker product, additive under the direct sum, normalized on diagonal tensors, and non-increasing under acting with linear maps on the k tensor factors. Strassen called the collection of these maps the "asymptotic spectrum of k-tensors". Strassen proved that understanding the asymptotic spectrum implies understanding the asymptotic relations among tensors, including the asymptotic rank. In particular, knowing the asymptotic spectrum means knowing the arithmetic complexity of matrix multiplication, a central problem in algebraic complexity theory.I will give an overview of known elements in the asymptotic spectrum of tensors, including our recent construction which is based on information theory and moment polytopes. This recent construction is joint work with Matthias Christandl and Peter Vrana.Then I will introduce the analogous object in graph theory: the asymptotic spectrum of graphs. I will explain the relation to Shannon capacity and give an overview of known elements in the asymptotic spectrum of graphs.

R

__Time__: **Monday, July 9th - 16:00 h**

__Colloquium__: Aaron Williams (Bard College at Simon's
Rock, USA)

__Title__: Fun and Games: The Computational Complexity of
Puzzles and Video Games

Most computer
scientists and discrete mathematicians are familiar with
computational complexity due to the famous P = NP conjecture. Some
researchers have a more thorough understanding of the classes P,
NP, and PSPACE since problems in logic, graph theory, and
combinatorial optimization are often classified by their
relationship to one of these classes. More recently, these
concepts have found a wider audience through their application to
puzzles and games. For example, it is known that the number puzzle
Sudoku is NP-complete, whereas the box pushing game Sokoban is
PSPACE-complete. In this talk we establish the computational
complexity of several puzzles and games. We prove that two new
paper and pencil puzzles are NP-complete. These puzzles are called
Pencils and Sto-Stone, and were created by the Japanese publisher
Nikoli that popularized Sudoku. We then prove that several puzzles
that have been implemented as video games are PSPACE-complete.
These games include a row shifting puzzle called MazezaM, a
turnstile puzzle for the Nintendo Game Boy called Kwirk, and a
puzzle called Switches that was invented by undergraduate student
Jonathan Gabor while he was attending high school. Our reductions
use conventional approaches such as Boolean Satisfiability, as
well as some less conventional tools including Gray Codes, and the
new Constraint Logic model pioneered by Hearn and Demaine in their
influential textbook "Games, Puzzles, and Computation". The talk
aims to be accessible to a wide audience, and hopes to encourage
researchers to seek similar results for problems (or puzzles!)
that are close to them. Most of the new results consist of joint
work with undergraduate students at Bard College at Simon's Rock.

-- Graduiertenkolleg 'Facets of Complexity' www.facetsofcomplexity.de/monday--------------FA7973066A21E5D927151C49-- From i.brunke@inf.fu-berlin.de Wed Jul 11 17:01:11 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 July 16th 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, July 16th - 14:15 h**

__Lecture__: Mihyun Kang (Graz University of Technology)

__Title__: Vanishing of cohomology groups of random
simplicial complexes

We consider
random simplicial complexes that are generated from the binomial
random hypergraphs by taking the downward-closure. We determine
when all cohomology groups with coefficients in F_2 vanish. This
is joint work with Oliver Cooley, Nicola Del Giudice, and Philipp
Spruessel.

Technische Universität Berlin

Straße des 17. Juni 136

10623 Berlin

__Time__: **Monday, July 16th - 16:00 h**

__Colloquium__: Martin Balko (Charles
University of Prague)

__Title__: Ramsey numbers and monotone colorings

For positive integers N and r >= 2, an r-monotone coloring of r-tuples from [N] is a 2-coloring by -1 and +1 that is monotone on the lexicographically ordered sequence of r-tuples of every (r+1)-tuple from [N]. Let ORS(n;r) be the minimum N such that every r-monotone coloring of r tuples from [N] contains n elements with all r-tuples of the same color. For every r >= 3, it is known that ORS(n;r) is bounded from above by a tower function of height r-2 with O(n) on the top. The Erdős--Szekeres Lemma and the Erdős--Szekeres Theorem imply ORS(n;2)=(n-1)

-- Graduiertenkolleg 'Facets of Complexity' www.facetsofcomplexity.de/monday--------------1DDEFF8A45135942AB3CCDF7-- From felsner@math.tu-berlin.de Tue Jul 17 15:09:35 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