Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, January 7, 2013

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
room 005

Lecture - 14:15

Michael Joswig - TU Darmstadt

Highly Symmetric Integer Linear Programs

A symmetry of an ILP is a linear transformation which acts as a signed permutation on the variables. Deciding the feasibility of an ILP is a well-known NP-dard problem. However, provided that the group of symmetries contains the alternating group A_n (in its standard action), we can present an algorithm which solves an ILP with m constraints in n variables in O(mn^2) time. Further, it will be discussed how finding ILP symmetries can be reduced to a graph isomorphism problem.

This is joint work with Richard Bödi and Katrin Herr.

Colloquium - 16:00

Katharine Jochemko - Freie Universität Berlin

Arithmetic of marked order polytopes and monotone triangle reciprocity

A map f from a poset P into a poset Q is order preserving if f(p) <= f(q) in Q whenever p < q in P, and f is strictly order preserving if f(p) < f(q). Stanley considered the problem of counting order preserving maps from a finite poset P into the chain of length n and showed that many enumerative problems (e.g. counting graph colorings) can be cast into this form. He showed that for a fixed poset P the number of these maps is given by a polynomial in the positive integer n and gave an interpretation for evaluating this polynomial at negative integers in terms of strictly order preserving maps. We consider the more general problem: Given a finite poset P, an induced subposet A which contains all minimal and maximal elements of P, and a map f from A into the integers. What is the number of integral valued order preserving maps with domain P extending f? By passing to real-valued maps we were able to show that the function counting integral valued extensions is a piecewise polynomial in the values of f and we can give an interpretation for evaluation at order reversing maps. These results can be applied to give a geometric proof of a combinatorial reciprocity for monotone triangles due to Fischer and Riegler (2011).

This is joined work with Raman Sanyal.

Letzte Aktualisierung: 17.12.2012