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.     

On the Convexity Number of Graphs

A set of vertices S in a graph is convex if it contains all vertices which belong to shortest paths between vertices in S. The convexity number c(G) of a graph G is the maximum cardinality of a convex set of vertices which does not contain all vertices of G. We prove NP-completeness of the problem to decide for a given bipartite graph G and an integer k whether c(G) ≥ k. Furthermore, we identify natural necessary extension properties of graphs of small convexity number and study the interplay between these properties and upper bounds on the convexity number.     

The Convexity Number of a Graph

 For two vertices u and v of a connected graph G, the set I[u,v] consists of all those vertices lying on a u−v shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤l≤k≤n−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented. Received: August 19, 1998 Final version received: May 17, 2000     

Transversal fluctuations for increasing subsequences on the plane

Consider a realization of a Poisson process in ℝ² with intensity 1 and take a maximal up/right path from the origin to (N, N) consisting of line segments between the points, where maximal means that it contains as many points as possible. The number of points in such a path has fluctuations of order N ^χ, where χ = 1/3, [BDJ]. Here we show that typical deviations of a maximal path from the diagonal x = y is of order N ^ξ with ξ = 2/3. This is consistent with the scaling identity χ = 2ξ− 1 which is believed to hold in many random growth models. Received: 16 April 1999 / Revised version: 5 July 1999 / Published online: 14 February 2000     

Convexes divisibles IV : Structure du bord en dimension 3

Divisible convex sets IV: Boundary structure in dimension 3 Let Ω be an indecomposable properly convex open subset of the real projective 3-space which is divisible i.e. for which there exists a torsion free discrete group Γ of projective transformations preserving Ω such that the quotient M := Γ\Ω is compact. We study the structure of M and of ∂Ω, when Ω is not strictly convex: The union of the properly embedded triangles in Ω projects in M onto an union of finitely many disjoint tori and Klein bottles which induces an atoroidal decomposition of M. Every non extremal point of ∂Ω is on an edge of a unique properly embedded triangle in Ω and the set of vertices of these triangles is dense in the boundary of Ω (see Figs. 1 to 4). Moreover, we construct examples of such divisible convex open sets Ω.      

Convex Sets in Acyclic Digraphs

A non-empty set X of vertices of an acyclic digraph is called connected if the underlying undirected graph induced by X is connected and it is called convex if no two vertices of X are connected by a directed path in which some vertices are not in X. The set of convex sets (connected convex sets) of an acyclic digraph D is denoted by and its size by co(D) (cc(D)). Gutin et al. (2008) conjectured that the sum of the sizes of all convex sets (connected convex sets) in D equals Θ(n · co(D)) (Θ(n · cc(D))) where n is the order of D. In this paper we exhibit a family of connected acyclic digraphs with and . We also show that the number of connected convex sets of order k in any connected acyclic digraph of order n is at least n − k + 1. This is a strengthening of a theorem of Gutin and Yeo.     

Maximizing Voronoi Regions of a Set of Points Enclosed in a Circle with Applications to Facility Location

In this paper we introduce an optimization problem which involves maximization of the area of Voronoi regions of a set of points placed inside a circle. Such optimization goals arise in facility location problems consisting of both mobile and stationary facilities. Let ψ be a circular path through which mobile service stations are plying, and S be a set of n stationary facilities (points) inside ψ. A demand point p is served from a mobile facility plying along ψ if the distance of p from the boundary of ψ is less than that from any member in S. On the other hand, the demand point p is served from a stationary facility p _i  ∈ S if the distance of p from p _i is less than or equal to the distance of p from all other members in S and also from the boundary of ψ. The objective is to place the stationary facilities in S, inside ψ, such that the total area served by them is maximized. We consider a restricted version of this problem where the members in S are placed equidistantly from the center o of ψ. It is shown that the maximum area is obtained when the members in S lie on the vertices of a regular n-gon, with its circumcenter at o. The distance of the members in S from o and the optimum area increases with n, and at the limit approaches the radius and the area of the circle ψ, respectively. We also consider another variation of this problem where a set of n points is placed inside ψ, and the task is to locate a new point q inside ψ such that the area of the Voronoi region of q is maximized. We give an exact solution of this problem when n = 1 and a (1 − ε)-approximation algorithm for the general case.     

