Convex decompositions in the plane and continuous pair colorings of the irrationals

We address the structure of nonconvex closed subsets of the Euclidean plane. A closed subsetS⊆ℝ² which is not presentable as a countable union of convex sets satisfies the following dichotomy:

p-Congruences onp-regular semigroups

A pair (S, P) of a regular semigroupsS and a subsetP ofE _s whereE _s is the set of all idempotent elements ofS is called aP-regular semigroupS(P) if it satisfies the following:

On the intersection of maximalm-convex subsets

A subsetS of a real linear spaceE is said to bem-convex providedm≧2, there exist more thanm points inS, and for eachm distinct points ofS at least one of the ( ₂ ^m ) segments between thesem points is included inS. InE, letxy denote the segment between two pointsx andy. For any pointx inSυE, letS _x ={y: xyυS}. The kernel of a setS is then defined as {xεS: S _x=S}. It is shown that the kernel of a setS is always a subset of the intersection of all maximalm-convex subsets ofS. A sufficient condition is given for the intersection of all the maximalm-convex subsets of a setS to be the kernel ofS.     

Analytic and polyhedral approximation of convex bodies in separable polyhedral Banach spaces

A closed, convex and bounded setP in a Banach spaceE is called a polytope if every finite-dimensional section ofP is a polytope. A Banach spaceE is called polyhedral ifE has an equivalent norm such that its unit ball is a polytope. We prove here:

A Helmholtz-Lie type characterization of ellipsoids,II

A closed convex surfaceS in is an ellipsoid if and only if for anyx, y εS there is an affinity mappingx ontoy and a neighborhood ofx inS onto a neighborhood ofy inS.     

An extension of the Erdős-Szekeres theorem on large angles

The existence of a functionn(ε) (ε>0) is established such that given a finite setV in the plane there exists a subsetW⊆V, |W|<n(ε) with the property that for anyv εV\ W there are two pointsw ₁,w ₂ εW such that the angle ∢(w ₁ vw ₂)>π-ε.     

Intersectional properties concerning planarm-convex sets

LetC be a collection of closed sets in the plane, and letS=∩C. (1) If IncC ⊆ kerS for allC inC and if dim kerS≧1, thenS is a union of three (or fever) convex sets. In particular, the results holds when the members ofC are 3-convex sets, all having the same kernelK, provided dimK≧1. (2) IfC is a finite collection ofm-convex sets such that ∩{kerC:C inC inC} ≠ ⊘,S~ IncS is connected, and for someZ inC, lncC⊆ lncZ for allC inC, thenS ism-convex.     

A helmholtz-lie type characterization of ellipsoids,I

A closed convex surfaceS in withd odd, is an ellipsoid if and only if it has the following property: for any pair of pointsx, y inS there is an affine transformation which mapsx ontoy and a suitable neighborhood ofx inS onto a neighborhood ofy inS.     

A sparse graph almost as good as the complete graph on points inK dimensions

A setV ofn points ink-dimensional space induces a complete weighted undirected graph as follows. The points are the vertices of this graph and the weight of an edge between any two points is the distance between the points under someL _p metric. Let ε≤1 be an error parameter and letk be fixed. We show how to extract inO(n logn+ε ^−k log(1/ε)n) time a sparse subgraphG=(V, E) of the complete graph onV such that: (a) for any two pointsx, y inV, the length of the shortest path inG betweenx andy is at most (1+∈) times the distance betweenx andy, and (b)|E|=O(ε^−k n).     

Path-closed sets

Given a digraphG = (V, E), call a node setT ⊆V path-closed ifv, v′ εT andw εV is on a path fromv tov′ impliesw εT. IfG is the comparability graph of a posetP, the path-closed sets ofG are the convex sets ofP. We characterize the convex hull of (the incidence vectors of) all path-closed sets ofG and its antiblocking polyhedron inR ^v , using lattice polyhedra, and give a minmax theorem on partitioning a given subset ofV into path-closed sets. We then derive good algorithms for the linear programs associated to the convex hull, solving the problem of finding a path-closed set of maximum weight sum, and prove another min-max result closely resembling Dilworth’s theorem.     

