BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Gennadiy Averkov

Gennadiy Averkov appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.MGmath.OCmath.COmath.AGDiscrete Mathematicsmath.PRmath.ACmath.CA

Catalog footprint

What is connected

26works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

26 published item(s)

preprint2022arXiv

Efficient MIP Techniques for Computing the Relaxation Complexity

The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the minimal number of inequalities needed to formulate a linear optimization problem over X without using auxiliary variables. Besides its relevance in integer programming, this concept has interpretations in aspects of social choice, symmetric cryptanalysis, and machine learning. We employ efficient mixed-integer programming techniques to compute a robust and numerically more practical variant of the relaxation complexity. Our proposed models require row or column generation techniques and can be enhanced by symmetry handling and suitable propagation algorithms. Theoretically, we compare the quality of our models in terms of their LP relaxation values. The performance of those models is investigated on a broad test set and is underlined by their ability to solve challenging instances that could not be solved previously.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The role of rationality in integer-programming relaxations

For a finite set $X \subset \mathbb{Z}^d$ that can be represented as $X = Q \cap \mathbb{Z}^d$ for some polyhedron $Q$, we call $Q$ a relaxation of $X$ and define the relaxation complexity $rc(X)$ of $X$ as the least number of facets among all possible relaxations $Q$ of $X$. The rational relaxation complexity $rc_\mathbb{Q}(X)$ restricts the definition of $rc(X)$ to rational polyhedra $Q$. In this article, we focus on $X = Δ_d$, the vertex set of the standard simplex, which consists of the null vector and the standard unit vectors in $\mathbb{R}^d$. We show that $rc(Δ_d) \leq d$ for every $d \geq 5$. That is, since $rc_{\mathbb{Q}}(Δ_d)=d+1$, irrationality can reduce the minimal size of relaxations. This answers an open question posed by Kaibel and Weltge (Lower bounds on the size of integer programs without additional variables, Mathematical Programming, 154(1):407-425, 2015). Moreover, we prove the asymptotic statement $rc(Δ_d) \in O(\frac{d}{\sqrt{\log(d)}})$, which shows that the ratio $rc(Δ_d)/rc_{\mathbb{Q}}(Δ_d)$ goes to $0$, as $d\to \infty$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Complexity of linear relaxations in integer programming

For a set $X$ of integer points in a polyhedron, the smallest number of facets of any polyhedron whose set of integer points coincides with $X$ is called the relaxation complexity $\mathrm{rc}(X)$. This parameter was introduced by Kaibel & Weltge (2015) and captures the complexity of linear descriptions of $X$ without using auxiliary variables. Using tools from combinatorics, geometry of numbers, and quantifier elimination, we make progress on several open questions regarding $\mathrm{rc}(X)$ and its variant $\mathrm{rc}_{\mathbb{Q}}(X)$, restricting the descriptions of $X$ to rational polyhedra. As our main results we show that $\mathrm{rc}(X) = \mathrm{rc}_{\mathbb{Q}}(X)$ when: (a) $X$ is at most four-dimensional, (b) $X$ represents every residue class in $(\mathbb{Z}/2\mathbb{Z})^d$, (c) the convex hull of $X$ contains an interior integer point, or (d) the lattice-width of $X$ is above a certain threshold. Additionally, $\mathrm{rc}(X)$ can be algorithmically computed when $X$ is at most three-dimensional, or $X$ satisfies one of the conditions (b), (c), or (d) above. Moreover, we obtain an improved lower bound on $\mathrm{rc}(X)$ in terms of the dimension of $X$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Optimizing Sparsity over Lattices and Semigroups

Motivated by problems in optimization we study the sparsity of the solutions to systems of linear Diophantine equations and linear integer programs, i.e., the number of non-zero entries of a solution, which is often referred to as the $\ell_0$-norm. Our main results are improved bounds on the $\ell_0$-norm of sparse solutions to systems $A x = b$, where $A \in \mathbb{Z}^{m \times n}$, $b \in \mathbb{Z}^m$ and $x$ is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In the lattice case and certain scenarios of the semigroup case, we give polynomial time algorithms for computing solutions with $\ell_0$-norm satisfying the obtained bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Homometry and direct-sum decompositions of lattice-convex sets

