On the family of linear extensions of a partial order

Given a partial order P defined on a finite set X, a binary relation ?_P may be defined on X by setting 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 partial orders P such that ?_P includes cycles. Thus, in a voting situation in which voters are unanimous in their preferences on the pairs in P and express all possible linearly ordered preferences on X which are consistent with P, with no two voters having the same preference order, strict simple majorities as given by ?_P can cycle.     

Minimizing bumps for posets of width two

Let L={x₁<…< x_n} be a linear extension of a finite partially ordered set P. A pair (x_i, x_i+1) forms a bump in L whenever x_i< x_i+1 in P. We give an effective solution for the problem of finding a linear extension with a minimum number of bumps when the width ofP is two.     

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.     

A comparison of algorithms for minimizing bumps in linear extensions of partial orders

The notion of bumps deals with a property of linear extensions of a partial order. Let P define a partial order on a set X and let L define a linear extension of P. A bump occurs whenever elements x and y in X are adjacent in both P and L. Heuristics have been developed to construct linear extensions of a partial order that should tend to minimize bumps. This paper presents results of a computer simulation study that compares the performance of bump minimizing algorithms.     

On the 1/3–2/3 Conjecture

Let (P, ≤) be a finite poset (partially ordered set), where P has cardinality n. Consider linear extensions of P as permutations x₁x₂?x_n in one-line notation. For distinct elements x, y ∈ P, we define ?(x ? y) to be the proportion of linear extensions of P in which x comes before y. For \(0\leq \alpha \leq \frac {1}{2}\), we say (x, y) is an α-balanced pair if α ≤ ?(x ? y) ≤?1 ? α. The 1/3–2/3 Conjecture states that every finite partially ordered set which is not a chain has a 1/3-balanced pair. We make progress on this conjecture by showing that it holds for certain families of posets. These include lattices such as the Boolean, set partition, and subspace lattices; partial orders that arise from a Young diagram; and some partial orders of dimension 2. We also consider various posets which satisfy the stronger condition of having a 1/2-balanced pair. For example, this happens when the poset has an automorphism with a cycle of length 2. Various questions for future research are posed.     

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].     

The total linear discrepancy of an ordered set

In this paper we introduce the notion of the total linear discrepancy of a poset as a way of measuring the fairness of linear extensions. If L is a linear extension of a poset P, and x,y is an incomparable pair in P, the height difference between x and y in L is |L(x)−L(y)|. The total linear discrepancy of P in L is the sum over all incomparable pairs of these height differences. The total linear discrepancy of P is the minimum of this sum taken over all linear extensions L of P. While the problem of computing the (ordinary) linear discrepancy of a poset is NP-complete, the total linear discrepancy can be computed in polynomial time. Indeed, in this paper, we characterize those linear extensions that are optimal for total linear discrepancy. The characterization provides an easy way to count the number of optimal linear extensions.     

Orientation-reversing actions on lens spaces and Gaussian integers

A finite group action on a lens space L(p,q) has ‘type OR’ if it reverses orientation and has an invariant Heegaard torus whose sides are interchanged by the orientation-reversing elements. In this paper we enumerate the actions of type OR up to equivalence. This leads to a complete classification of geometric finite group actions on amphicheiral lens spaces L(p,q) with p>2. The family of actions of type OR is partially ordered by lifting actions via covering maps. We show that each connected component of this poset may be described in terms of a subset of the lattice of Gaussian integers ordered by divisibility. This results in a correspondence equating equivalence classes of actions of type OR with pairs of Gaussian integers.     

Linear Discrepancy and Weak Discrepancy of Partially Ordered Sets

The linear discrepancy of a partially ordered set P=(X,) is the least integer k for which there exists an injection f: XZ satisfying (i) if xy then f(x)<f(y) and (ii) if xy then |f(x)–f(y)|k. This concept is closely related to the weak discrepancy of P studied previously. We prove a number of properties of linear and weak discrepancies and relate them to other poset parameters. Both parameters have applications in ranking the elements of a partially ordered set so that the difference in rank of incomparable elements is minimized.     

Constructions for overlarge sets of disjoint pure directed triple systems

Let X be a v-set, v≥3. A transitive triple (x,y,z) on X is a set of three ordered pairs (x,y),(y,z) and (x,z) of X. A directed triple system of order v, denoted by DTS(v), is a pair (X,?), where X is a v-set and ? is a collection of transitive triples on X such that every ordered pair of X belongs to exactly one triple of ?. A DTS(v) is called pure and denoted by PDTS(v) if (x,y,z)∈? implies (z,y,x)??. An overlarge set of disjoint PDTS(v) is denoted by OLPDTS(v). In this paper, we establish some recursive constructions for OLPDTS(v), so we obtain some results.     

On First Range Times of Linear Diffusions

In this paper we consider first range times (with randomised range level) of a linear diffusion on R. Inspired by the observation that the exponentially randomised range time has the same law as a similarly randomised first exit time from an interval, we study a large family of non-negative 2-dimensional random variables (X,X′) with this property. The defining feature of the family is F^c(x,y)=F^c(x+y,0), ∀ x ≥ 0, y ≥ 0, where F^c(x,y):=P (X > x, X′ > y) We also explain the Markovian structure of the Brownian local time process when stopped at an exponentially randomised first range time. It is seen that squared Bessel processes with drift are serving hereby as a Markovian element.     

Domination by second countable spaces and Lindelöf Σ-property

