n-distributivity,dimension and Carathéodory's theorem

A. Huhn proved that the dimension of Euclidean spaces can be characterized through algebraic properties of the lattices of convex sets. In fact, the lattice of convex sets of isn+1-distributive but notn-distributive. In this paper his result is generalized for a class of algebraic lattices generated by their completely join-irreducible elements. The lattice theoretic form of Carathéodory's theorem characterizesn-distributivity in such lattices. Several consequences of this result are studied. First, it is shown how infiniten-distributivity and Carathéodory's theorem are related. Then the main result is applied to prove that for a large class of lattices beingn-distributive means being in the variety generated by the finiten-distributive lattices. Finally,n-distributivity is studied for various classes of lattices, with particular attention being paid to convexity lattices of Birkhoff and Bennett for which a Helly type result is also proved.Presented by J. Sichler.     

Stability in Aleksandrov's problem for a convex body,one of whose projections is a ball

A stability theorem is proved corresponding to this uniqueness theorem forn5,k3, and under the hypothesis that one of the projections of the convex body on a hyperplane ofR ⁿ is a ball. In particular the stability theorem holds in the case when the body is a solid of revolution.Translated from Ukrainskií Geometricheskií Sbornik, Issue 28, 1985, pp. 50–62.     

Common transversals in the plane: The fractional perspective

A fresh look is taken at the fractional Helly theorem for line transversals to families of convex sets in the plane. This theorem was first proved in 1980 by Katchalski and Liu [M. Katchalski, A. Liu, Symmetric twins and common transversals, Pacific J. Math. 86 (1980) 513–515]. It asserts that for every integer k≥3, there exists a real number ρ(k)(0,1) such that the following holds: If is a family of n compact convex sets in the plane, and any k or fewer members of have a line transversal, then some subfamily of of size at least has a line transversal. A lower bound on ρ(k) is obtained which is stronger than the one obtained in [M. Katchalski, A. Liu, Symmetric twins and common transversals, Pacific J. Math. 86 (1980) 513–515]. Also, examples are given to show that a conjecture of Katchalski concerning the value of ρ(3), if true, is the best possible.     

On clique convergent graphs

A graphG isconvergent when there is some finite integern 0, such that then-th iterated clique graphK ⁿ(G) has only one vertex. The smallest suchn is theindex ofG. TheHelly defect of a convergent graph is the smallestn such thatK ⁿ(G) is clique Helly, that is, its maximal cliques satisfy the Helly property. Bandelt and Prisner proved that the Helly defect of a chordal graph is at most one and asked whether there is a graph whose Helly defect exceeds the difference of its index and diameter by more than one. In the present paper an affirmative answer to the question is given. For any arbitrary finite integern, a graph is exhibited, the Helly defect of which exceeds byn the difference of its index and diameter.     

Convex Sets in Acyclic Digraphs

A non-empty set X of vertices of an acyclic digraph is called connected if the underlying undirected graph induced by X is connected and it is called convex if no two vertices of X are connected by a directed path in which some vertices are not in X. The set of convex sets (connected convex sets) of an acyclic digraph D is denoted by and its size by co(D) (cc(D)). Gutin et al. (2008) conjectured that the sum of the sizes of all convex sets (connected convex sets) in D equals Θ(n · co(D)) (Θ(n · cc(D))) where n is the order of D. In this paper we exhibit a family of connected acyclic digraphs with and . We also show that the number of connected convex sets of order k in any connected acyclic digraph of order n is at least n − k + 1. This is a strengthening of a theorem of Gutin and Yeo.     

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

Intersection properties of boxes. Part I: An upper-bound theorem

LetP be a family ofn boxes inR ^d (with edges parallel to the coordinate axes). Fork=0, 1, 2, …, denote byf _k (P) the number of subfamilies ofP of sizek+1 with non-empty intersection. We show that iff _r (P)=0 for somer≦n, then where thef _k (n, d, r) are ceg196rtain definite numbers defined by (3.4) below. The result is best possible for eachk. Fork=1 it was conjectured by G. Kalai (Israel J. Math.48 (1984), 161–174). As an application, we prove a ‘fractional’ Helly theorem for families of boxes inR ^d .     

A note on the colorful fractional Helly theorem

Helly’s theorem is a classical result concerning the intersection patterns of convex sets in ${\mathbb{R}}^d$. Two important generalizations are the colorful version and the fractional version. Recently, Bárány et al. combined the two, obtaining a colorful fractional Helly theorem. In this paper, we give an improved version of their result.     

Inverting the Motivic Bott Element

We prove a version for motivic cohomology of Thomason's theorem on Bott-periodic K-theory, namely, that for a field k containing the nth roots of unity, the mod n motivic cohomology of a smooth k-scheme agrees with mod n étale cohomology, after inverting the element in H⁰(k,(1)) corresponding to a primitive nth root of unity.     

Convexly independent sets

A family of pairwise disjoint compact convex sets is called convexly independent, if none of its members is contained in the convex hull of the union of the other members of the family. The main result of the paper gives an upper bound for the maximum cardinalityh(k, n) of a family of mutually disjoint compact convex sets such that any subfamily of at mostk members of is convexly independent, but no subfamily of sizen is.     

Meinardus' theorem on weighted partitions: Extensions and a probabilistic proof