Two sets in $\mathbb{R}^d$ are called homometric if they have the same covariogram, where the covariogram of a finite subset $K$ of $\mathbb{R}^d$ is the function associating to each $u \in \mathbb{R}^d$ the cardinality of $K \cap (K+u)$. Understanding the structure of homometric sets is important for a number of areas of mathematics and applications. If two sets are homometric but do not coincide up to translations and point reflections, we call them nontrivially homometric. We study nontrivially homometric pairs of lattice-convex sets, where a set $K$ is called lattice-convex with respect to a lattice $\mathbb{M} \subseteq \mathbb{R}^d$ if $K$ is the intersection of $\mathbb{M}$ and a convex subset of $\mathbb{R}^d$. This line of research was initiated in 2005 by Daurat, Gérard and Nivat and, independently, by Gardner, Gronchi and Zong. All pairs of nontrivially homometric lattice-convex sets that have been known so far can essentially be written as direct sums $S \oplus T$ and $S \oplus (-T)$, where $T$ is lattice-convex, the underlying lattice~$\mathbb{M}$ is the direct sum of $T$ and some sublattice $\mathbb{L}$, and $S$ is a subset of $\mathbb{L}$. We study pairs of nontrivially homometric lattice-convex sets assuming this particular form and establish a necessary and a sufficient condition for the lattice-convexity of $S \oplus T$. This allows us to explicitly describe all nontrivially homometric pairs in dimension two, under the above assumption, and to construct examples of nontrivially homometric pairs of lattice-convex sets for each $d \ge 3$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Maximum Semidefinite and Linear Extension Complexity of Families of Polytopes

We relate the maximum semidefinite and linear extension complexity of a family of polytopes to the cardinality of this family and the minimum pairwise Hausdorff distance of its members. This result directly implies a known lower bound on the maximum semidefinite extension complexity of 0/1-polytopes. We further show how our result can be used to improve on the corresponding bounds known for polygons with integer vertices. Our geometric proof builds upon nothing else than a simple well-known property of maximum volume inscribed ellipsoids of convex bodies. In particular, it does not rely on factorizations over the semidefinite cone and thus avoids involved procedures of balancing them as required, e.g., in [Briet, Dadush & Pokutta 2015]. We hope that revealing the geometry behind the phenomenon opens doors for further results. Moreover, we show that the linear extension complexity of every d-dimensional 0/1-polytope is bounded from above by O(2^d / d).

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Tight bounds on discrete quantitative Helly numbers

Given a subset S of R^n, let c(S,k) be the smallest number t such that whenever finitely many convex sets have exactly k common points in S, there exist at most t of these sets that already have exactly k common points in S. For S = Z^n, this number was introduced by Aliev et al. [2014] who gave an explicit bound showing that c(Z^n,k) = O(k) holds for every fixed n. Recently, Chestnut et al. [2015] improved this to c(Z^n,k) = O(k (log log k)(log k)^{-1/3} ) and provided the lower bound c(Z^n,k) = Omega(k^{(n-1)/(n+1)}). We provide a combinatorial description of c(S,k) in terms of polytopes with vertices in S and use it to improve the previously known bounds as follows: We strengthen the bound of Aliev et al. [2014] by a constant factor and extend it to general discrete sets S. We close the gap for Z^n by showing that c(Z^n,k) = Theta(k^{(n-1)/(n+1)}) holds for every fixed n. Finally, we determine the exact values of c(Z^n,k) for all k <= 4.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Lifting properties of maximal lattice-free polyhedra

