Densely two-valued metric projections in uniformly convex Banach spaces

For every uniformly convex Banach spaceX with dimX2 there is a residual setU in the Hausdorff metric spaceB(X) of bounded and closed sets inX such that the metric projection generated by a set fromU is two-valued and upper semicontinuous on a dense and everywhere continual subset ofX. For any two closed and separated subsetsM ₁ andM ₂ ofX the points on the equidistant hypersurface which have best approximations both inM ₁ andM ₂ form a dense G set in the induced topology.The author is partially supported by the National Fund for Scientific Research at the Bulgarian Ministry of Science and Education under contract MM 408/94.     

Cross-cuts in the power set of an infinite set

In the power setP(E) of a setE, the sets of a fixed finite cardinalityk form across-cut, that is, a maximal unordered setC such that ifX, Y E satisfyXY, X someX inC, andY someY inC, thenXZY for someZ inC. ForE=, ₁, and ₂, it is shown with the aid of the continuum hypothesis thatP(E) has cross-cuts consisting of infinite sets with infinite complements, and somewhat stronger results are proved for and ₁.The work reported here has been partially supported by NSERC Grant No. A8054.     

Ambiguous loci of the metric projection onto compact starshaped sets in a Banach space

LetE be a real Banach space andL(E) the family of all nonempty compact starshaped subsets ofE. Under the Hausdorff distance,L(E) is a complete metric space. The elements of the complement of a first Baire category subset ofL(E) are called typical elements ofL(E). ForXL(E) we denote by the metrical projection ontoX, i.e. the mapping which associates to eachaE the set of all points inX closest toa. In this note we prove that, ifE is strictly convex and separable with dimE2, then for a typicalXL(E) the map is not single valued at a dense set of points. Moreover, we show that a typical element ofL(E) has kernel consisting of one point and set of directions dense in the unit sphere ofE.     

On the connectedness of the set of weakly efficient points of a vector optimization problem in locally convex spaces

In vector optimization, topological properties of the set of efficient and weakly efficient points are of interest. In this paper, we study the connectedness of the setE ^w of all weakly efficient points of a subsetZ of a locally convex spaceX with respect to a continuous mappingp:X Y,Y locally convex and partially ordered by a closed, convex cone with nonempty interior. Under the general assumptions thatZ is convex and closed and thatp is a pointwise quasiconvex mapping (i.e., a generalized quasiconvex concept), the setE ^w is connected, if the lower level sets ofp are compact. Furthermore, we show some connectedness results on the efficient points and the efficient and weakly efficient outcomes. The considerations of this paper extend the previous results of Refs. 1–3. Moreover, some examples in vector approximation are given.The author is grateful to Dr. D. T. Luc and to a referee for pointing out an error in an earlier version of this paper.     

The Arrow-Barankin-Blackwell theorem in a dual space setting

In 1953 Arrow, Barankin, and Blackwell proved that, ifR ⁿ is equipped with its natural ordering and ifF is a closed convex subset ofR ⁿ , then the set of points inF that can be supported by strictly positive linear functionals is dense in the set of all efficient (maximal) points ofF. Many generalizations of this density result to infinite-dimensional settings have been given. In this note, we consider the particular setting where the setF is contained in the topological dualY ^* of a partially ordered, nonreflexive normed spaceY, and the support functionals are restricted to be either nonnegative or strictly positive elements in the canonical embedding ofY inY ^*. Three alternative density results are obtained, two of which generalize a space-specific result due to Majumdar for the dual system (Y,Y ^*)=(L ¹,L ).This research was supported in part by funds provided by the Provident Chair of Excellence in Applied Mathematics at the University of Tennessee, Chattanooga, Tennessee.     

Independent collections of translates of boxes and a conjecture due to Grünbaum

A collection ofn setsA ₁, ...,A _n is said to beindependent provided every set of the formX ₁ ... X _n is nonempty, where eachX _i is eitherA _i orA _i ^c . We give a simple characterization for when translates of a given box form an independent set inR ^d. We use this to show that the largest number of such boxes forming an independent set inR ^d is given by 3d/2 ford2. This settles in the negative a conjecture of Grünbaum (1975), which states that the maximum size of an independent collection of sets homothetic to a fixed convex setC inR ^d isd+1. It also shows that the bound of 2d of Rényiet al. (1951) for the maximum number of boxes (not necessarily translates of a given one) with sides parallel to the coordinate axes in an independent collection inR ^d can be improved for these special collections.Daniel Q. Naiman was supported by National Science Foundation Grant No. DMS-9103126. Henry P. Wynn was supported by the Science and Engineering Research Council, UK.     

