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 better decomposition theorem for simply connected m-convex sets

A set S in R^d is said to be m-convex, m ? 2, if and only if for every m points in S, at least one of the line segments determined by these points lies in S. For S a closed m-convex set in R², various decomposition theorems have been obtained to express S as a finite union of convex sets. However, the previous bounds may be lowered further, and we have the following result:In case S is simply connected, then S is a union of σ(m) or fewer convex sets, where $\text{σ(m) = [(m ?}\text{N}\text{)(m ?}\text{3}\text{2}\text{) +}\text{3}\text{2}\text{]}$.Moreover, this result induces an improved decomposition in the general case as well.     

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.     

On then-cutset property

For a partially ordered setP and an elementx ofP, a subsetS ofP is called a cutset forx inP if every element ofS is noncomparable tox and every maximal chain ofP meets {x}∪S. We letc(P) denote the smallest integerk such that every elementx ofP has a cutsetS with ‖S‖?k: Ifc(P)?n we say thatP has then-cutset property. Our results bear on the following question: givenP, what is the smallestn such thatP can be embedded in a partially ordered set having then-cutset property? As usual, 2 ⁿ denotes the Boolean lattice of all subsets of ann-element set, andB _n denotes the set of atoms and co-atoms of 2 ⁿ . We establish the following results: (i) a characterization, by means of forbidden configurations, of whichP can be embedded in a partially ordered set having the 1-cutset property; (ii) ifP contains a copy of 2 ⁿ , thenc(P)?2^[n/2]?1; (iii) for everyn>3 there is a partially ordered setP containing 2 ⁿ such thatc(P)<c(2 ⁿ ); (iv) for every positive integern there is a positive integerN such that, ifB _m is contained in a partially ordered set having then-cutset property, thenm?N.     

AnR danalogue of Valentine’s theorem on 3-convex sets

This paper deals with anR ^danalogue of a theorem of Valentine which states that a closed 3-convex setS in the plane is decomposable into 3 or fewer closed convex sets. In Valentine’s proof, the points of local nonconvexity ofS are treated as vertices of a polygonP contained in the kernel ofS, yielding a decomposition ofS into 2 or 3 convex sets, depending on whetherP has an even or odd number of edges. Thus the decomposition actually depends onc(P′), the chromatic number of the polytopeP′ dual toP. A natural analogue of this result is the following theorem: LetS be a closed subset ofR ^d, and letQ denote the set of points of local nonconvexity ofS. We require thatQ be contained in the kernel ofS and thatQ coincide with the set of points in the union of all the (d − 2)-dimensional faces of somed-dimensional polytopeP. ThenS is decomposable intoc(P′) closed convex sets.     

Stability theorems for projections of convex sets

LetH ^n?1 denote the set of all (n ? 1)-dimensional linear subspaces of euclideann-dimensional spaceE ⁿ (n≧3), and letJ andK be two compact convex subsets ofE ⁿ. It is well-known thatJ andK are translation equivalent (or homothetic) if for allH ∈H ^n?1 the respective orthogonal projections, sayJ _H, K_H, are translation equivalent (or homothetic). This fact gives rise to the following stability problem: Ifε≧0 is given, and if for everyH ∈H ^n?1 a translate (or homothetic copy) ofK _H is within Hausdorff distanceε ofJ _H, how close isJ to a nearest translate (or homothetic copy) ofK? In the case of translations it is shown that under the above assumptions there is always a translate ofK within Hausdorff distance (1 + 2√2)ε ofJ. Similar results for homothetic transformations are proved and applications regarding the stability of characterizations of centrally symmetric sets and spheres are given. Furthermore, it is shown that these results hold even ifH ^n?1 is replaced by a rather small (but explicitly specified) subset ofH ^n?1.     

Essential and inessential points of local nonconvexity

LetS be a closed connected subset of a Hausdorff linear topological space,Q the points of local nonconvexity ofS, E the essential members ofQ, N the inessential. IfS～Q is connected, then the following are true: Theorem 1.If Q ?Øis countable, then S is planar. Theorem 2.If Q is finite and nonempty, then cardE≧cardN+1. Theorem 3.If SυR ² and N is infinite, then E is infinite.     

Sets in a euclidean space which are not a countable union of convex subsets

We prove that if a closed planar setS is not a countable union of convex subsets, then exactly one of the following holds:

On visibility and covering by convex sets

A setX⊆ℝ ^d isn-convex if among anyn of its points there exist two such that the segment connecting them is contained inX. Perles and Shelah have shown that any closed (n+1)-convex set in the plane is the union of at mostn ⁶ convex sets. We improve their bound to 18n ³, and show a lower bound of order Ω(n ²). We also show that ifX⊆ℝ² is ann-convex set such that its complement has λ one-point path-connectivity components, λ<∞, thenX is the union ofO(n ⁴+n ²λ) convex sets. Two other results onn-convex sets are stated in the introduction (Corollary 1.2 and Proposition 1.4). Research supported by Charles University grants GAUK 99/158 and 99/159, and by U.S.-Czechoslovak Science and Technology Program Grant No. 94051. Part of the work by J. Matoušek was done during the author’s visits at Tel Aviv University and The Hebrew University of Jerusalem. Part of the work by P. Valtr was done during his visit at the University of Cambridge supported by EC Network DIMANET/PECO Contract No. ERBCIPDCT 94-0623.     