On sets having finitely many points of local nonconvexity and propertyP m

If a pointq ofS has the property that each neighborhood ofq contains pointsx andy such that the segmentxy is not contained byS, q is called a point of local nonconvexity ofS. LetQ denote the set of points of local nonconvexity ofS. Tietze’s well known theorem that a closed connected setS in a linear topological space is convex ifQ=φ is generalized in the result:If S is a closed set in a linear topological space such that S ∼ Q is connected and |Q|=n<∞,then S is the union of n+1or fewer closed convex sets. Letk be the minimal number of convex sets needed in a convex covering ofS. Bounds fork in terms ofm andn are obtained for sets having propertyP _m and |Q|=n.     

Extensions of the measurable choice theorem by means of forcing

Using the method of forcing of set theory, we prove the following two theorems on the existence of measurable choice functions: LetT be the closed unit interval [0,1] and letm be the usual Lebesgue measure defined on the Borel subsets ofT. Theorem1. LetS⊂T×T be a Borel set such that for alltεT,S _t ^def={x|(t,x)εS} is countable and non-empty. Then there exists a countable series of Lebesgue-measurable functionsf _n: T→T such thatS _t={f_n(t)|nεω} for alltε[0,1],W _x={y|(x,y)εW} is uncountable. Then there exists a functionh:[0,1]×[0,1]→W with the following properties: (a) for each xε[0,1], the functionh(x,·) is one-one and ontoW _x and is Borel measurable; (b) for eachy, h(·, y) is Lebesgue measurable; (c) the functionh is Lebesgue measurable.     

A decomposition theorem form-convex sets

LetS be a closedm-convex subset of the plane,m≧2,Q the set of points of local nonconvexity ofS, with convQ ⊆S. If there is some pointp in [(bdryS) ∩ (kerS)] ∼Q, thenS is a union ofm−1 closed convex sets. The result is best possible for everym.     

Improved bounds on weak ε-nets for convex sets

LetS be a set ofn points in ℝ ^d . A setW is aweak ε-net for (convex ranges of)S if, for anyT⊆S containing εn points, the convex hull ofT intersectsW. We show the existence of weak ε-nets of size , whereβ ₂=0,β ₃=1, andβ _d ≈0.149·2 ^d-1(d-1)!, improving a previous bound of Alonet al. Such a net can be computed effectively. We also consider two special cases: whenS is a planar point set in convex position, we prove the existence of a net of sizeO((1/ε) log^1.6(1/ε)). In the case whereS consists of the vertices of a regular polygon, we use an argument from hyperbolic geometry to exhibit an optimal net of sizeO(1/ε), which improves a previous bound of Capoyleas. Work by Bernard Chazelle has been supported by NSF Grant CCR-90-02352 and the Geometry Center. Work by Herbert Edelsbrunner has been supported by NSF Grant CCR-89-21421. Work by Michelangelo Grigni has been supported by NSERC Operating Grants and NSF Grant DMS-9206251. Work by Leonidas Guibas and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Emo Welzl and Micha Sharir has been supported by a grant from the G.I.F., the German-Israeli Foundation for Scientific Research and Development. Work by Micha Sharir has also been supported by NSF Grant CCR-91-22103, and by a grant from the Fund for Basic Research administered by the Israeli Academy of Sciences.     

Convexity and a certain propertyP m

The propertyP _m (directly analogous to Valentine’s propertyP ₃) is used to prove several curious results concerning subsets of a topological linear space, among them the following: (a) If a closed setS has propertyP _m and containsk points of local nonconvexity no distinct pair of which can see each other viaS, thenS is the union ofm − k − 1 or fewer starshaped sets. (b) Any closed connected set with propertyP _m is polygonally connected. (c) A closed connected setS with propertyP _m is anL _m−1 set (each pair of points may be joined by a polygonal arc ofm − 1 of fewer sides inS). (d) A finite-dimensional set with propertyP _m is anL _{2m − 3} set. A new proof of Tietze’s theorem on locally convex sets is given, and various examples refute certain plausible conjectures.     