On the martingale problem for Banach space valued stochastic differential equations

LetE denote a real separable Banach space and letZ=(Z(t, f) be a family of centered, homogeneous, Gaussian independent increment processes with values inE, indexed by timet0 and the continuous functionsf:[0,t] E. If the dependence ont andf fulfills some additional properties,Z is called a gaussian random field. For continuous, adaptedE-valued processesX a stochastic integral processY = ₀ ^. Z(t, X)(dt) is defined, which is a continuous local martingale with tensor quadratic variation[Y] = ₀ ^. Q(t, X)dt, whereQ(t, f) denotes the covariance operator ofZ(t, f).Y is called a solution of the homogeneous Gaussian martingale problem, ifY = ₀ ^. Z(t, Y)(dt). Such solutions occur naturally in connection with stochastic differential equations of the type (D):dX(t)=G(t, X) dt+Z(t, X)(dt), whereG is anE-valued vector field. It is shown that a solution of (D) can be obtained by a kind of variation of parameter method, first solving a deterministic integral equation only involvingG and then solving an associated homogeneous martingale problem.     

Divergence rates for the number of rare numbers

Suppose thatX ₁,X ₂, ... is a sequence of i.i.d. random variables taking value inZ ⁺. Consider the random sequenceA(X)(X ₁,X ₂,...). LetY _n be the number of integers which appear exactly once in the firstn terms ofA(X). We investigate the limit behavior ofY _n /E[Y _n ] and establish conditions under which we have almost sure convergence to 1. We also find conditions under which we dtermine the rate of growth ofE[Y _n ]. These results extend earlier work by the author.     

A combinatorial property of points and ellipsoids

For eachd1 there is a constantc _d>0 such that any finite setXR ^d contains a subsetYX, |Y|[1/4d(d+3)]+1 having the following property: ifEY is an ellipsoid, then |E X|c _d |X|.On leave from the Mathematical Institute of the Hungarian Academy of Sciences, 1364 Budapest, P.O. Box 127, Hungary. Supported by a research fellowship from the Science and Engineering Research Council, U.K., and by Hungarian National Foundation for Scientific Research Grant No. 1812.     

On the maximum 2-1 matching

Given a simple bipartite graphG=(X,Y, E).M E is called a 2-1 matching ofG if: 1) _x X, either two edges or none inM is incident tox and 2) _y Y, at most one edge inM is incident toy. In this paper, we describe an efficient algorithm for finding a maximum 2-1 matching in a given bipartite graph. We also formulate and prove a duality theorem for 2-1 matching.     

Building ofGL(m, D) and centralizers

LetG=GL(m, D) whereD is a central division algebra over a commutative nonarchimedean local fieldF. LetE/F be a field extension contained inM(m, D). We denote byI (resp.I _E) the nonextended affine building ofG (resp. of the centralizer ofE ^x inG). In this paper we prove that there exists a uniqueG _E-equivariant affine mapj _EI_EI. It is injective and its image coincides with the set ofE ^x-fixed points inI. Moreover, we prove thatj _E is compatible with the Moy-Prasad filtrations.This author's contribution was written while he was a post-doctoral student at King's College London and supported by an european TMR grant     

A characterization of brownian motion in a lipschitz domain by its killing distributions

Let (Y _t, Q^x) be a strong Markov process in a bounded Lipschitz domainD with continuous paths up to its lifetime , and let (X _t, P^x) be a Brownian motion inD. IfY _– exists in D andQ ^x(Y_– C)=P^x(X_– C) for all Borel subsetsC of D and allx, thenY is a time change ofX.     

Some sets obeying harmonic synthesis

