The Ptolemy and Zb?ganu constants of normed spaces

In every inner product space H the Ptolemy inequality holds: the product of the diagonals of a quadrilateral is less than or equal to the sum of the products of the opposite sides. In other words, ‖x−y‖‖z−w‖≤‖x−z‖‖y−w‖+‖z−y‖‖x−w‖ for any points w,x,y,z in H. It is known that for each normed space (X,‖⋅‖), there exists a constant C such that for any w,x,y,z∈X, we have ‖x−y‖‖z−w‖≤C(‖x−z‖‖y−w‖+‖z−y‖‖x−w‖). The smallest such C is called the Ptolemy constant of X and is denoted by C_P(X). We study the relationships between this constant and the geometry of the space X, and hence with metric fixed point theory. In particular, we relate the Ptolemy constant C_P to the Zb?ganu constant C_Z, and prove that if X is a Banach space with , then X has (uniform) normal structure and therefore the fixed point property for nonexpansive mappings. We derive general lower and upper bounds for both C_P and C_Z, and calculate the precise values of these two constants for several normed spaces. We also present a number of conjectures and open problems.     

Submaximal and door compactifications

In this paper, a characterization is given for compact door spaces. We, also, deal with spaces X such that a compactification K(X) of X is submaximal or door.Let X be a topological space and K(X) be a compactification of X.We prove, here, that K(X) is submaximal if and only if for each dense subset D of X, the following properties hold:

(i)

D is co-finite in K(X);

(ii)

for each x∈K(X)?D, {x} is closed.

If X is a noncompact space, then we show that K(X) is a door space if and only if X is a discrete space and K(X) is the one-point compactification of X.     

Expansive homeomorphisms and plane separating continua

A homeomorphism is expansive provided that there exists a constant c>0 and for every x,y∈X there exists an integer n, dependent only on x and y, such that d(hn(x),hn(y))>c. It is shown that if X is a 1-dimensional continuum that separates the plane into 2 pieces, then h cannot be expansive.     

A pair of spaces of upper semi-continuous maps and continuous maps

For a Tychonoff space X, we use ↓USC(X) and ↓C(X) to denote the families of the regions below all upper semi-continuous maps and of the regions below all continuous maps from X to I=[0,1], respectively. In this paper, we consider the spaces ↓USC(X) and ↓C(X) topologized as subspaces of the hyperspace Cld(X×I) consisting of all non-empty closed sets in X×I endowed with the Vietoris topology. We shall prove that ↓USC(X) is homeomorphic (≈) to the Hilbert cube Q=ω[−1,1] if and only if X is an infinite compact metric space. And we shall prove that (↓USC(X),↓C(X))≈(Q,c₀), where , if and only if ↓C(X)≈c₀ if and only if X is a compact metric space and the set of isolated points is not dense in X.     

A duality relation for entrance and exit laws for Markov processes