We study the uniqueness of minimal liftings of cut-generating functions obtained from maximal lattice-free polyhedra. We prove a basic invariance property of unique minimal liftings for general maximal lattice-free polyhedra. This generalizes a previous result by Basu, Cornuéjols and Köppe~\cite{bcm} for {\em simplicial} maximal lattice-free polytopes, thus completely settling this fundamental question about lifting for maximal lattice-free polyhedra. We further give a very general iterative construction to get maximal lattice-free polyhedra with the unique-lifting property in arbitrary dimensions. This single construction not only obtains all previously known polyhedra with the unique-lifting property, but goes further and vastly expands the known list of such polyhedra. Finally, we extend characterizations from~\cite{bcm} about lifting with respect to maximal lattice-free simplices to more general polytopes. These nontrivial generalizations rely on a number of results from discrete geometry, including the Venkov-Alexandrov-McMullen theorem on translative tilings and characterizations of zonotopes in terms of central symmetry of their faces.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Notions of maximality for integral lattice-free polyhedra: the case of dimension three

Lattice-free sets (convex subsets of $\mathbb{R}^d$ without interior integer points) and their applications for cutting-plane methods in mixed-integer optimization have been studied in recent literature. Notably, the family of all integral lattice-free polyhedra which are not properly contained in another integral lattice-free polyhedron has been of particular interest. We call these polyhedra $\mathbb{Z}^d$-maximal. It is known that, for fixed $d$, the family $\mathbb{Z}^d$-maximal integral lattice-free polyhedra is finite up to unimodular equivalence. In view of possible applications in cutting-plane theory, one would like to have a classification of this family. However, this turns out to be a challenging task already for small dimensions. In contrast, the subfamily of all integral lattice-free polyhedra which are not properly contained in any other lattice-free set, which we call $\mathbb{R}^d$-maximal lattice-free polyhedra, allow a rather simple geometric characterization. Hence, the question was raised for which dimensions the notions of $\mathbb{Z}^d$-maximality and $\mathbb{R}^d$-maximality are equivalent. This was known to be the case for dimensions one and two. On the other hand, Nill and Ziegler (2011) showed that for dimension $d \ge 4$, there exist polyhedra which are $\mathbb{Z}^d$-maximal but not $\mathbb{R}^d$-maximal. In this article, we consider the remaining case $d = 3$ and prove that for integral polyhedra the notions of $\mathbb{R}^3$-maximality and $\mathbb{Z}^3$-maximality are equivalent. As a consequence, the classification of all $\mathbb{R}^3$-maximal integral polyhedra by Averkov, Wagner and Weismantel (2011) contains all $\mathbb{Z}^3$-maximal integral polyhedra.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Covariograms generated by valuations

Let ϕbe a real-valued valuation on the family of compact convex subsets of \mathbb{R}^n and let K be a convex body in \mathbb{R}^n. We introduce the ϕ-covariogram g_{K,ϕ} of K as the function associating to each x \in \mathbb{R}^n the value ϕ(K \cap (K+x)). If ϕis the volume, then g_{K,ϕ} is the covariogram, extensively studied in various sources. When ϕis a quermassintegral (e.g., surface area or mean width) g_{K,ϕ} has been introduced by Nagel. We study various properties of ϕ-covariograms, mostly in the case n=2 and under the assumption that ϕis translation invariant, monotone and even. We also consider the generalization of Matheron's covariogram problem to the case of ϕ-covariograms, that is, the problem of determining an unknown convex body K, up to translations and point reflections, by the knowledge of g_{K,ϕ}. A positive solution to this problem is provided under different assumptions, including the case that K is a polygon and ϕis either strictly monotone or ϕis the width in a given direction. We prove that there are examples in every dimension n\geq3 where K is determined by its covariogram but it is not determined by its width-covariogram. We also present some consequence of this study in stochastic geometry.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Largest integral simplices with one interior integral point: Solution of Hensley's conjecture and related results

For each dimension $d$, $d$-dimensional integral simplices with exactly one interior integral point have bounded volume. This was first shown by Hensley. Explicit volume bounds were determined by Hensley, Lagarias and Ziegler, Pikhurko, and Averkov. In this paper we determine the exact upper volume bound for such simplices and characterize the volume-maximizing simplices. We also determine the sharp upper bound on the coefficient of asymmetry of an integral polytope with a single interior integral point. This result confirms a conjecture of Hensley from 1983. Moreover, for an integral simplex with precisely one interior integral point, we give bounds on the volumes of its faces, the barycentric coordinates of the interior integral point and its number of integral points. Furthermore, we prove a bound on the lattice diameter of integral polytopes with a fixed number of interior integral points. The presented results have applications in toric geometry and in integer optimization.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On maximal S-free sets and the Helly number for the family of S-convex sets