LetX be a (not necessarily closed) subspace of the dual spaceB ^* of a separable Banach spaceB. LetX ₁ denote the set of all weak ^* limits of sequences inX. DefineX _a , for every ordinal numbera, by the inductive rule:X _a = (U _{b < a} X _b ) ₁ .There is always a countable ordinala such thatX _a is the weak ^* closure ofX; the first sucha is called theorder ofX inB ^* . LetE be a closed subset of a locally compact abelian group. LetPM(E) be the set of pseudomeasures, andM(E) the set of measures, whose supports are contained inE. The setE obeys synthesis if and only ifM(E) is weak ^* dense inPM(E). Varopoulos constructed an example in which the order ofM(E) is 2. The authors construct, for every countable ordinala, a setE inR that obeys synthesis, and such that the order ofM(E) inPM(E) isa. This work was done in Jerusalem, when the second-named author was a visitor at the Institute of Mathematics of the Hebrew University of Jerusalem, with the support of an NSF International Travel Grant and of NSF Grant GP33583.     

Rare numbers

Suppose thatX ₁,X ₂,... is a sequence of iid random variables taking values inZ ⁺. Consider the random sequenceA(X)(X ₁,X ₂,...). LetY _n be the number of integers which appear exactly once in the firstn terms ofA(X). We investigate the limit behavior ofn ^–(1–) Y _n for [0, 1].     

A characterization ofh-Brownian motion by its exit distributions

Summary LetX ^h be anh-Brownian motion in the unit ballDR ^d withh harmonic, such that the representing measure ofh is not singular with respect to the surface measure on D. IfY is a continuous strong Markov process inD with the same killing distributions asX ^h , thenY is a time change ofX ^h . Similar results hold in simply connected domains inC provided with either the Martin or the Euclidean boundary.     

Matroid intersection algorithms

LetM ₁ = (E, 9₁),M ₂ = (E, 9₂) be two matroids over the same set of elementsE, and with families of independent sets 9₁, 9₂. A setI 9₁ 9₂ is said to be anintersection of the matroidsM ₁,M ₂. An important problem of combinatorial optimization is that of finding an optimal intersection ofM ₁,M ₂. In this paper three matroid intersection algorithms are presented. One algorithm computes an intersection containing a maximum number of elements. The other two algorithms compute intersections which are of maximum total weight, for a given weighting of the elements inE. One of these algorithms is primal-dual, being based on duality considerations of linear programming, and the other is primal. All three algorithms are based on the computation of an augmenting sequence of elements, a generalization of the notion of an augmenting path from network flow theory and matching theory. The running time of each algorithm is polynomial inm, the number of elements inE, and in the running times of subroutines for independence testing inM ₁,M ₂. The algorithms provide constructive proofs of various important theorems of matroid theory, such as the Matroid Intersection Duality Theorem and Edmonds' Matroid Polyhedral Intersection Theorem.Research sponsored by the Air Force Office of Scientific Research Grant 71-2076.     

Some properties of graph centroids

The concept of a branch weight centroid has been extended in [12] so that it can be defined for an arbitrary finite setX with a distinguished familyC of "convex" subsets ofX. In particular, the centroid of a graphG was defined forX to be the vertex setV(G) ofG andU V(G) is convex if it is the vertex set of a chordless path inG. In this paper, which is an extended version of [13], we give necessary and sufficient conditions for a graph to be a centroid of another graph as well as of itself. Then, we apply these results to some particular classes of graphs: chordal, Halin, series-parallel and outerplanar.This research has been partly supported by Grant RP.I.09 from the Institute of Computer Science, University of Warsaw. This paper was completed when the second author was at Fachbereich 3 -Mathematik, Technische Universität Berlin, supported also by the Alexander von Humboldt-Stiftung (Bonn).     

Preparation of papers

LetF be a family of real-valued maps onR ⁿ, and letY be a subset ofR ⁿ. Denote byS(Y|F) the set of ally* Y such that, for somef F,f(y)f(y*) for ally inY. Let us say thatF is a scalarization family if, for any subsetY,S(Y|F) is equal to the set of properly efficient points inY. General conditions forF to be a scalarization family were given in Ref. 1. However, scalarization families must contain nondifferentiable functions. In this note, it is shown that, if the condition of Ref. 1 which forces nondifferentiability is dropped, thenS(Y|F) is dense in the set of properly efficient points.