A Helly-type theorem for countable intersections of starshaped sets

Let k and d be fixed integers, 0kd, and let be a collection of sets in If every countable subfamily of has a starshaped intersection, then is (nonempty and) starshaped as well. Moreover, if every countable subfamily of has as its intersection a starshaped set whose kernel is at least k-dimensional, then the kernel of is at least k-dimensional, too. Finally, dual statements hold for unions of sets.Received: 3 April 2004     

A Helly theorem for intersections of orthogonally starshaped sets

Let $\cal{F}$ be a finite family of simply connected orthogonal polygons in the plane. If every three (not necessarily distinct) members of $\cal{F}$ have a nonempty intersection which is starshaped via staircase paths, then the intersection $\cap \{F : F\; \hbox{in}\; \cal{F}\}$ is a (nonempty) simply connected orthogonal polygon which is starshaped via staircase paths. Moreover, the number three is best possible, even with the additional requirement that the intersection in question be nonempty. The result fails without the simple connectedness condition.     

Unions of orthogonally convex or orthogonally starshaped polygons

LetT be a simply connected orthogonal polygon having the property that for every three points ofT, at least two of these points see each other via staircases inT. ThenT is a union of three orthogonally convex polygons. The number three is best possible.ForT a simply connected orthogonal polygon,T is a union of two orthogonally convex polygons if and only if for every sequencev ₁,...,v _n,v _n+1 =v ₁ inT, n odd, at least one consecutive pairv _i ,v _i+1 sees each other via staircase paths inT, 1 i n. An analogous result says thatT is a union of two orthogonal polygons which are starshaped via staircase paths if and only if for every odd sequence inT, at least one consecutive pair sees a common point via staircases inT.Supported in part by NSF grants DMS-8908717 and DMS-9207019.     

Simply connected orthogonal polygons as unions of two orthogonally starshaped sets

Let S be a simply connected orthogonal polygon in the plane. The set S is a union of two sets which are starshaped via staircase paths (i.e., orthogonally starshaped) if and only if for every three points of S, at least two of these points see (via staircase paths) a common point of S. Moreover, the simple connectedness condition cannot be deleted.     

A sperner-type theorem

Let P=P ₁×P ₂×...×P _M be the direct product of symmetric chain orders P ₁, P ₂, ..., P _M . Let F be a subset of P containing no l+1 elements which are identical in M–1 components and linearly ordered in the Mth one. Then max |F|cM ^1/2lW(P), where W(P) is the cardinality of the largest level of P, and c is independent of P, M and l. Infinitely many P show that this result is best possible for every M and l apart from the constant factor c.     

Points of local nonconvexity and sets which are almost starshaped

Let Sø be a bounded connected set in R ², and assume that every 3 or fewer lnc points of S are clearly visible from a common point of S. Then for some point p in S, the set A{s : s in S and [p, s] S} is nowhere dense in S. Furthermore, when S is open, then S in starshaped.     

A topological central point theorem

In this paper a generalized topological central point theorem is proved for maps of a simplex to finite-dimensional metric spaces. Similar generalizations of the Tverberg theorem are considered.     

A fractional Helly theorem for convex lattice sets

A set of the form , where is convex and denotes the integer lattice, is called a convex lattice set. It is known that the Helly number of d-dimensional convex lattice sets is 2^d. We prove that the fractional Helly number is only d+1: For every d and every α∈(0,1] there exists β>0 such that whenever F₁,…,F_n are convex lattice sets in such that for at least index sets I⊆{1,2,…,n} of size d+1, then there exists a (lattice) point common to at least βn of the F_i. This implies a (p,d+1)-theorem for every p?d+1; that is, if is a finite family of convex lattice sets in such that among every p sets of , some d+1 intersect, then has a transversal of size bounded by a function of d and p.     

Krasnosel'skii numbers for bounded finitely starlike sets inR d

For eachk andd, 1kd, definef(d, d)=d+1 andf(d, k)=2d if 1kd–1. The following results are established:Let be a uniformly bounded collection of compact, convex sets inR ^d . For a fixedk, 1kd, dim {MM in }k if and only if for some > 0, everyf(d, k) members of contain a commonk-dimensional set of measure (volume) at least.LetS be a bounded subset ofR ^d . Assume that for some fixedk, 1kd, there exists a countable family of (k–l)-flats {H _i :i1} inR ^d such that clS S {H_i i 1 } and for eachi1, (clS S) H _i has (k–1) dimensional measure zero. Every finite subset ofS sees viaS a set of positivek-dimensional measure if and only if for some>0, everyf(d,k) points ofS see viaS a set ofk-dimensional measure at least .The numbers off(d,d) andf(d, 1) above are best possible.Supported in part by NSF grant DMS-8705336.     

