Über eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner

The problem of the partition-numbersJ _?(p, q), considered by Hadwiger and Debrunner for the family ?=C ⁿ of convex bodies, is extended to simplicial complexes and arbitrary families assuming only the validity of Helly’s theorem. We obtain results similar to those of Hadwiger and Debrunner. Further we show the existence of all partition-numbers for the family? = H ⁿC of homothets of a convex body and we get new informations on the partition-numbers for the family of parallel rectangles.     

Kirchberger-type theorems for separation by convex domains

We say that a convex set K in ? ^d strictly separates the set A from the set B if A ? int(K) and B ? cl K = ø. The well-known Theorem of Kirchberger states the following. If A and B are finite sets in ? ^d with the property that for every T ? A?B of cardinality at most d + 2, there is a half space strictly separating T ? A and T ? B, then there is a half space strictly separating A and B. In short, we say that the strict separation number of the family of half spaces in ? ^d is d + 2.In this note we investigate the problem of strict separation of two finite sets by the family of positive homothetic (resp., similar) copies of a closed, convex set. We prove Kirchberger-type theorems for the family of positive homothets of planar convex sets and for the family of homothets of certain polyhedral sets. Moreover, we provide examples that show that, for certain convex sets, the family of positive homothets (resp., the family of similar copies) has a large strict separation number, in some cases, infinity. Finally, we examine how our results translate to the setting of non-strict separation.     

On the vertex index of convex bodies

We introduce the vertex index, vein(K), of a given centrally symmetric convex body K⊂Rd, which, in a sense, measures how well K can be inscribed into a convex polytope with small number of vertices. This index is closely connected to the illumination parameter of a body, introduced earlier by the first named author, and, thus, related to the famous conjecture in Convex Geometry about covering of a d-dimensional body by d² smaller positively homothetic copies. We provide asymptotically sharp estimates (up to a logarithmic term) of this index in the general case. More precisely, we show that for every centrally symmetric convex body K⊂Rd one has

     

Billiards in convex bodies with acute angles

In this paper we investigate the existence of closed billiard trajectories in not necessarily smooth convex bodies. In particular, we show that if a body K ? R^d has the property that the tangent cone of every non-smooth point q ? ?K is acute (in a certain sense), then there is a closed billiard trajectory in K.     

On a question by Corson about point-finite coverings

We answer in the affirmative the following question raised by H. H. Corson in 1961: “Is it possible to cover every Banach space X by bounded convex sets with non-empty interior in such a way that no point of X belongs to infinitely many of them?”Actually, we show the way to produce in every Banach space X a bounded convex tiling of order 2, i.e., a covering of X by bounded convex closed sets with non-empty interior (tiles) such that the interiors are pairwise disjoint and no point of X belongs to more than two tiles.     

Asymmetry of Convex Bodies of Constant Width

The symmetry of convex bodies of constant width is discussed in this paper. We proved that for any convex body K?? ⁿ of constant width, \(1\leq \mathrm{as}_{\infty}(K)\leq\frac{n+\sqrt{2n(n+1)}}{n+2}\), where as_∞(?) denotes the Minkowski measure of asymmetry for convex bodies. Moreover, the equality holds on the left-hand side precisely iff K is an Euclidean ball and the upper bounds are attainable, in particular, if n=3, the equality holds on the right-hand side if K is a Meissner body.     

A discrete version of Koldobsky’s slicing inequality

Let #K be a number of integer lattice points contained in a set K. In this paper we prove that for each d ∈ N there exists a constant C(d) depending on d only, such that for any origin-symmetric convex body K ? R ^d containing d linearly independent lattice points

$$\# K \leqslant C\left( d \right)\max \left( {\# \left( {K \cap H} \right)} \right)vo{l_d}{\left( K \right)^{\frac{{d - m}}{d}}},$$

where the maximum is taken over all m-dimensional subspaces of R ^d . We also prove that C(d) can be chosen asymptotically of order O(1) ^d d ^d?m . In particular, we have order O(1) ^d for hyperplane slices. Additionally, we show that if K is an unconditional convex body then C(d) can be chosen asymptotically of order O(d) ^d?m .

     

Covering Convex Bodies by Cylinders and Lattice Points by Flats

