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.     

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.     

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.     

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.     

New Combinations of Convex Sets

The family of convex sets in a (finite dimensional) real vector space admits several unary and binary operations – dilatation, intersection, convex hull, vector sum – which preserve convexity. These generalize to convex functions, where there are in fact further operations of this kind. Some of the latter may be regarded as combinations of two such operations, acting on complementary subspaces. In this paper, a general theory of such mixed operations is introduced, and some of its consequences developed.     

具有最小度距离的双圈图

记G（n）为所有n阶连通简单双圈图所构成的集合．本文主要讨论G（n）按其度距离从小到大进行排序的问题,并确定了该序的前两个图及其相应的度距离,其中具有最小度距离的图是由星图K1,n-1的一个悬挂点与另外两个悬挂点之间各连上一条边所得的图Sn．