Return to Colloquia & Seminar listing
Parametric Polyhedra with at least $k$ Lattice Points
Algebra & Discrete Mathematics| Speaker: | Prof. Iskander Aliev, Cardiff Univ. UK |
| Location: | 1147 MSB |
| Start time: | Mon, May 16 2016, 4:10PM |
The well-studied affine semigroup $\sg(A)=\{ b : b=Ax, \ x \in \Z^n, x \geq 0\}$ can be stratified by the sizes of the polyhedral fibers $IP_A(b)=\{x: Ax=b, x\geq 0, x\in \Z^n\}$.
In this talk we first discuss a structure theory that characterizes precisely the set $\sg_{\geq k}(A)$ of all vectors $b \in \sg(A)$ such that their fiber $IP_A(b)$ contains \emph{at least} $k$ lattice points.
As a corollary, we prove that for fixed $n,k$ the $k$-Frobenius number can be computed in polynomial time, generalising a well-known result of Ravi Kannan.
We also discuss related results on the behavior of integers with exactly $k$-representations.
The talk is based on a joint work with Jesus De Loera and Quentin Louveaux.