The fractional weak discrepancy of a partially ordered set

In this paper we introduce the notion of the fractional weak discrepancy of a poset, building on previous work on weak discrepancy in [J.G. Gimbel and A.N. Trenk, On the weakness of an ordered set, SIAM J. Discrete Math. 11 (1998) 655-663; P.J. Tanenbaum, A.N. Trenk, P.C. Fishburn, Linear discrepancy and weak discrepancy of partially ordered sets, ORDER 18 (2001) 201-225; A.N. Trenk, On k-weak orders: recognition and a tolerance result, Discrete Math. 181 (1998) 223-237]. The fractional weak discrepancywd_F(P) of a poset P=(V,?) is the minimum nonnegative k for which there exists a function f:V→R satisfying (1) if a?b then f(a)+1?f(b) and (2) if a∥b then |f(a)-f(b)|?k. We formulate the fractional weak discrepancy problem as a linear program and show how its solution can also be used to calculate the (integral) weak discrepancy. We interpret the dual linear program as a circulation problem in a related directed graph and use this to give a structural characterization of the fractional weak discrepancy of a poset.     

Fractional weak discrepancy and split semiorders

The fractional weak discrepancywd_F(P) of a poset P=(V,?) was introduced in Shuchat et al. (2007) [6] as the minimum nonnegative k for which there exists a function f:V→R satisfying (i) if a?b then f(a)+1≤f(b) and (ii) if a∥b then |f(a)−f(b)|≤k. In this paper we generalize results in Shuchat et al. (2006, 2009) [5] and [7] on the range of wd_F for semiorders to the larger class of split semiorders. In particular, we prove that for such posets the range is the set of rationals that can be represented as r/s for which 0≤s−1≤r<2s.     

When linear and weak discrepancy are equal

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, then |h_L(x)−h_L(y)|≤k, whereas the weak discrepancy is the least k such that there is a weak extension W of P such that if x and y are incomparable, then |h_W(x)−h_W(y)|≤k. This paper resolves a question of Tanenbaum, Trenk, and Fishburn on characterizing when the weak and linear discrepancy of a poset are equal. Although it is shown that determining whether a poset has equal weak and linear discrepancy is -complete, this paper provides a complete characterization of the minimal posets with equal weak and linear discrepancy. Further, these minimal posets can be completely described as a family of interval orders.     

Range of the Fractional Weak Discrepancy Function

In this paper we describe the range of values that can be taken by the fractional weak discrepancy of a poset and characterize semiorders in terms of these values. In [6], we defined the fractional weak discrepancy of a poset to be the minimum nonnegative for which there exists a function satisfying (1) if then and (2) if then . This notion builds on previous work on weak discrepancy in [3, 7, 8]. We prove here that the range of values of the function is the set of rational numbers that are either at least one or equal to for some nonnegative integer . Moreover, is a semiorder if and only if , and the range taken over all semiorders is the set of such fractions .The third author's work was supported in part by a Wellesley College Brachman Hoffman Fellowship.     

Stochastic applications of media theory: Random walks on weak orders or partial orders

This paper presents the axioms of a real time random walk on the set of states of a medium and some of their consequences, such as the asymptotic probabilities of the states. The states of the random walk coincide with those of the medium, and the transitions of the random walk are governed by a probability distribution on the set of token-events, together with a Poisson process regulating the arrivals of such events. We examine two special cases. The first is the medium on strict weak orders on a set of three elements, the second the medium of strict partial orders on the same set. Thus, in each of these cases, a state of the medium is a binary relation. We also consider tune in-and-out extensions of these two special cases. We review applications of these models to opinion poll data pertaining to the 1992 United States presidential election. Each strict weak order or strict partial order is interpreted as being the implicit or explicit opinion of some individual regarding the three major candidates in that election, namely, Bush, Clinton and Perot. In particular, the strict partial order applications illustrate our notion of a response function that provides the link between theory and data in situations where, in contrast to previous papers, the permissible responses do not span the entire set of permissible states of the medium.     

Construction of some countable 1-arc-transitive bipartite graphs

We generalize earlier work which gave a method of construction for bipartite graphs which are obtained as the set of maximal or minimal elements of a certain cycle-free partial order. The method is extended here to produce a 1-arc-transitive bipartite graph in a ‘free’ way, starting with any partial order with greatest and least element and with instructions on its points about how they will ramify in the extension. A key feature of our work is the interplay between properties of the initial partial order, the extended partial order, and the bipartite graph which results. We also extend the earlier work by giving a complete characterization of all 2-CS-transitive cycle-free partial orders. In addition, we discuss the completeness of the constructed partial orders, in the sense of Dedekind and MacNeille, and remark that the bipartite graph constructed can only be 2-arc-transitive in the cycle-free case.     

A setup heuristic for interval orders

The setup minimization problem for linear extensions of interval orders is considered and a simple greedy heuristic is shown to be never worse than twice the optimum.     

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.     

Homomorphism-Homogeneous Partially Ordered Sets

A structure is called homogeneous if every isomorphism between finite substructures of the structure extends to an automorphism of the structure. Recently, P. J. Cameron and J. Nešetřil introduced a relaxed version of homogeneity: we say that a structure is homomorphism-homogeneous if every homomorphism between finite substructures of the structure extends to an endomorphism of the structure. In this paper we characterize homomorphism-homogeneous partially ordered sets (where a homomorphism between partially ordered sets A and B is a mapping f : A →B satisfying ). We show that there are five types of homomorphism-homogeneous partially ordered sets: partially ordered sets whose connected components are chains; trees; dual trees; partially ordered sets which split into a tree and a dual tree; and X ₅-dense locally bounded partially ordered sets. Supported by the Ministry od Science and Environmental Protection of the Republic of Serbia, Grant No. 144017.     