Center conditions II: Parametric and model center problems

We consider an Abel equation (*)y’=p(x)y ² +q(x)y ³ withp(x), q(x) polynomials inx. A center condition for (*) (closely related to the classical center condition for polynomial vector fields on the plane) is thaty ₀=y(0)≡y(1) for any solutiony(x) of (*). We introduce a parametric version of this condition: an equation (**)y’=p(x)y ² +εq(x)y ³ p, q as above, ℂ, is said to have a parametric center, if for any ε and for any solutiony(ε,x) of (**),y(ε,0)≡y(ε,1). We show that the parametric center condition implies vanishing of all the momentsm _k (1), wherem _k (x)=∫ ₀ ^{x pk} (t)q(t)(dt),P(x)=∫ ₀ ^x p(t)dt. We investigate the structure of zeroes ofm _k (x) and on this base prove in some special cases a composition conjecture, stated in [10], for a parametric center problem. The research of the first and the third author was supported by the Israel Science Foundation, Grant No. 101/95-1 and by the Minerva Foundation.     

Semigroup actions on homogeneous spaces

LetG be a connected semi-simple Lie group with finite center andS⊄G a subsemigroup with interior points. LetG/L be a homogeneous space. There is a natural action ofS onG/L. The relationx≤y ify ∈Sx, x, y ∈G/L, is transitive but not reflexive nor symmetric. Roughly, a control set is a subsetD ⊄G/L, inside of which reflexivity and symmetry for ≤ hold. Control sets are studied inG/L whenL is the minimal parabolic subgroup. They are characterized by means of the Weyl chambers inG meeting intS. Thus, for eachw ∈W, the Weyl group ofG, there is a control setD _w .D ₁ is the only invariant control set, and the subsetW(S)={w:D _w =D ₁} turns out to be a subgroup. The control sets are determined byW(S)/W. The following consequences are derived: i)S=G ifS is transitive onG/H, i.e.Sx=G/H for allx ∈G/H. HereH is a non discrete closed subgroup different fromG andG is simple. ii)S is neither left nor right reversible ifS #G iii)S is maximal only if it is the semigroup of compressions of a subset of some minimal flag manifold. Research partially supported by CNPq grant n^o 50.13.73/91-8     

On the separator of subsets of semigroups

By the separator \operatornameSepA\operatorname{\mathit{Sep}}A of a subset A of a semigroup S we mean the set of all elements x of S which satisfy conditions xA⊆A, Ax⊆A, x(S−A)⊆(S−A), (S−A)x⊆(S−A). In this paper we deal with the separator of subsets of semigroups.     

A nonlinear version of Roth's theorem for sets of positive density in the real line

It is proved that given ε>0, there is δ(ε)>0 such that ifS is a measurable set of [0,N], |S|>εN, then there is a triplex, x+h, x+h ² inS withh satisfyingh>δ(ε)N ^1/2. The argument is related to [B] and uses the behavior of certain non-linear convolution-type operators. The method can be adapted in a variety of situations. For instance, it can be used to prove the analogue of the previous statement with the square replaced by another power,h ³,h ⁴ etc.     

Finite unions of shore sets

Adendroid is an arcwise connected hereditarily unicoherent continuum. Ashore set in a dendroidX is a subsetA ofX such that, for each ε>0, there exists a subdendroidB ofX such that the Hausdorff distance fromB toX is less then ε andB∩A=θ. Answering a question by I. Puga, in this paper we prove that the finite union of pairwise disjoint shore subdendroids of a dendroidX is a shore set. We also show that the hypothesis that the shore subdendroids are disjoint is necessary. It is still unknown if the union of two closed disjoint shore subsets of a dendroidX is also shore set.