We study two combinatorial parameters, which we denote by f(S) and h(S), associated to an arbitrary set S \subseteq R^d, where d \in N. In the nondegenerate situation, f(S) is the largest possible number of facets of a d-dimensional polyhedron L such that the interior of L is disjoint with S and L is inclusion-maximal with respect to this property. The parameter h(S) is the Helly number of the family of all sets that can be given as the intersection of S with a convex subset of R^d. We obtain the inequality f(S) \le h(S) for an arbitrary S and the equality f(S)=h(S) for every discrete S. Furthermore, motivated by research in integer and mixed-integer optimization, we show that 2^d is the sharp upper bound on f(S) in the case S = (Z^d \times R^n) \cap C, where n \ge 0 and C \subseteq R^{d+n} is convex. The presented material generalizes and unifies results of various authors, including the result h(Z^d) = 2^d of Doignon, the related result f(Z^d)=2^d of Lovász and the inequality f(Z^d \cap C) \le 2^d, which has recently been proved for every convex set C \subseteq R^d by Dey & Morán.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Constructive proofs of some positivstellensätze for compact semialgebraic subsets of $\mathbb{R}^d$

In a broad sense, positivstellensätze are results about representations of polynomials which are strictly positive on a given set. We give constructive and, to a large extent, elementary proofs of some known positivstellensätze for compact semialgebraic subsets of $\mathbb{R}^d$. The presented proofs extend and simplify arguments of Berr, Wörmann (2001) and Schweighofer (2002, 2005).

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On finitely generated closures in the theory of cutting planes

Let $P$ be a rational polyhedron in $\mathbb{R}^d$ and let $\mathcal{L}$ be a class of $d$-dimensional maximal lattice-free rational polyhedra in $\mathbb{R}^d$. For $L \in \mathcal{L}$ by $R_L(P)$ we denote the convex hull of points belonging to $P$ but not to the interior of $L$. Andersen, Louveaux and Weismantel showed that if the so-called max-facet-width of all $L \in \mathcal{L}$ is bounded from above by a constant independent of $L$, then $\bigcap_{L\in \mathcal{L}} R_L(P)$ is a rational polyhedron. We give a short proof of a generalization of this result. We also give a characterization for the boundedness of the max-facet-width on $\mathcal{L}$. The presented results are motivated by applications in cutting-plane theory from mixed-integer optimization.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the convergence of the affine hull of the Chvátal-Gomory closures

Given an integral polyhedron P and a rational polyhedron Q living in the same n-dimensional space and containing the same integer points as P, we investigate how many iterations of the Chvátal-Gomory closure operator have to be performed on Q to obtain a polyhedron contained in the affine hull of P. We show that if P contains an integer point in its relative interior, then such a number of iterations can be bounded by a function depending only on n. On the other hand, we prove that if P is not full-dimensional and does not contain any integer point in its relative interior, then no finite bound on the number of iterations exists.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the reconstruction of planar lattice-convex sets from the covariogram

A finite subset $K$ of $\mathbb{Z}^d$ is said to be lattice-convex if $K$ is the intersection of $\mathbb{Z}^d$ with a convex set. The covariogram $g_K$ of $K\subseteq \mathbb{Z}^d$ is the function associating to each $u \in \integer^d$ the cardinality of $K\cap (K+u)$. Daurat, Gérard, and Nivat and independently Gardner, Gronchi, and Zong raised the problem on the reconstruction of lattice-convex sets $K$ from $g_K$. We provide a partial positive answer to this problem by showing that for $d=2$ and under mild extra assumptions, $g_K$ determines $K$ up to translations and reflections. As a complement to the theorem on reconstruction we also extend the known counterexamples (i.e., planar lattice-convex sets which are not reconstructible, up to translations and reflections) to an infinite family of counterexamples.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the size of lattice simplices with a single interior lattice point