The number c_n of weighted partitions of an integer n, with parameters (weights) b_k, k1, is given by the generating function relationship . Meinardus (1954) established his famous asymptotic formula for c_n, as n→∞, under three conditions on power and Dirichlet generating functions for the sequence b_k. We give a probabilistic proof of Meinardus' theorem with weakened third condition and extend the resulting version of the theorem from weighted partitions to other two classic types of decomposable combinatorial structures, which are called assemblies and selections.     

Convex programs with an additional reverse convex constraint

A method is presented for solving a class of global optimization problems of the form (P): minimizef(x), subject toxD,g(x)0, whereD is a closed convex subset ofR ⁿ andf,g are convex finite functionsR ⁿ . Under suitable stability hypotheses, it is shown that a feasible point is optimal if and only if 0=max{g(x):xD,f(x)f( )}. On the basis of this optimality criterion, the problem is reduced to a sequence of subproblemsQ _k ,k=1, 2, ..., each of which consists in maximizing the convex functiong(x) over some polyhedronS _k . The method is similar to the outer approximation method for maximizing a convex function over a compact convex set.     

Rubber bands,convex embeddings and graph connectivity

We give various characterizations ofk-vertex connected graphs by geometric, algebraic, and physical properties. As an example, a graphG isk-connected if and only if, specifying anyk vertices ofG, the vertices ofG can be represented by points of ^k–1 so that nok are on a hyper-plane and each vertex is in the convex hull of its neighbors, except for thek specified vertices. The proof of this theorem appeals to physics. The embedding is found by letting the edges of the graph behave like ideal springs and letting its vertices settle in equilibrium.As an algorithmic application of our results we give probabilistic (Monte-Carlo and Las Vegas) algorithms for computing the connectivity of a graph. Our algorithms are faster than the best known (deterministic) connectivity algorithms for allkn, and for very dense graphs the Monte Carlo algorithm is faster by a linear factor.     

On the topological complexity of DC-sets

A DC-set is a set defined by means of convex constraints and one additional inverse convex constraint. Given an arbitrary closed subsetM of the Euclideann-space, we show that there exists a DC-set in (n+1)-space being homeomorphic to the given setM. Secondly, for any fixedn2, we construct a compactn-dimensional manifold with boundary, which is a DC-set and which has arbitrarily large Betti-numbersr _k fork n–2.     

A Comparison Theorem on Moment Inequalities Between Negatively Associated and Independent Random Variables

Let {X _i, 1in} be a negatively associated sequence, and let {X* _i , 1in} be a sequence of independent random variables such that X* _i and X _i have the same distribution for each i=1, 2,..., n. It is shown in this paper that Ef( ⁿ _i=1 X _i)Ef( ⁿ _i=1 X* _i ) for any convex function f on R ¹ and that Ef(max_1kn ⁿ _i=k X _i)Ef(max_1kn ^k _i=1 X* _i ) for any increasing convex function. Hence, most of the well-known inequalities, such as the Rosenthal maximal inequality and the Kolmogorov exponential inequality, remain true for negatively associated random variables. In particular, the comparison theorem on moment inequalities between negatively associated and independent random variables extends the Hoeffding inequality on the probability bounds for the sum of a random sample without replacement from a finite population.     

Erdős–Szekeres-Type Theorems for Segments and Noncrossing Convex Sets

A family of convex sets is said to be in convex position, if none of its members is contained in the convex hull of the others. It is proved that there is a function N(n) with the following property. If is a family of at least N(n) plane convex sets with nonempty interiors, such that any two members of have at most two boundary points in common and any three are in convex position, then has n members in convex position. This result generalizes a theorem of T. Bisztriczky and G. Fejes Tóth. The statement does not remain true, if two members of may share four boundary points. This follows from the fact that there exist infinitely many straight-line segments such that any three are in convex position, but no four are. However, there is a function M(n) such that every family of at least M(n) segments, any four of which are in convex position, has n members in convex position.     

On the second differentiability of convex surfaces

Properties of pointwise second differentiability of real-valued convex functions in ⁿ are studied. Some proofs of the Busemann-Feller-Aleksandrov theorem are reviewed and a new proof of this theorem is presented.     

k-Weakly almost convex groups and π 1 ∞ \tilde M^3

We extend Cannon's notion ofk-almost convex groups which requires that for two pointsx, y on then-sphere in the Cayley graph which can be joined by a pathl ₁ of length k, there is a second pathl ₂ in then-ball, joiningx andy, of bounded length N(k). Ourk-weakly almost convexity relaxes this condition by requiring only thatl ₁ l ₂ bounds a disk of area C ₁(k)n ^{1 - (k)} +C ₂(k). IfM ³ is a closed 3-manifold with 3-weakly almost convex fundamental group, then ₁ .     

How big can the circuits of a bridge of a maximal circuit be?

IfCE(G) is a maximum cardinality cocircuit of a 2-connected graphG, then no other maximum cocircuit is contained in one and the same block ofG-C. The analogous conjecture for real representable matroids would have important applications to classifying convex bodies with a certain Helly type property.     

The generalized tilt formula

A convex hull construction in Minkowski space defines a canonical cell decomposition for a cusped hyperbolicn-manifold. An algorithm to compute the canonical cell decomposition uses the concept of the tilt of ann-simplex relative to each of its (n–1)-dimensional faces. An essential tool for computing tilts is the tilt theorem. The tilt theorem was previously known only in dimensionsn3, and the proof was needlessly complicated. Here we offer a new, simplified proof which applies in all dimensions. We also offer a second geometric interpretation of the tilt.