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