In connection with an unsolved problem of Bang (1951) we give a lower bound for the sum of the base volumes of cylinders covering a d-dimensional convex body in terms of the relevant basic measures of the given convex body. As an application we establish lower bounds on the number of k-dimensional flats (i.e. translates of k-dimensional linear subspaces) needed to cover all the integer points of a given convex body in d-dimensional Euclidean space for 1≤k≤d−1. K. Bezdek and A.E. Litvak are partially supported by a Natural Sciences and Engineering Research Council of Canada Discovery Grant.     

Some remarks concerning kissing numbers,blocking numbers and covering numbers

This article shows an inequality concerning blocking numbers and Hadwiger's covering numbers and presents a strange phenomenon concerning kissing numbers and blocking numbers. As a simple corollary, we can improve the known upper bounds for Hadwiger's covering numbers ford-dimensional centrally symmetric convex bodies to 3 ^d –1.     

Minkowski Additive Operators Under Volume Constraints

We investigate Minkowski additive, continuous, and translation invariant operators \(\Phi :\mathcal {K}^n\rightarrow \mathcal {K}^n\) defined on the family of convex bodies such that the volume of the image \(\Phi (K)\) is bounded from above and below by multiples of the volume of the convex body K, uniformly in K. We obtain a representation result for an infinite subcone contained in the cone formed by this type of operators. Under the additional assumption of monotonicity or \({{\mathrm{SO}}}(n)\)-equivariance, we obtain new characterization results for the difference body operator.     

Edge clique covering sum of graphs

The edge clique cover sum number (resp. edge clique partition sum number) of a graph G, denoted by scc(G) (resp. scp(G)), is defined as the smallest integer k for which there exists a collection of complete subgraphs of G, covering (resp. partitioning) all edges of G such that the sum of sizes of the cliques is at most k. By definition, scc(G) \({\leqq}\) scp(G). Also, it is known that for every graph G on n vertices, scp(G) \({\leqq n^{2}/2}\). In this paper, among some other results, we improve this bound for scc(G). In particular, we prove that if G is a graph on n vertices with no isolated vertex and the maximum degree of the complement of G is d ? 1, for some integer d, then scc(G) \({\leqq cnd\left\lceil\log \left(({n-1})/(d-1)\right)\right\rceil}\), where c is a constant. Moreover, we conjecture that this bound is best possible up to a constant factor. Using a well-known result by Bollobás on set systems, we prove that this conjecture is true at least for d = 2. Finally, we give an interpretation of this conjecture as an interesting set system problem which can be viewed as a multipartite generalization of Bollobás’ two families theorem.     

Conley index of nontrivial invariant sets in a Hilbert space

We study flows defined in a Hilbert space by potential completely continuous fields Id-K(·), where K(·) is an operator close to a homogeneous one. The Conley index of the set of fixed points and separatrices joining them (a nontrivial invariant set) is defined for such flows. By using this index, we prove that the equation K(x) = x has infinitely many solutions of arbitrarily large norm provided that the potential φ: ?φ(·) = K(·) is coercive and has an even leading part. As a corollary, we justify the stability of an arbitrary finite number of solutions under small perturbations of the field. We show that the Conley index differs from the classical rotation theory of vector fields when proving existence theorems.     

On a normed version of a Rogers–Shephard type problem

A translation body of a convex body is the convex hull of two of its translates intersecting each other. In the 1950s, Rogers and Shephard found the extremal values, over the family of n-dimensional convex bodies, of the maximal volume of the translation bodies of a given convex body. In our paper, we introduce a normed version of this problem, and for the planar case, determine the corresponding quantities for the four types of volumes regularly used in the literature: Busemann, Holmes–Thompson, and Gromov’s mass and mass*. We examine the problem also for higher dimensions, and for centrally symmetric convex bodies.     

Finite Sets as Complements of Finite Unions of Convex Sets

Suppose S?? ^d is a set of (finite) cardinality n, whose complement can be written as the union of k convex sets. It is perhaps intuitively appealing that when n is large k must also be large. This is true, as is shown here. First the case in which the convex sets must also be open is considered, and in this case a family of examples yields an upper bound, while a simple application of a theorem of Björner and Kalai yields a lower bound. Much cruder estimates are then obtained when the openness restriction is dropped. For a given set S the problem of determining the smallest number of convex sets whose union is ? ^d ?S is shown to be equivalent to the problem of finding the chromatic number of a certain (infinite) hypergraph ? _S . We consider the graph \(\mathcal {G}_{S}\) whose edges are the 2-element edges of ? _S , and we show that, when d=2, for any sufficiently large set S, the chromatic number of \(\mathcal{G}_{S}\) will be large, even though there exist arbitrarily large finite sets S for which \(\mathcal{G}_{S}\) does not contain large cliques.     