Some Krasnosel'skii numbers for finitely starlike sets in the plane

Let S be a subset of the plane. In case (int cl S) S = , then S is finitely starlike if and only if every 4 points of S see via S a common point. In case (int cl S) S has at most countably many components, each a singleton set, then S is finitely starlike if and only if every 5 points of S see via S a common point. Each of the numbers 4 and 5 is best possible. Examples show that these results fail without suitable restrictions on (int cl S) S. Moreover, a final example shows that if a general Krasnosel'skii number . exists to characterize finitely starlike sets in the plane, then > 9.     

A characterization theorem for tilings having countably many singular points

LetT be a tiling of the plane. At most countably many points of U{bdry T T inT} fail to lie in a nondegenerate edge ofT if and only ifT has at most countably many singular points. The result fails without the requirement that the edges be nondegenerate. Moreover, countably many cannot be replaced by finitely many in the theorem.     

A general duality theorem for marginal problems

Summary Given probability spaces (X _i ,A _i ,P _i ),i=1, 2 letM(P ₁,P ₂) denote the set of all probabilities on the product space with marginalsP ₁ andP ₂ and leth be a measurable function on (X ₁×X ₂,A ₁ A ₂). In order to determine supfh dP where the supremum is taken overP inM(P ₁,P ₂), a general duality theorem is proved. Only the perfectness of one of the coordinate spaces is imposed without any further topological or tightness assumptions. An example without any further topological or tightness assumptions. An example is given to show that the assumption of perfectness is essential. Applications to probabilities with given marginals and given supports, stochastic order and probability metrics are included.     

j-partitions for visible shorelines

Summary LetC be a compact set inR ². A setS R ² C is said to have aj-partition relative toC if and only if there existj or fewer pointsc ₁,, c _j inC such that each point ofS sees somec _i via the complement ofC. Letm, j be fixed integers, 3 m, 2 j, and writem (uniquely) asm = qj + r, where 1 r j. Assume thatC is a convexm-gon in R², withS R ² C. Forq = 0 orq = 1, the setS has aj-partition relative toC. Forq 2,S has aj-partition relative toC if and only if every (qj + 1)-member subset ofS has aj-partition relative toC, and the Helly numberqj + 1 is best possible.IfC is a disk, no such Helly number exists.     

A topological colorful Helly theorem

Let be d+1 families of convex sets in . The Colorful Helly Theorem (see (Discrete Math. 40 (1982) 141)) asserts that if for all choices of then there exists an 1?i?d+1 such that .Our main result is both a topological and a matroidal extension of the colorful Helly theorem. A simplicial complex X is d-Leray if for all induced subcomplexes Y⊂X and i?d.Theorem.LetXbe ad-Leray complex on the vertex setV. Suppose M is a matroidal complex on the same vertex setVwith rank functionρ. IfM⊂Xthen there exists a simplexτ∈Xsuch thatρ(V−τ)?d.     

Generalizations of Tarski's fixed point theorem for order varieties of complete meet semilattices

A poset P is -conditionally complete ( a cardinal) if every set X P all of whose subsets of cardinality < have an upper bound has a least upper bound. For we characterize the subposets of a -complete poset which can occur as the set of fixed points of some montonic function on P. This yields a generalization of Tarski's fixed point theorem. We also show that for every the class of -conditionally complete posets forms an order variety and we exhibit a simple generating poset for each such class.Research supported in part by NSERC while the author was visiting Professor Ivo Rosenberg at the Université de Montreal.Research supported in part by NSF-grant DMS-8703743.     

On the equipartition of plane convex bodies and convex polygons

In this paper we consider the problem of partitioning a plane compact convex body into equal-area parts, i.e., an equipartition, by means of chords. We prove two basic results that hold with some specific exceptions: (a) When chords are pairwise non-crossing, the dual tree of the partition has to be a path, (b) A convex n-gon admits no equipartition produced by more than n chords having a common interior point.     

A vector-sum theorem in two-dimensional space

Given a finite setX of vectors from the unit ball of the max norm in the twodimensional space whose sum is zero, it is always possible to writeX = {x₁, , x_n} in such a way that the first coordinates of each partial sum lie in [–1, 1] and the second coordinates lie in [–C, C] whereC is a universal constant.