Entering and leaving j-facets

Let S be a set of n points in d -space, no i+1 points on a common (i-1) -flat for 1 ≤ i ≤ d . An oriented (d-1) -simplex spanned by d points in S is called a j-facet of S if there are exactly j points from S on the positive side of its affine hull. We show: (*) {\em For j ≤ n/2 - 2 , the total number of (≤ j) -facets (i.e. the number of i -facets with 0 ≤ i ≤ j ) in 3-space is maximized in convex position (where these numbers are known).} A large part of this presentation is a preparatory review of some basic properties of the collection of j -facets—some with their proofs—and of relations to well-established concepts and results from the theory of convex polytopes (h -vector, Dehn—Sommerville relations, Upper Bound Theorem, Generalized Lower Bound Theorem). The relations are established via a duality closely related to the Gale transform—similar to previous works by Lee, by Clarkson, and by Mulmuley. A central definition is as follows. Given a directed line ℓ and a j -facet F of S , we say that {\it ℓ enters F } if ℓ intersects the relative interior of F in a single point, and if ℓ is directed from the positive to the negative side of F . One of the results reviewed is a tight upper bound of j+d-1 \choose d-1 on the maximum number of j -facets entered by a directed line. Based on these considerations, we also introduce a vector for a point relative to a point set, which—intuitively speaking—expresses ``how interior' the point is relative to the point set. This concept allows us to show that statement (*) above is equivalent to the Generalized Lower Bound Theorem for d -polytopes with at most d+4 vertices. Received May 21, 1999, and in revised form July 6, 2000. Online publication January 17, 2001.     

Sommets et normales concourantes des courbes convexes de largeur constante et singularités des hérissons

LetC be a convex curve of constant width and of classC ₄ ⁺ . It is known thatC has at least 6 vertices and its interior contains either a point through which infinitely many normals pass or an open set of points through each of which pass at least 6 normals. If all its vertices are nondegenerate, then: (i)C has exactly 6 vertices if, and only if, its evolute is the boundary of a topological disc through each interior point of which pass at least 6 normals; (ii) ifC has more than 6 vertices, then there exists an open set of points through each of which pass at least 10 normals. The proof: (i) expresses the number of normals passing through a point as a function of the index with respect to the evolute; (ii) relates this index to the number of singularities of the evolute (i.e. of vertices). Furthermore, we give formulas for counting singularities of generic hedgehogs in ℝ² and ℝ³.

     

Minimal Simplicial Dissections and Triangulations of Convex 3-Polytopes

This paper addresses three questions related to minimal triangulations of a three-dimensional convex polytope P . • Can the minimal number of tetrahedra in a triangulation be decreased if one allows the use of interior points of P as vertices? • Can a dissection of P use fewer tetrahedra than a triangulation? • Does the size of a minimal triangulation depend on the geometric realization of P ? The main result of this paper is that all these questions have an affirmative answer. Even stronger, the gaps of size produced by allowing interior vertices or by using dissections may be linear in the number of points. Received August 16, 1999, and in revised form February 29, 2000. Online publication May 19, 2000.     

Asymmetry of Convex Polytopes and Vertex Index of Symmetric Convex Bodies

In (Gluskin, Litvak in Geom. Dedicate 90:45–48, [2002]) it was shown that a polytope with few vertices is far from being symmetric in the Banach–Mazur distance. More precisely, it was shown that Banach–Mazur distance between such a polytope and any symmetric convex body is large. In this note we introduce a new, averaging-type parameter to measure the asymmetry of polytopes. It turns out that, surprisingly, this new parameter is still very large, in fact it satisfies the same lower bound as the Banach–Mazur distance. In a sense it shows the following phenomenon: if a convex polytope with small number of vertices is as close to a symmetric body as it can be, then most of its vertices are as bad as the worst one. We apply our results to provide a lower estimate on the vertex index of a symmetric convex body, which was recently introduced in (Bezdek, Litvak in Adv. Math. 215:626–641, [2007]). Furthermore, we give the affirmative answer to a conjecture by Bezdek (Period. Math. Hung. 53:59–69, [2006]) on the quantitative illumination problem.     

On the Potential Theory of One-dimensional Subordinate Brownian Motions with Continuous Components