Markov processes X_t on (X, F_X) and Y_t on (Y, F_Y) are said to be dual with respect to the function f(x, y) if E_xf(X_t, y) = E_yf(x, Y_t for all x ? X, y ? Y, t ? 0. It is shown that this duality reverses the role of entrance and exit laws for the processes, and that two previously published results of the authors are dual in precisely this sense. The duality relation for the function f(x, y) = 1_{x<y} is established for one-dimensional diffusions, and several new results on entrance and exit laws for diffusions, birth-death processes, and discrete time birth-death chains are obtained.     

Semiorders and the 1/3–2/3 conjecture

A well-known conjecture of Fredman is that, for every finite partially ordered set (X, <) which is not a chain, there is a pair of elements x, y such that P(x, the proportion of linear extensions of (X, <) with x below y, lies between 1/3 and 2/3. In this paper, we prove the conjecture in the special case when (X, <) is a semiorder. A property we call 2-separation appears to be crucial, and we classify all locally finite 2-separated posets of bounded width.     

The t-median function on graphs

A median of a sequence π=x₁,x₂,…,x_k of elements of a finite metric space (X,d) is an element x for which is minimum. The function M with domain the set of all finite sequences on X and defined by M(π)={x:x is a median of π} is called the median function on X, and is one of the most studied consensus functions. Based on previous characterizations of median sets M(π), a generalization of the median function is introduced and studied on various graphs and ordered sets. In addition, new results are presented for median graphs.     

Generic uniqueness of equilibrium points

Let X be a nonempty, convex and compact subset of normed linear space E (respectively, let X be a nonempty, bounded, closed and convex subset of Banach space E and A be a nonempty, convex and compact subset of X) and f:X×X→R be a given function, the uniqueness of equilibrium point for equilibrium problem which is to find x^∗∈X (respectively, x^∗∈A) such that f(x^∗,y)≥0 for all y∈X (respectively, f(x^∗,y)≥0 for all y∈A) is studied with varying f (respectively, with both varying f and varying A). The results show that most of equilibrium problems (in the sense of Baire category) have unique equilibrium point.     

Coupled fixed point theorems for a generalized Meir-Keeler contraction in partially ordered metric spaces

Let X be a non-empty set and F:X×X→X be a given mapping. An element (x,y)∈X×X is said to be a coupled fixed point of the mapping F if F(x,y)=x and F(y,x)=y. In this paper, we consider the case when X is a complete metric space endowed with a partial order. We define generalized Meir-Keeler type functions and we prove some coupled fixed point theorems under a generalized Meir-Keeler contractive condition. Some applications of our obtained results are given. The presented theorems extend and complement the recent fixed point theorems due to Bhaskar and Lakshmikantham [T. Gnana Bhaskar, V. Lakshmikantham, Fixed point theorems in partially ordered metric spaces and applications, Nonlinear Anal. 65 (2006) 1379-1393].     

Linear extension majority cycles in height-1 orders

For points x and y in a poset (X, >) let x> _p y mean that more linear extensions of the poset have x above y than y above x. It has been known for some time that > _p can have cycles when the height of the poset is two or more. Moreover, the smallest posets with a > _p cycle have nine points and heights of 2, 3 and 4. We show here that height-1 posets can also have > _p cycles. Our smallest example for this phenomenon has 15 points.Research supported through a fellowship from the Center for Advanced Study of the University of Delaware.     

On an internal property of absolute retracts,II

Let X be a (metrizable) space. A mixer for X is, roughly speaking, a map μ:X³→X such that μ(x, x, y) = μ(x, y, x) = μ(y, x, x) = x for all x, y ∈ X. We show that each AR has a mixer and that a finite dimensional path connected space with a mixer is an AR. Our main result is that each separable space with a mixer and having an open cover by sets contractible within the whole space, is LEC.     

Universal correlations in finite posets

Posets A, BX×X, with X finite, are said to be universally correlated (AB) if, for all posets R over X, (i.e., all posets RY×Y with XY), we have P(RA) P(RB)P(RAB) P(R). Here P(RA), for instance, is the probability that a randomly chosen bijection from Y to the totally ordered set with |Y| elements is a linear extension of RA. We show that AB iff, for all posets R over X, P(RA) P(RB)P(RAB) P(R(AB)).Winkler proved a theorem giving a necessary and sufficient condition for AB. We suggest an alteration to his proof, and give another condition equivalent to AB.Daykin defined the pair (A, B) to be universally negatively correlated (A B) if, for all posets R over X, P(RA) P(RB)P(RAB) P(R(AB)). He suggested a condition for AB. We give a counterexample to that conjecture, and establish the correct condition. We write AB if, for all posets R over X, P(RA) P(RB)P(RAB) P(R). We give a necessary and sufficient condition for AB.We also give constructive techniques for listing all pairs (A, B) satisfying each of the relations AB, AB, and AB.     

On linear extension majority graphs of partial orders

The linear extension majority (LEM) graph (X, > p) of a finite partially ordered set (X, P) has x>py for elements x and y in X just when more linear extensions L of P on X have xLy than yLx. A linear extension L of P on X is a linear order on X with P ? L. There exist finite partially ordered sets (X, P) whose LEM graphs have no >p-maximal elements, in which case every x in X has an x′ in X for which x′>px.     

Postulation of disjoint unions of lines and a few planes

Let X⊂Pⁿ, n≥5, be a general union of x planes and y lines. Here we prove that X has the expected postulation if x is small with respect to y.     

Applications of utility functions defined on quasi-metric spaces

A quasi-metric space (X,d) is called sup-separable if (X,d^s) is a separable metric space, where d^s(x,y)=max{d(x,y),d(y,x)} for all x,y∈X. We characterize those preferences, defined on a sup-separable quasi-metric space, for which there is a semi-Lipschitz utility function. We deduce from our results that several interesting examples of quasi-metric spaces which appear in different fields of theoretical computer science admit semi-Lipschitz utility functions. We also apply our methods to the study of certain kinds of dynamical systems defined on quasi-metric spaces.     

Score vectors of tournaments

A tournament T on any set X is a dyadic relation such that for any x, y ∈ X (a) (x, x) ? T and (b) if x ≠ y then (x, y) ∈ T iff (y, x) ? T. The score vector of T is the cardinal valued function defined by R(x) = |{y ∈ X : (x, y) ∈ T}|. We present theorems for infinite tournaments analogous to Landau's necessary and sufficient conditions that a vector be the score vector for some finite tournament. Included also is a new proof of Landau's theorem based on a simple application of the “marriage” theorem.     

Properties of functions with monotone graphs

A metric space (X,d) is monotone if there is a linear order < on X and a constant c>0 such that d(x,y)≦cd(x,z) for all x<y<z∈X. Properties of continuous functions with monotone graph (considered as a planar set) are investigated. It is shown, for example, that such a function can be almost nowhere differentiable, but must be differentiable at a dense set, and that the Hausdorff dimension of the graph of such a function is 1.     

A note on internally disjoint alternating paths in bipartite graphs

Let G be a balanced bipartite graph with partite sets X and Y, which has a perfect matching, and let x∈X and y∈Y. Let k be a positive integer. Then we prove that if G has k internally disjoint alternating paths between x and y with respect to some perfect matching, then G has k internally disjoint alternating paths between x and y with respect to every perfect matching.     

Principal topologies and transformation semigroups

For a given set X, the set F(X) of all maps from X to X forms a semigroup under composition. A subsemigroup S of F(X) is said to be saturated if for each x∈X there exists a set Ox⊆X with x∈Ox such that . It is shown that there exists a one-to-one correspondence between principal topologies on X and saturated subsemigroups of F(X). Some properties of principal topologies on X and the corresponding properties of their associated saturated subsemigroups of F(X) are discussed.