Covering a set with homothets of a convex body

We consider two problems mentioned in the book “Research Problems in Discrete Geometry” (Brass et al. in research problems in discrete geometry, vol xii+499. Springer, New York, pp ISBN: 978-0387-23815-8; 0-387-23815-8, 2005). First, let K and L be given convex bodies in \mathbbR^d{\mathbb{R}^{d}} . We prove that if the total volume of a family of positive homothets of K is sufficiently large then they permit a translative covering of L. This problem, in the case when K = L and the dimension is two, was originally posed by L. Fejes Tóth. The previously known bound (Januszewski in proc. of the International scientific conference on mathematics, pp 29–34. Žilina, 1998) on the total volume (in the case when K = L) was of order d ^d vol(K), we prove a bound that is exponential in the dimension. The second problem is the following: Find a condition, in terms of the coefficients of homothety, that is necessary for a family of positive homothets of K to cover K. The problem was phrased by V. Soltan, who conjectured that the sum of the coefficients is at least d. We confirm an asymptotic version of this conjecture.     

Vector scheduling with rejection on a single machine

In this paper, we study a vector scheduling problem with rejection on a single machine, in which each job is characterized by a d-dimension vector and a penalty, in the sense that, jobs can be either rejected by paying a certain penalty or assigned to the machine. The objective is to minimize the sum of the maximum load over all dimensions of the total vector of all accepted jobs, and the total penalty of rejected jobs. We prove that the problem is NP-hard and design two approximation algorithms running in polynomial time. When d is a fixed constant, we present a fully polynomial time approximation scheme.     

Spherical bodies of constant width

The intersection L of two different non-opposite hemispheres G and H of the d-dimensional unit sphere \(S^d\) is called a lune. By the thickness of L we mean the distance of the centers of the \((d-1)\)-dimensional hemispheres bounding L. For a hemisphere G supporting a convex body \(C \subset S^d\) we define \(\mathrm{width}_G(C)\) as the thickness of the narrowest lune or lunes of the form \(G \cap H\) containing C. If \(\mathrm{width}_G(C) =w\) for every hemisphere G supporting C, we say that C is a body of constant width w. We present properties of these bodies. In particular, we prove that the diameter of any spherical body C of constant width w on \(S^d\) is w, and that if \(w < \frac{\pi }{2}\), then C is strictly convex. Moreover, we check when spherical bodies of constant width and constant diameter coincide.     

A new simultaneous iterative method with a parameter for solving the extended split equality problem and the extended split equality fixed point problem

In this article, we first propose an extended split equality problem which is an extension of the convex feasibility problem, and then introduce a parameter w to establish the fixed point equation system. We show the equivalence of the extended split equality problem and the fixed point equation system. Based on the fixed point equation system, we present a simultaneous iterative algorithm and obtain the weak convergence of the proposed algorithm. Further, by introducing the concept of a G-mapping of a finite family of strictly pseudononspreading mappings \(\{T_{i}\}_{i = 1}^{N}\), we consider an extended split equality fixed point problem for G-mappings and give a simultaneous iterative algorithm with a way of selecting the stepsizes which do not need any prior information about the operator norms, and the weak convergence of the proposed algorithm is obtained. We apply our iterative algorithms to some convex and nonlinear problems. Finally, several numerical results are shown to confirm the feasibility and efficiency of the proposed algorithms.     

Nonlinear separation concerning <Emphasis Type="Italic">E</Emphasis>-optimal solution of constrained multi-objective optimization problems

This paper aims at investigating optimality conditions in terms of E-optimal solution for constrained multi-objective optimization problems in a general scheme, where E is an improvement set with respect to a nontrivial closed convex point cone with apex at the origin. In the case where E is not convex, nonlinear vector regular weak separation functions and scalar weak separation functions are introduced respectively to realize the separation between the two sets in the image space, and Lagrangian-type optimality conditions are established. These results extend and improve the convex ones in the literature.     

An exact algorithm for finding a vector subset with the longest sum

We consider the problem: Given a set of n vectors in the d-dimensional Euclidean space, find a subsetmaximizing the length of the sum vector.We propose an algorithm that finds an optimal solution to this problem in time O(n^d?1(d + logn)). In particular, if the input vectors lie in a plane then the problem is solvable in almost linear time.