Given a space M, a family of sets A of a space X is ordered by M if A={AK:K is a compact subset of M} and K⊂L implies AK⊂AL. We study the class M of spaces which have compact covers ordered by a second countable space. We prove that a space Cp(X) belongs to M if and only if it is a Lindelöf Σ-space. Under MA(ω₁), if X is compact and (X×X)\Δ has a compact cover ordered by a Polish space then X is metrizable; here Δ={(x,x):x∈X} is the diagonal of the space X. Besides, if X is a compact space of countable tightness and X²\Δ belongs to M then X is metrizable in ZFC.We also consider the class M^? of spaces X which have a compact cover F ordered by a second countable space with the additional property that, for every compact set P⊂X there exists F∈F with P⊂F. It is a ZFC result that if X is a compact space and (X×X)\Δ belongs to M^? then X is metrizable. We also establish that, under CH, if X is compact and Cp(X) belongs to M^? then X is countable.     

Bipartite Q-polynomial distance-regular graphs and uniform posets

Let Γ denote a bipartite distance-regular graph with vertex set X and diameter D≥3. Fix x∈X and let L (resp., R) denote the corresponding lowering (resp., raising) matrix. We show that each Q-polynomial structure for Γ yields a certain linear dependency among RL ², LRL, L ² R, L. Define a partial order ≤ on X as follows. For y,z∈X let y≤z whenever ?(x,y)+?(y,z)=?(x,z), where ? denotes path-length distance. We determine whether the above linear dependency gives this poset a uniform or strongly uniform structure. We show that except for one special case a uniform structure is attained, and except for three special cases a strongly uniform structure is attained.     

On the Rédei zeta function

Let L be a locally finite lattice. An order function ν on L is a function defined on pairs of elements x, y (with x ≤ y) in L such that ν(x, y) = ν(x, z) ν(z, y). The Rédei zeta function of L is given by ?(s; L) = Σ_x∈Lμ(Ô, x) ν(Ô, x)^?s. It generalizes the following functions: the chromatic polynomial of a graph, the characteristic polynomial of a lattice, the inverse of the Dedekind zeta function of a number field, the inverse of the Weil zeta function for a variety over a finite field, Philip Hall's φ-function for a group and Rédei's zeta function for an abelian group. Moreover, the paradigmatic problem in all these areas can be stated in terms of the location of the zeroes of the Rédei zeta function.     

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.     

Weighted norm inequalities, Gaussian bounds and sharp spectral multipliers

Let L be a non-negative self-adjoint operator acting on L²(X) where X is a space of homogeneous type. Assume that L generates a holomorphic semigroup e−tL whose kernels pt(x,y) have Gaussian upper bounds but there is no assumption on the regularity in variables x and y. In this article, we study weighted Lp-norm inequalities for spectral multipliers of L. We show that sharp weighted Hörmander-type spectral multiplier theorems follow from Gaussian heat kernel bounds and appropriate L² estimates of the kernels of the spectral multipliers. These results are applicable to spectral multipliers for large classes of operators including Laplace operators acting on Lie groups of polynomial growth or irregular non-doubling domains of Euclidean spaces, elliptic operators on compact manifolds and Schrödinger operators with non-negative potentials.     

Modular metric spaces, I: Basic concepts

The notion of a modular is introduced as follows. A (metric) modular on a set X is a function w:(0,∞)×X×X→[0,∞] satisfying, for all x,y,z∈X, the following three properties: x=y if and only if w(λ,x,y)=0 for all λ>0; w(λ,x,y)=w(λ,y,x) for all λ>0; w(λ+μ,x,y)≤w(λ,x,z)+w(μ,y,z) for all λ,μ>0. We show that, given x₀∈X, the set X_w={x∈X:lim_λ→∞w(λ,x,x₀)=0} is a metric space with metric , called a modular space. The modular w is said to be convex if (λ,x,y)?λw(λ,x,y) is also a modular on X. In this case X_w coincides with the set of all x∈X such that w(λ,x,x₀)<∞ for some λ=λ(x)>0 and is metrizable by . Moreover, if or , then ; otherwise, the reverse inequalities hold. We develop the theory of metric spaces, generated by modulars, and extend the results by H. Nakano, J. Musielak, W. Orlicz, Ph. Turpin and others for modulars on linear spaces.     

Irreducible Width 2 Posets of Linear Discrepancy 3

The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h _L (x) − h _L (y)| ≤ k, where h _L (x) is the height of x in L. Tannenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the problem for characterizing the posets of linear discrepancy 2. Howard et al. (Order 24:139–153, 2007) showed that this problem is equivalent to finding all posets of linear discrepancy 3 such that the removal of any point reduces the linear discrepancy. In this paper we determine all of these minimal posets of linear discrepancy 3 that have width 2. We do so by showing that, when removing a specific maximal point in a minimal linear discrepancy 3 poset, there is a unique linear extension that witnesses linear discrepancy 2. The first author was supported during this research by National Science foundation VIGRE grant DMS-0135290.     

Littlewood–Paley and Spectral Multipliers on Weighted L p Spaces

Let L be a non-negative self-adjoint operator acting on L ²(X), where X is a space of homogeneous type. Assume that L generates a holomorphic semigroup e ^?tL whose kernel p _t (x,y) has a Gaussian upper bound but there is no assumption on the regularity in variables x and y. In this article we study weighted L ^p -norm inequalities for spectral multipliers of L. We show that a weighted Hörmander-type spectral multiplier theorem follows from weighted L ^p -norm inequalities for the Lusin and Littlewood–Paley functions, Gaussian heat kernel bounds, and appropriate L ² estimates of the kernels of the spectral multipliers.