Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, July 16, 2007

Freie Universität Berlin
Institut für Informatik
Takustr. 9, 14195 Berlin
room 005

Lecture - 14:15

Winfried Bruns - Universität Osnabrück

Covering properties of normal affine monoids

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).


Faculty meeting

Letzte Aktualisierung: 04.07.2007