NP-hardness results for the aggregation of linear orders into median orders

Given a collection Π of individual preferences defined on a same finite set of candidates, we consider the problem of aggregating them into a collective preference minimizing the number of disagreements with respect to Π and verifying some structural properties. We study the complexity of this problem when the individual preferences belong to any set containing linear orders and when the collective preference must verify different properties, for instance transitivity. We show that the considered aggregation problems are NP-hard for different types of collective preferences (including linear orders, acyclic relations, complete preorders, interval orders, semiorders, quasi-orders or weak orders), if the number of individual preferences is sufficiently large.     

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.     

A Fractional Donsker Theorem

We prove a Donsker-type approximation of the fractional Brownian motion which extends a result by Sottinen for the case H > 1/2 to the full range of Hurst parameters H ∈ (0, 1). The convergence is established by a Donsker-type theorem for Volterra Gaussian processes. The approximation is applied to weak convergence of fractional Wiener integrals.     

On the semilattice of weak orders of a set

Order theoretic and combinatorial properties of the semilattice of weak orders on a set are developed. In the case of a finite set, an order theoretic characterization of this semilattice is obtained.     

Inductive Characterizations of Finite Interval Orders and Semiorders

We introduce an inductive definition for two classes of orders. By simple proofs, we show that one corresponds to the interval orders class and that the other is exactly the semiorders class.     

Degree bounds for linear discrepancy of interval orders and disconnected posets

Let $P$ be a poset in which each point is incomparable to at most $\Delta$ others. Tanenbaum, Trenk, and Fishburn asked in a 2001 paper if the linear discrepancy of such a poset is bounded above by $?(3\Delta ?1)/2?$. This paper answers their question in the affirmative for two classes of posets. The first class is the interval orders, which are shown to have linear discrepancy at most $\Delta$, with equality precisely for interval orders containing an antichain of size $\Delta +1$. The stronger bound is tight even for interval orders of width 2. The second class of posets considered is the disconnected posets, which have linear discrepancy at most $?(3\Delta ?1)/2?$. This paper also contains lemmas on the role of critical pairs in linear discrepancy as well as a theorem establishing that every poset contains a point whose removal decreases the linear discrepancy by at most 1.     

Algorithms for some graph theoretical optimization problems

This is a summary of the main results presented in the author’s PhD thesis. This thesis, written in English, was supervised by Frits Spieksma and defended on September 23, 2005 at the Katholieke Universiteit Leuven. A copy of the thesis is available from the authors website (http://www.econ. kuleuven.be/linda.moonen/public/). The thesis can be roughly split into two parts. The first part is dedicated to the problem of partitioning partially ordered sets into chains of limited size. The second part deals with the structure and the connectivity of the Internet.     

Preemptive scheduling and antichain polyhedra

We present a theoretical framework, which is based upon notions of ordered hypergraphs and antichain polyhedra, and which is dedicated to the combinatorial analysis of preemptive scheduling problems submitted to parallelization constraints.This framework allows us to characterize specific partially ordered structures which are such that induced preemptive scheduling problems may be solved through linear programming. To prove that, in the general case, optimal preemptive schedules may be searched inside some connected subset of the vertex set of an Antichain Polyhedron.     

Herz型空间中的分数次积分算子的弱型估计

本文研究了Herz型空间中的分数次积分算子的弱型估计,与陆善镇和杨大春在文献[1]中给出的强型估计一起完整地建立了Herz型空间中的分数次积分算子的Hardy－Littlewood－Sobolev定理．     

Fuzzy Optimality Conditions for Fractional Multiobjective Bilevel Problems Under Fractional Constraints

In this article, we are concerned with fractional multiobjective optimization problems. In order to derive optimality conditions, we consider a new single level problem [12 J.J. Ye ( 2006 ). Constraint qualification and KKT conditions for bilevel programming problems . Mathematics of Operations Research 31 : 811 – 824 .[Crossref], [Web of Science ®] , [Google Scholar]], which is locally equivalent to the bilevel fractional multiobjective problem (P) at the optimal solution. Our approach consists of using another approach initiated by Mordukhovich [7 B.S. Mordukhovich ( 1976 ). Maximum principle in problems of time optimal control with nonsmooth constraints . J. Appl. Math. Mech. 40 : 960 – 969 .[Crossref], [Web of Science ®] , [Google Scholar], 8 B.S. Mordukhovich ( 1980 ). Metric approximations and necessary optimality conditions for general classes of nonsmooth extremal problems . Soviet. Math. Dokl. 22 : 526 – 530 . [Google Scholar]], which does not involve any convex approximations and convex separation arguments, called the extremal principle [5 B.S. Mordukhovich ( 2006 ). Variational Analysis and Generalized Differentiation, I: Basic Theory . Grundlehren Series (Fundamental Principles of Mathematical Sciences) , Vol. 330 , Springer , Berlin . [Google Scholar], 6 B.S. Mordukhovich ( 2006 ). Variational Analysis and Generalized Differentiation, II: Applications , Grundlehren Series (Fundamental Principles of Mathematical Sciences) , Vol. 331 , Springer , Berlin . [Google Scholar], 9 B.S. Mordukhovich ( 1994 ). Generalized differential calculus for nonsmooth and set-valued mappings . J. Math. Anal. Appl. 183 : 250 – 288 .[Crossref], [Web of Science ®] , [Google Scholar]], for the study of necessary optimality conditions in fractional vector optimization.