Monday, July 16, 2007
Freie Universität Berlin
Institut für Informatik
Takustr. 9, 14195 Berlin
room 005
Lecture - 14:15
Abstract:
A \emph{positive affine monoid} $M$ is a finitely generated
submonoid of a free abelian group of finite rank whose only
invertible element is $0$. It is called \emph{normal} if every $x\in
\gp(M)$ (the group generated by $M$) for which a multiple $kx$,
$k\in\ZZ$, $k>0$, lies in $M$ belongs to $M$ itself. The
\emph{Hilbert basis} of $M$ is the subset of those elements that can
not be decomposed as a sum of two nonzero elements of $M$.
$\Hilb(M)$ is in fact the unique minimal system of generators of
$M$.
One says that $M$ has \emph{unimodular Hilbert covering} (UHC) if it
is the union of those submonoids that are generated by a basis of
$\gp(M)$ contained in $\Hilb(M)$, and $M$ has the \emph{integral
Carath\'eodory property} (ICP) if it is the union of those
submonoids that are generated by subsets of $\Hilb(M)$ of
cardinality at most rank $M$. The terminology is motivated by
Carath\'eodory's theorem on cones: every point in the cone generated
by a set $X\subset \RR^d$ is in one of the subcones generated by a
subset $X'\subset X$ of cardinality $\le d$.
Clearly, (UHC) implies (ICP), and as proved by Bruns and Gubeladze,
(ICP) implies normality. In dimension $\le 3$ every monoid has (UHC)
as shown by Seb\"o, but in 1998 B\&G found a rank $6$ normal monoid
that has neither (UHC) nor (ICP). It remained an open problem
whether (ICP) implies (UHC) until recently when we discovered a rank
$6$ monoid that is (ICP) but not (UHC). We will discuss the
experimental approach to the discovery of the (counter)examples
which have been as hard to find as needles in a haystack.
Though the relationship between normality, (UHC) and (ICP) is
clarified in general, there remain interesting open problems. For
example, the situation in dimensions $4$ and $5$ is completely open.
However, our experimental data suggest that in these dimensions all
normal monoids have (UHC).
afterwards