#
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

*Abstract:*

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

*Abstract:*

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