Monday, January 7, 2013
Freie Universität Berlin
Institut für Informatik
Lecture - 14:15
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
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.