Convex Sets in Lexicographic Products of Graphs

Geodesic convex sets, Steiner convex sets, and J-convex (alias induced path convex) sets of lexicographic products of graphs are characterized. The geodesic case in particular rectifies Theorem 3.1 in Canoy and Garces (Graphs Combin 18(4):787–793, 2002).     

Intervals and Convex Sets in Strong Product of Graphs

In this note we consider intervals and convex sets of strong product. Vertices of an arbitrary interval of ${G\boxtimes H}$ are classified with shortest path properties of one factor and a walk properties of a slightly modified second factor. The convex sets of the strong product are characterized by convexity of projections to both factors and three other local properties, one of them being 2-convexity.     

Intersection Theorems for Infinite Families of Convex Sets in Graphs

We prove several Helly-type theorems for infinite families of geodesically convex sets in infinite graphs. That is, we determine the least cardinal n such that any family of (particular) convex sets in some infinite graph has a nonempty intersection whenever each of its subfamilies of cardinality less than n has a nonempty intersection. We obtain some general compactness theorems, and some particular results for pseudo-modular graphs, strongly dismantlable graphs and ball-Helly graphs.     

Minimal Convex k-Gons Containing a Given Convex Polygon

There is a k-gon of minimal area containing a given convex n-gon (k<n) such that k-1 sides of the n-gon lie on the sides of the k-gon. All midpoints of the sides of the k-gon belong to the n-gon. Bibliography: 3 titles.     

Remarks on Minimal Sets for Cyclic Mappings in Uniformly Convex Banach Spaces

In this article, we prove that every nonempty and convex pair of subsets of uniformly convex in every direction Banach spaces has the proximal normal structure and then we present a best proximity point theorem for cyclic relatively nonexpansive mappings in such spaces. We also study the structure of minimal sets of cyclic relatively nonexpansive mappings and obtain the existence results of best proximity points for cyclic mappings using some new geometric notions on minimal sets. Finally, we prove a best proximity point theorem for a new class of cyclic contraction-type mappings in the setting of uniformly convex Banach spaces and so, we improve the main conclusions of Eldred and Veeramani.     

Constructible Convex Sets

We investigate when closed convex sets can be written as countable intersections of closed half-spaces in Banach spaces. It is reasonable to consider this class to comprise the constructible convex sets since such sets are precisely those that can be defined by a countable number of linear inequalities, hence are accessible to techniques of semi-infinite convex programming. We also explore some model theoretic implications. Applications to set convergence are given as limiting examples.     

Finding Convex Sets in Convex Position

Let F{\cal{F}} denote a family of pairwise disjoint convex sets in the plane. F{\cal{F}} is said to be in convex position, if none of its members is contained in the convex hull of the union of the others. For any fixed k 3 5k\ge5, we give a linear upper bound on P_k(n)P_k(n), the maximum size of a family F{\cal{F}} with the property that any k members of F{\cal{F}} are in convex position, but no n are.     

On Closed Sets with Convex Projections

A shadow of a subset A of Rⁿ is the image of A under a projectiononto a hyperplane. Let C be a closed nonconvex set in Rⁿ suchthat the closures of all its shadows are convex. If, moreover,there are n independent directions such that the closures ofthe shadows of C in those directions are proper subsets of therespective hyperplanes then it is shown that C contains a copyof R^n–2. Also for every closed convex set B ‘minimalimitations’ C of B are constructed, that is, closed subsetsC of B that have the same shadows as B and that are minimalwith respect to dimension.     

Convex Partitions of Graphs

A set of vertices S of a graph G is convex if all vertices of every geodesic between two of its vertices are in S. We say that G is k-convex if V(G) can be partitioned into k convex sets. The convex partition number of G is the least k ⩾ 2 for which G is k-convex. In this paper we examine k-convexity of graphs. We show that it is NP-complete to decide if G is k-convex, for any fixed k ⩾ 2. We describe a characterization for k-convex cographs, leading to a polynomial time algorithm to recognize if a cograph is k-convex. Finally, we discuss k-convexity for disconnected graphs.     

Translating Finite Sets into Convex Sets

Let X be a reflexive Banach space, and let C X be a closed,convex and bounded set with empty interior. Then, for every > 0, there is a nonempty finite set F X with an arbitrarilysmall diameter, such that C contains at most .|F| points ofany translation of F. As a corollary, a separable Banach spaceX is reflexive if and only if every closed convex subset ofX with empty interior is Haar null. 2000 Mathematics SubjectClassification 46B20 (primary), 28C20 (secondary).     

Graphs with a Small Number of Nonnegative Eigenvalues

In this paper, by means of computer checking, all simple graphs with at most two nonnegative eigenvalues, and all minimal simple graphs with exactly two (respectively, three) nonnegative eigenvalues are determined. Received: April 5, 1996 / Revised: May 2, 1997     

On the Minimal Number of Edges in Induced Subgraphs of Special Distance Graphs

Mathematical Notes - Three new theorems are proved in the paper, which give bounds for the number of edges in induced subgraphs of a special distance graph.     

Minimal Kakeya Sets

Blokhuis and Mazzocca (A. Blokhuis and F. Mazzocca, The finite field Kakeya problem (English summary). Building bridges. Bolyai Soc Math Stud 19 (2008) 205–218) provide a strong answer to the finite field analog of the classical Kakeya problem, which asks for the minimum size of a point set in an affine plane π that contains a line in every direction. In this article, we consider the related problem of minimal Kakeya sets, namely Kakeya sets containing no smaller Kakeya sets, and provide an interesting infinite family of minimal Kakeya sets that are not of extremal size.     

Sets with a Prescribed Number of Power Invariants

Let A₁,...,A_n be points in , let be a fixed point, let p be a positive integer, and let ₁,...,_n be positive real numbers. If the does not depend on the position of M on a sphere with center O, then one says that the point system {A₁,...,A_n} has an invariant of degree p with weight system {,...,_n}. It is proved that for arbitrary positive integers d and N there exists a finite point system having invariants of degrees p=1,...,N with common positive weight system {₁,...,_n}. Bibliography: 2 titles.     

Extremal Convex Planar Sets

Each convex planar set K has a perimeter C, a minimum width E, an area A, and a diameter D. The set of points (E,C, A^1/2, D) corresponding to all such sets is shown to occupy a cone in the non-negative orthant of R⁴with its vertex at the origin. Its three-dimensional cross section S in the plane D = 1 is investigated. S lies in a rectangular parallelepiped in R³. Results of Lebesgue, Kubota, Fukasawa, Sholander, and Hemmi are used to determine some of the boundary surfaces of S, and new results are given for the other boundary surfaces. From knowledge of S, all inequalities among E, C ,A, and D can be found.     

Covering Planar Graphs with a Fixed Number of Balls

In this note we prove that there exists a constant ρ such that any planar graph G of diameter ≤ 2R can be covered with at most ρ balls of radius R, a result conjectured by Gavoille, Peleg, Raspaud, and Sopena in 2001.