Let $\mathcal{T}^d(1)$ be the set of all $d$-dimensional simplices $T$ in $\real^d$ with integer vertices and a single integer point in the interior of $T$. It follows from a result of Hensley that $\mathcal{T}^d(1)$ is finite up to affine transformations that preserve $\mathbb{Z}^d$. It is known that, when $d$ grows, the maximum volume of the simplices $T \in \cT^d(1)$ becomes extremely large. We improve and refine bounds on the size of $T \in \mathcal{T}^d(1)$ (where by the size we mean the volume or the number of lattice points). It is shown that each $T \in \mathcal{T}^d(1)$ can be decomposed into an ascending chain of faces whose sizes are `not too large'. More precisely, if $T \in \mathcal{T}^d(1)$, then there exist faces $G_1 \subseteq ... \subseteq G_d=T$ of $T$ such that, for every $i \in \{1,...,d\}$, $G_i$ is $i$-dimensional and the size of $G_i$ is bounded from above in terms of $i$ and $d$. The bound on the size of $G_i$ is double exponential in $i$. The presented upper bounds are asymptotically tight on the log-log scale.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A proof of Lovász's theorem on maximal lattice-free sets

Let $K$ be a maximal lattice-free set in $\mathbb{R}^d$, that is, $K$ is convex and closed subset of $\mathbb{R}^d$, the interior of $K$ does not cointain points of $\mathbb{Z}^d$ and $K$ is inclusion-maximal with respect to the above properties. A result of Lovász assert that if $K$ is $d$-dimensional, then $K$ is a polyhedron with at most $2^d$ facets, and the recession cone of $K$ is spanned by vectors from $\mathbb{Z}^d$. A first complete proof of mentioned Lovász's result has been published in a paper of Basu, Conforti, Cornuéjols and Zambelli (where the authors use Dirichlet's approximation as a tool). The aim of this note is to give another proof of this result. Our proof relies on Minkowki's first fundamental theorem from the gemetry of numbers. We remark that the result of Lovász is relevant in integer and mixed-integer optimization.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Maximal lattice-free polyhedra: finiteness and an explicit description in dimension three

A convex set with nonempty interior is maximal lattice-free if it is inclusion-maximal with respect to the property of not containing integer points in its interior. Maximal lattice-free convex sets are known to be polyhedra. The precision of a rational polyhedron $P$ in $\mathbb{R}^d$ is the smallest integer $s$ such that $sP$ is an integral polyhedron. In this paper we show that, up to affine mappings preserving $\mathbb{Z}^d$, the number of maximal lattice-free rational polyhedra of a given precision $s$ is finite. Furthermore, we present the complete list of all maximal lattice-free integral polyhedra in dimension three. Our results are motivated by recent research on cutting plane theory in mixed-integer linear optimization.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On finite generation and infinite convergence of generalized closures from the theory of cutting planes

For convex sets $K$ and $L$ in ${\mathbb{R}}^d$ we define $R_L(K)$ to be the convex hull of all points belonging to $K$ but not to the interior of $L$. Cutting-plane methods from integer and mixed-integer optimization can be expressed in geometric terms using functionals $R_L$ with appropriately chosen sets $L$. We describe the geometric properties of $R_L(K)$ and characterize those $L$ for which $R_L$ maps polyhedra to polyhedra. For certain natural classes ${\mathcal{L}}$ of convex sets in ${\mathbb{R}}^d$ we consider the functional $R_{\mathcal{L}}$ given by $R_{\mathcal{L}}(K):= \bigcap_{L \in {\mathcal{L}}}R_L(K)$. The functional $R_{\mathcal{L}}$ can be used to define various types of closure operations considered in the theory of cutting planes (such as the Chvátal closure, the split closure as well as generalized split closures recently introduced by Andersen, Louveaux and Weismantel). We study conditions on ${\mathcal{L}}$ under which $R_{\mathcal{L}}$ maps rational polyhedra to rational polyhedra. We also describe the limit of the sequence of sets obtained by iterative application of $R_{\mathcal{L}}$ to $K$. A part of the presented material gives generalized formulations and unified proofs of several recent results obtained by various authors.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Description of polygonal regions by polynomials of bounded degree

We show that every (possibly unbounded) convex polygon $P$ in $R^2$ with $m$ edges can be represented by inequalities $p_1 \ge 0,...,p_n \ge 0,$ where the $p_i$'s are products of at most $k$ affine functions each vanishing on an edge of $P$ and $n=n(m,k)$ satisfies $s(m,k) \le n(m,k) \le (1+ε_m) s(m,k)$ with $s(m,k):=\max \{m/k,\log_2 m\}$ and $ε_m \to 0$ as $m \to \infty$. This choice of $n$ is asymptotically best possible. An analogous result on representing the interior of $P$ in the form $p_1 > 0,..., p_n > 0$ is also given. For $k \le m/\log_2 m$ these statements remain valid for representations with arbitrary polynomials of degree not exceeding $k$.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Inequalities for the lattice width of lattice-free convex sets in the plane

A closed, convex set $K$ in $\mathbb{R}^2$ with non-empty interior is called lattice-free if the interior of $K$ is disjoint with $\mathbb{Z}^2$. In this paper we study the relation between the area and the lattice width of a planar lattice-free convex set in the general and centrally symmetric case. A correspondence between lattice width on the one hand and covering minima on the other, allows us to reformulate our results in terms of covering minima introduced by Kannan and Lovász. We obtain a sharp upper bound for the area for any given value of the lattice width. The lattice-free convex sets satisfying the upper bound are characterized. Lower bounds are studied as well. Parts of our results are applied in a paper by the authors and Weismantel for cutting plane generation in mixed integer linear optimization, which was the original inducement for this paper. We further rectify a result of Kannan and Lovász with a new proof.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Minimal polynomial descriptions of polyhedra and special semialgebraic sets

We show that a $d$-dimensional polyhedron $S$ in $\real^d$ can be represented by $d$-polynomial inequalities, that is, $S = \{x \in \real^d : p_0(x) \ge 0, >..., p_{d-1}(x) \ge 0 \}$, where $p_0,...,p_{d-1}$ are appropriate polynomials. Furthermore, if an elementary closed semialgebraic set $S$ is given by polynomials $q_1,...,q_k$ and for each $x \in S$ at most $s$ of these polynomials vanish in $x$, then $S$ can be represented by $s+1$ polynomials (and by $s$ polynomials under the extra assumption that the number of points $x \in S$ in which $s$ $q_i$'s vanish is finite).

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Transversal numbers over subsets of linear spaces

Let $M$ be a subset of $\mathbb{R}^k$. It is an important question in the theory of linear inequalities to estimate the minimal number $h=h(M)$ such that every system of linear inequalities which is infeasible over $M$ has a subsystem of at most $h$ inequalities which is already infeasible over $M.$ This number $h(M)$ is said to be the Helly number of $M.$ In view of Helly's theorem, $h(\mathbb{R}^n)=n+1$ and, by the theorem due to Doignon, Bell and Scarf, $h(\mathbb{Z}^d)=2^d.$ We give a common extension of these equalities showing that $h(\mathbb{R}^n \times \mathbb{Z}^d) = (n+1) 2^d.$ We show that the fractional Helly number of the space $M \subseteq \mathbb{R}^d$ (with the convexity structure induced by $\mathbb{R}^d$) is at most $d+1$ as long as $h(M)$ is finite. Finally we give estimates for the Radon number of mixed integer spaces.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

Confirmation of Matheron's conjecture on the covariogram of a planar convex body

The covariogram g_K of a convex body K in E^d is the function which associates to each x in E^d the volume of the intersection of K with K+x. In 1986 G. Matheron conjectured that for d=2 the covariogram g_K determines K within the class of all planar convex bodies, up to translations and reflections in a point. This problem is equivalent to some problems in stochastic geometry and probability as well as to a particular case of the phase retrieval problem in Fourier analysis. It is also relevant for the inverse problem of determining the atomic structure of a quasicrystal from its X-ray diffraction image. In this paper we confirm Matheron's conjecture completely.

0 citations0 reviewsNo code linkedOpen access