[Facets-of-complexity] Invitation to Monday Lectures on June 25th 2018

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

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:

Room MA 041 - Ground Floor
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

Abstract:

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).

Coffee & Tea Break :

Room MA 316 - Third Floor
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

Abstract:

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.

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