Unions of three starshaped sets in R2

LetS be a compact, simply connected set inR ². If every boundary point ofS is clearly visible viaS from at least one of the three pointsa, b, c, thenS is a union of three starshaped sets whose kernels containa, b, c, respectively. The result fails when the number three is replaced by four.As a partial converse, ifS is a union of three starshaped sets whose kernels containa, b, c, respectively, then the set of points in the boundary ofS clearly visible from at least one ofa, b, orc is dense in the boundary ofS.Supported in part by NSF grant DMS-8705336.     

An example concerning unions of two starshaped sets in the plane

LetS be a closed, simply connected subset of the plane,J a line segment (or a one-pointed set),J⊂S. If for every three points ofS there is a point ofJ seeing at least two of these points viaS, thenS is a union of two starshaped sets. IfJ⊈S or ifS is not simply connected, the result fails.     

A decomposition theorem for χ1-convex sets

A set S in $\text{R}$ is said to be χ-convex if and only if S does not contain a visually independent subset having cardinality χ. It is natural to ask when an χ-convex set may be expressed as a countable union of convex sets. Here it is proved that if S is a closed χ-convex set in the plane and $\text{R}$ has at most finitely many bounded components, then S is a countable union of convex sets. A parallel result holds in $\text{R}$ when S is a closed χ-convex set which contains all triangular regions whose relative boundaries are in S. However, the result fails for arbitrary χ-convex sets, even in the plane.     

Intersection properties of boxes in R d

A family of sets is calledn-pierceable if there exists a set ofn points such that each member of the family contains at least one of the points. Helly’s theorem on intersections of convex sets concerns 1-pierceable families. Here the following Helly-type problem is investigated: Ifd andn are positive integers, what is the leasth =h(d, n) such that a family of boxes (with parallel edges) ind-space isn-pierceable if each of itsh-membered subfamilies isn-pierceable? The somewhat unexpected solution is: (i)h(d, 2) equals3d for oddd and 3d?1 for evend; (ii)h(2, 3)=16; and (iii)h(d, n) is infinite for all (d, n) withd≧2 andn≧3 except for (d, n)=(2, 3).     

A lower bound for the convexity number of some graphs

Given a connected graphG, we say that a setC ?V(G) is convex inG if, for every pair of verticesx, y ∈ C, the vertex set of everyx-y geodesic inG is contained inC. The convexity number ofG is the cardinality of a maximal proper convex set inG. In this paper, we show that every pairk, n of integers with 2 ≤k ≤ n?1 is realizable as the convexity number and order, respectively, of some connected triangle-free graph, and give a lower bound for the convexity number ofk-regular graphs of ordern withn>k+1.     

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.     

Sets with a mode

LetM be a point andS be a compact set inR ² such thatS is the closure of its interior. The theorem desired says that ifM is a mode ofS thenS is convex and centrally symmetric with respect toM. Some conditions on the boundary ofS are needed for the proof given.     

Minimal quadratic residue cyclic codes of length 2 n

LetF be a finite field of prime power orderq(odd) and the multiplicative order ofq modulo 2 ⁿ (n>1) be ?(2 ⁿ )/2. Ifn>3, thenq is odd number(prime or prime power) of the form 8m±3. Ifq=8m?3, then the ring $$R_{2^n } = F\left[ x \right]/< x^{2^n } - 1 > $$ has 2n primitive idempotents. The explicit expressions for these primitive idempotents are obtained and the minimal QR cyclic codes of length 2 ⁿ generated by these idempotents are completely described. Ifq=8m+3 then the expressions for the 2n?1 primitive idempotents ofR ₂ ⁿ are obtained. The generating polynomials and the upper bounds of the minimum distance of minimal QR cyclic codes generated by these 2n?1 idempotents are also obtained. The casen=2, 3 is dealt separately.     

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.     

Epigraph of operator functions

It is known that a real function f is convex if and only if the set E(f) = {(x, y) ∈ ? × ?; f (x) ≤ y}, the epigraph of f is a convex set in ?². We state an extension of this result for operator convex functions and C^?-convex sets as well as operator log-convex functions and C^?-log-convex sets. Moreover, the C^?-convex hull of a Hermitian matrix has been represented in terms of its eigenvalues.     

The dimension of intersections of convex sets II

The subject of this paper is a Helly type theorem which solves the following problem: Find the smallest number β= β(j,k,n) having the following property: IfG is any finite family ofβ + 1 convex sets in Euclideann-space and if the intersection of everyβ members ofG is at leastk-dimensional, then the intersection of all members ofG is at leastj-dimensional.