Duality for Semiantichains and Unichain Coverings in Products of Special Posets

Saks and West conjectured that for every product of partial orders, the maximum size of a semiantichain equals the minimum number of unichains needed to cover the product. We prove the case where both factors have width 2. We also use the characterization of product graphs that are perfect to prove other special cases, including the case where both factors have height 2. Finally, we make some observations about the case where both factors have dimension 2. Work supported in part by NSA Award No. H98230-06-1-0065.     

Linear Discrepancy of Chain Products and Posets with Bounded Degree

The linear discrepancy of a poset P, denoted ld(P), is the minimum, over all linear extensions L, of the maximum distance in L between two elements incomparable in P. With r denoting the maximum vertex degree in the incomparability graph of P, we prove that \({\rm ld}(P)\le \left\lfloor (3r-1)/2 \right\rfloor\) when P has width 2. Tanenbaum, Trenk, and Fishburn asked whether this upper bound holds for all posets. We give a negative answer using a randomized construction of bipartite posets whose linear discrepancy is asymptotic to the trivial upper bound 2r???1. For products of chains, we give alternative proofs of results obtained independently elsewhere.     

Bounds on Norms of Compound Matrices and on Products of Eigenvalues

An upper bound on operator norms of compound matrices is presented,and special cases that involve the l₁, l₂ and l norms are investigated.The results are then used to obtain bounds on products of thelargest or smallest eigenvalues of a matrix. 1991 MathematicsSubject Classification 15A15, 15A18, 15A42.     

代数的局部完备集范畴和FS-局部dcpo范畴的笛卡儿闭性

本文引入了代数的局部完备集,FS-局部dcpo,局部稳定映射等概念．主要结果是：以局部Scott连续映射为态射的代数的局部完备集范畴,以局部稳定映射为态射的代数的局部完备集范畴以及以局部Scott连续映射为态射的FS-局部dcpo范畴都是笛卡儿闭范畴．     

Explicit Bounds for Some Special Integral Inequalities on Time Scales

In this paper, we investigate some nonlinear integral inequalities on time scales, which provide explicit bounds on unknown functions. Our results, which can be used as handy tools to study the properties of certain dynamic equations on time scales, unify and extend some integral inequalities and their corresponding discrete analogues.     

Bounds on Special Subsets in Graphs, Eigenvalues and Association Schemes

We give a bound on the sizes of two sets of vertices at a given minimum distance in a graph in terms of polynomials and the Laplace spectrum of the graph. We obtain explicit bounds on the number of vertices at maximal distance and distance two from a given vertex, and on the size of two equally large sets at maximal distance. For graphs with four eigenvalues we find bounds on the number of vertices that are not adjacent to a given vertex and that have µ common neighbours with that vertex. Furthermore we find that the regular graphs for which the bounds are tight come from association schemes.     

Markov Chains on Graded Posets

We consider two types of discrete-time Markov chains where the state space is a graded poset and the transitions are taken along the covering relations in the poset. The first type of Markov chain goes only in one direction, either up or down in the poset (an up chain or down chain). The second type toggles between two adjacent rank levels (an up-and-down chain). We introduce two compatibility concepts between the up-directed transition probabilities (an up rule) and the down-directed (a down rule), and we relate these to compatibility between up-and-down chains. This framework is used to prove a conjecture about a limit shape for a process on Young’s lattice. Finally, we settle the questions whether the reverse of an up chain is a down chain for some down rule and whether there exists an up or down chain at all if the rank function is not bounded.     

A Note on the Homology of Signed Posets

Let S be a signed poset in the sense of Reiner [4]. Fischer [2] defines the homology of S, in terms of a partial ordering P (S) associated to S, to be the homology of a certain subcomplex of the chain complex of P (S).In this paper we show that if P (S) is Cohen-Macaulay and S has rank n, then the homology of S vanishes for degrees outside the interval [n/2, n].Research partially supported by the National Science Foundation and the John Simon Guggenheim Foundation.     

Varieties of Posets

We introduce and investigate the notion of a homomorphism, of a congruence relation, of a substructure of a poset and consequently the notion of a variety of posets. These notions are consistent with those used in lattice theory and multilattice theory. There are given some properties of the lattice of all varieties of posets.     

Preface of the Special Issue Error Bounds,Regularity, and Nonsmooth Optimization

Set-Valued and Variational Analysis -     

Some New Bounds for Singular Values and Eigenvalues of Matrix Products

For two Hermitian matrices A and B, at least one of which is positive semidefinite, we give upper and lower bounds for each eigenvalue of AB in terms of the eigenvalues of A and B. For two complex matrices A,B with known singular values, upper and lower bounds are deduced for each singular value of AB.     

Posets on up to 16 Points

In this article we describe a very efficient method to construct pairwise non-isomorphic posets (equivalently, T ₀ topologies). We also give the results obtained by a computer program based on this algorithm, in particular the numbers of non-isomorphic posets on 15 and 16 points and the numbers of labelled posets and topologies on 17 and 18 points.     

A Note on Blockers in Posets

The blocker A* of an antichain A in a finite poset P is the set of elements minimal with the property of having with each member of A a common predecessor. The following is done: (1) The posets P for which A** = A for all antichains are characterized.(2) The blocker A* of a symmetric antichain in the partition lattice is characterized.(3) Connections with the question of finding minimal size blocking sets for certain set families are discussed.AMS Subject Classification: 05C35, 05D05, 06A07.     

Cover-Incomparability Graphs of Posets

Cover-incomparability graphs (C-I graphs, for short) are introduced, whose edge-set is the union of edge-sets of the incomparability and the cover graph of a poset. Posets whose C-I graphs are chordal (resp. distance-hereditary, Ptolemaic) are characterized in terms of forbidden isometric subposets, and a general approach for studying C-I graphs is proposed. Several open problems are also stated.     

Three-Variable Equations of Posets

We find an independent base for three-variable equations of posets.     

Peckness of Edge Posets

For any graded poset P, we define a new graded poset, ??(P), whose elements are the edges in the Hasse diagram of P. For any group G acting on the boolean algebra B _n in a rank-preserving fashion we conjecture that ??(B _n /G) is Peck. We prove that the conjecture holds for “common cover transitive” actions. We give some infinite families of common cover transitive actions and show that the common cover transitive actions are closed under direct and semidirect products.     

偏序集上的滤子极大理想

在偏序集上引入并考察了滤子极大理想的概念,证明了相应的存在性定理。引入并考察了伪极大元和伪既约元的概念,利用图表的形式对连续格中各种类型的既约元和素元之间的关系进行了归纳总结,完善了文献《Continuous Lattices and Domains》(作者:G.Gierz,et al)中的一个图表的相关内容,填补了在分配的连续格情形该图表的一个未知内容,部分地回答了该文献中的一个问题。     

Upper Maximal Graphs of Posets

We introduce and study a class of simple graphs, the upper-maximal graphs (UM-graphs), associated to finite posets. The vertices of the UM-graph of a given poset P are the elements of P, and edges are formed by those vertices x and y whenever any maximal element of P that is greater than x is also greater than y or vise versa. We show that the class of UM-graphs constitutes a subclass of comparability graphs. We further provide a characterization of chordal UM-graphs, and compare UM-graphs with known bound graphs of posets.