Suppose that S is a subordinator with a nonzero drift and W is an independent 1-dimensional Brownian motion. We study the subordinate Brownian motion X defined by X _t  = W(S _t ). We give sharp bounds for the Green function of the process X killed upon exiting a bounded open interval and prove a boundary Harnack principle. In the case when S is a stable subordinator with a positive drift, we prove sharp bounds for the Green function of X in (0, ∞ ), and sharp bounds for the Poisson kernel of X in a bounded open interval.     

An Upper Bound for the Poisson Kernel on Higher Rank <Emphasis Type="Italic">NA</Emphasis> Groups

Let S be a semi direct product S=N\rtimes AS=N\rtimes A where N is a connected and simply connected nilpotent Lie group and A is isomorphic with ℝ ^k , k > 1. We obtain an upper bound for the Poisson kernel for the class of second order left-invariant differential operators on S.     

Inequality of Nordhaus-Gaddum type for total outer-connected domination in graphs

A set S of vertices in a graph G = (V, E) without isolated vertices is a total outer-connected dominating set (TCDS) of G if S is a total dominating set of G and G[V − S] is connected. The total outer-connected domination number of G, denoted by γ _tc (G), is the minimum cardinality of a TCDS of G. For an arbitrary graph without isolated vertices, we obtain the upper and lower bounds on γ _tc (G) + γ _tc ($ \bar G $ \bar G ), and characterize the extremal graphs achieving these bounds.     

On the number of vertices and edges of the Buneman graph

In 1971, Peter Buneman proposed a way to construct a tree from a collection of pairwise compatible splits. This construction immediately generalizes to arbitrary collections of splits, and yields a connected median graph, called the Buneman graph. In this paper, we prove that the vertices and the edges of this graph can be described in a very simple way: given a collection of splitsS, the vertices of the Buneman graph correspond precisely to the subsetsS′ ofS such that the splits inS′ are pairwise incompatible and the edges correspond to pairs (S′, S) withS′ as above andS∈S′. Using this characterization, it is much more straightforward to construct the vertices of the Buneman graph than using prior constructions. We also recover as an immediate consequence of this enumeration that the Buneman graph is a tree, that is, that the number of vertices exceeds the number of edges (by one), if and only if any two distinct splits inS are compatible.     

Poisson structures on Hilbert schemes of points¶of a surface and integrable systems

In this paper we prove that if S is a Poisson surface, i.e., a smooth algebraic surface with a Poisson structure, the Hilbert scheme of points of S has a natural Poisson structure, induced by the one of S. This generalizes previous results obtained by A. Beauville [B1] and S. Mukai [M2] in the symplectic case, i.e., when S is an abelian or K3 surface. Finally we apply our results to give some examples of integrable Hamiltonian systems naturally defined on these Hilbert schemes. In the simple case S=ℙ² we obtain by this construction a large class of integrable systems, which includes the ones studied by P. Vanhaecke in [V1] and, more generally, in [V2]. Received: 9 March 1998 / Revised version: 19 June 1998     

A general non-convex large deviation result with applications to stochastic equations

We prove an abstract large deviation result for a sequence of random elements of a vector space satisfying an “abstract exponential martingale condition”. The framework naturally generates non-convex rate functions. We apply the result to solutions of It? stochastic equations in R ^d driven by Brownian motion and a Poisson random measure. Received: 23 June 1999 / Revised version: 17 February 2000 / Published online: 22 November 2000     

Spanning trees with many leaves

Let a maximal chain of vertices of degree 2 in a graph G consist of k > 0 vertices. We prove that G has a spanning tree with more than \fracv(G)2k + 4 \frac{{v(G)}}{{2k + 4}} leaves (where υ(G) is the number of vertices of the graph G). We present an infinite series of examples showing that the constant \frac12k + 4 \frac{1}{{2k + 4}} cannot be enlarged. Bibliography: 7 titles.     

A criterion of density for solutions of Poisson-driven SDEs

We construct a Dirichlet structure related to a Poisson measure on ℝ⁺×M, where M is a general measured space, with compensator dt⊗dv. We obtain a criterion of density for variables in the domain of the Dirichlet form and we apply it to S.D.E. driven by this Poisson measure. Received: 15 May 1999 / Revised version: 23 February 2000 / Published online: 12 October 2000