Mathematics Colloquia and Seminars

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.