BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Martin Henk appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Recently, K.-Y. Wu introduced affine subspace concentration conditions for the cone volumes of polytopes and proved that the cone volumes of centered, reflexive, smooth lattice polytopes satisfy these conditions. We extend the result to arbitrary centered polytopes.
Gardner, Gronchi and Zong posed the problem to find a discrete analogue of M. Meyer's inequality bounding the volume of a convex body from below by the geometric mean of the volumes of its slices with the coordinate hyperplanes. Motivated by this problem, for which we provide a first general bound, we study in a more general context the question to bound the number of lattice points of a convex body in terms of slices as well as projections.
We obtain a transference bound for vertices of corner polyhedra that connects two well-established areas of research: proximity and sparsity of solutions to integer programs. In the knapsack scenario, it gives an exponential (in the size of support of a solution) improvement on previously known proximity estimates. In addition, for general integer linear programs we obtain a resembling result that connects the minimum absolute nonzero entry of an optimal solution with the size of its support.
Motivated by long-standing conjectures on the discretization of classical inequalities in the Geometry of Numbers, we investigate a new set of parameters, which we call \emph{packing minima}, associated to a convex body $K$ and a lattice $Λ$. These numbers interpolate between the successive minima of $K$ and the inverse of the successive minima of the polar body of $K$, and can be understood as packing counterparts to the covering minima of Kannan & Lovász (1988). As our main results, we prove sharp inequalities that relate the volume and the number of lattice points in $K$ to the sequence of packing minima. Moreover, we extend classical transference bounds and discuss a natural class of examples in detail.
In this survey we give an overview about some of the main results on parametric densities, a concept which unifies the theory of finite (free) packings and the classical theory of infinite packings.
We obtain optimal lower and upper bounds for the (additive) integrality gaps of integer knapsack problems. In a randomised setting, we show that the integrality gap of a "typical" knapsack problem is drastically smaller than the integrality gap that occurs in a worst case scenario.
We prove a tight subspace concentration inequality for the dual curvature measures of a symmetric convex body.
Let $\# K$ be a number of integer lattice points contained in a set $K$. In this paper we prove that for each $d\in {\mathbb N}$ there exists a constant $C(d)$ depending on $d$ only, such that for any origin-symmetric convex body $K \subset {\mathbb R}^d$ containing $d$ linearly independent lattice points $$ \# K \leq C(d)\max(\# (K\cap H))\, {\rm vol}_d(K)^{\frac{d-m}{d}}, $$ where the maximum is taken over all $m$-dimensional subspaces of ${\mathbb R}^d$. We also prove that $C(d)$ can be chosen asymptotically of order $O(1)^{d}d^{d-m}$. In addition, we show that if $K$ is an unconditional convex body then $C(d)$ can be chosen asymptotically of order $O(d)^{d-m}$.
We study upper bounds on the number of lattice points for convex bodies having their centroid at the origin. For the family of simplices as well as in the planar case we obtain best possible results. For arbitrary convex bodies we provide an upper bound, which extends the centrally symmetric case and which, in particular, shows that the centroid assumption is indeed much more restrictive than an assumption on the number of interior lattice points even for the class of lattice polytopes.
We show that the cone-volume measure of a convex body with centroid at the origin satisfies the subspace concentration condition. This implies, among others, a conjectured best possible inequality for the $\mathrm{U}$-functional of a convex body. For both results we provide stronger versions in the sense of stability inequalities.
Minkowski's 2nd theorem in the Geometry of Numbers provides optimal upper and lower bounds for the volume of a $o$-symmetric convex body in terms of its successive minima. In this paper we study extensions of this theorem from two different points of view: either relaxing the symmetry condition, assuming that the centroid of the set lies at the origin, or replacing the volume functional by the surface area.
The cone-volume measure of a polytope with centroid at the origin is proved to satisfy the subspace concentration condition. As a consequence a conjectured (a dozen years ago) fundamental sharp affine isoperimetric inequality for the U-functional is completely established -- along with its equality conditions.
We give bounds on the successive minima of an $o$-symmetric convex body under the restriction that the lattice points realizing the successive minima are not contained in a collection of forbidden sublattices. Our investigations extend former results to forbidden full-dimensional lattices, to all successive minima and complement former results in the lower dimensional case.
Given an integer matrix A satisfying certain regularity assumptions, we consider for a positive integer s the set F_s(A) of all integer vectors b such that the associated knapsack polytope P(A,b)={x: Ax=b, x non-negative} contains at least s integer points. In this paper we investigate the structure of the set F_s(A) sing the concept of s-covering radius. In particular, in a special case we prove an optimal lower bound for the s-Frobenius number.
For $A\in\mathbb{Z}^{m\times n}$ we investigate the behaviour of the number of lattice points in $P_A(b)=\{x\in\mathbb{R}^n:Ax\leq b\}$, depending on the varying vector $b$. It is known that this number, restricted to a cone of constant combinatorial type of $P_A(b)$, is a quasi-polynomial function if b is an integral vector. We extend this result to rational vectors $b$ and show that the coefficients themselves are piecewise-defined polynomials. To this end, we use a theorem of McMullen on lattice points in Minkowski-sums of rational dilates of rational polytopes and take a closer look at the coefficients appearing there.
We produce new upper and lower bounds for the s-Frobenius number by relating it to the so called s-covering radius of a certain convex body with respect to a certain lattice; this generalizes a well-known theorem of R. Kannan for the classical Frobenius number. Using these bounds, we obtain results on the average behavior of the s-Frobenius number, extending analogous recent investigations for the classical Frobenius number by a variety of authors. We also derive bounds on the s-covering radius, an interesting geometric quantity in its own right.
Given an integer mxn matrix A satisfying certain regularity assumptions, a well-known integer programming problem asks to find an integer point in the associated knapsack polytope P(A, b)={x: A x= b, x>=0} or determine that no such point exists. We obtain a LLL-based polynomial time algorithm that solves the problem subject to a constraint on the location of the vector b.
We investigate structural properties of the cone of roots of relative Steiner polynomials of convex bodies. We prove that they are closed, monotonous with respect to the dimension, and that they cover the whole upper half-plane, except the positive real axis, when the dimension tends to infinity. In particular, it turns out that relative Steiner polynomials are stable polynomials if and only if the dimension is $\leq 9$. Moreover, pairs of convex bodies whose relative Steiner polynomial has a complex root on the boundary of such a cone have to satisfy some Aleksandrov-Fenchel inequality with equality. An essential tool for the proofs of the results is the characterization of Steiner polynomials via ultra-logconcave sequences.
Minkowski's second theorem on successive minima gives an upper bound on the volume of a convex body in terms of its successive minima. We study the problem to generalize Minkowski's bound by replacing the volume by the lattice point enumerator of a convex body. In this context we are interested in bounds on the coefficients of Ehrhart polynomials of lattice polytopes via the successive minima. Our results for lattice zonotopes and lattice-face polytopes imply, in particular, that for 0-symmetric lattice-face polytopes and lattice parallelepipeds the volume can be replaced by the lattice point enumerator.
We investigate the Ehrhart polynomial for the class of 0-symmetric convex lattice polytopes in Euclidean $n$-space $\mathbb{R}^n$. It turns out that the roots of the Ehrhart polynomial and Minkowski's successive minima are closely related by their geometric and arithmetic mean. We also show that the roots of lattice $n$-polytopes with or without interior lattice points differ essentially. Furthermore, we study the structure of the roots in the planar case. Here it turns out that their distribution reflects basic properties of lattice polygons.
An immediate generalization of the classical McKay correspondence for Gorenstein quotient spaces $\Bbb{C}^{r}/G$ in dimensions $r\geq 4$ would primarily demand the existence of projective, crepant, full desingularizations. Since this is not always possible, it is natural to ask about special classes of such quotient spaces which would satisfy the above property. In this paper we give explicit necessary and sufficient conditions under which 2-parameter series of Gorenstein cyclic quotient singularities have torus-equivariant resolutions of this specific sort in all dimensions.