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