On poset similarity

Let P be a poset, and let A be an element of its strict incidence algebra. Saks (SIAM J. Algebraic Discrete Methods 1 (1980) 211–215; Discrete Math. 59 (1986) 135–166) and Gansner (SIAM J. Algebraic Discrete Methods 2 (1981) 429–440) proved that the kth Dilworth number of P is less than or equal to the dimension of the nullspace of A^k, and that there is some member of the strict incidence algebra of P for which equality is attained (for all k simultaneously). In this paper we focus attention on the question of when equality is attained with the strict zeta matrix, and proceed under a particular random poset model. We provide an invariant depending only on two measures of nonunimodality of the level structure for the poset that, with probability tending to 1 as the smallest level tends to infinity, takes on the same value as the inequality gap between the width of P and the dimension of the nullspace of its strict zeta matrix. In particular, we characterize the level structures for which the width of P is, with probability tending to 1, equal to the dimension of the nullspace of its strict zeta matrix. As a consequence, by the Kleitman–Rothschild Theorem 5, almost all posets in the Uniform random poset model have width equal to the dimension of the nullspace of their zeta matrices. We hope this is a first step toward a complete characterization of when equality holds in Saks’ and Gansner's inequality for the strict zeta matrix and for all k. New to this paper are also the canonical representatives of the poset similarity classes (where two posets are said to be similar if their strict zeta matrices are similar in the matrix-theoretic sense), and these form the setting for our work on Saks’ and Gansner's inequalities. (Also new are two functions that measure the nonunimodality of a sequence of real numbers.)     

On a poset of trees

We will prove that the path minimizes the number of closed walks of length ℓ among the connected graphs for all ℓ. Indeed, we will prove that the number of closed walks of length ℓ and many other properties such as the spectral radius, Estada index increase or decrease along a certain poset of trees. This poset is a leveled poset with path as the smallest element and star as the greatest element.     

On poset Boolean algebras of scattered posets with finite width

We prove that the poset algebra of every scattered poset with finite width is embeddable in the poset algebra of a well ordered poset.Mathematics Subject Classification (2000):Primary 03G05, 06A06, 06A11; Secondary 08A05, 54G12     

On the lattice of order ideals of an up-down poset

The combinatorial structure of the distributive lattice of order ideals of an up-down poset is studied. Two recursions are given for the Whitney numbers, and generating functions for the Whitney numbers are derived. In addition, an explicit nested chain decomposition is given for the lattice, the existence of which implies that the lattice satisfies the Sperner property and its generalizations, and has unimodal Whitney numbers.     

A poset hierarchy

This article extends a paper of Abraham and Bonnet which generalised the famous Hausdorff characterisation of the class of scattered linear orders. They gave an inductively defined hierarchy that characterised the class of scattered posets which do not have infinite incomparability antichains (i.e. have the FAC). We define a larger inductive hierarchy ^κℌ* which characterises the closure of the class of all κ-well-founded linear orders under inversions, lexicographic sums and FAC weakenings. This includes a broader class of “scattered” posets that we call κ-scattered. These posets cannot embed any order such that for every two subsets of size < κ, one being strictly less than the other, there is an element in between. If a linear order has this property and has size κ it is unique and called ℚ(κ). Partial orders such that for every a < b the set {x: a < x < b} has size ≥ κ are called weakly κ-dense, and posets that do not have a weakly κ-dense subset are called strongly κ-scattered. We prove that ^κℌ* includes all strongly κ-scattered FAC posets and is included in the class of all FAC κ-scattered posets. For κ = ℵ₀ the notions of scattered and strongly scattered coincide and our hierarchy is exactly aug(ℌ) from the Abraham-Bonnet theorem. The authors warmly thank Uri Abraham for his many useful suggestions and comments. Mirna Džamonja thanks EPSRC for their support on an EPSRC Advanced Fellowship.     

Balancing poset extensions

We show that any finite partially ordered setP (not a total order) contains a pair of elementsx andy such that the proportion of linear extensions ofP in whichx lies belowy is between 3/11 and 8/11. A consequence is that the information theoretic lower bound for sorting under partial information is tight up to a multiplicative constant. Precisely: ifX is a totally ordered set about which we are given some partial information, and ife(X) is the number of total orderings ofX compatible with this information, then it is possible to sortX using no more thanC log₂ e (X) comparisons whereC is approximately 2.17.Supported in part by NSF Grant MCS83-01867.     

Two poset polytopes

Two convex polytopes, called theorder polytope (P) andchain polytope (P), are associated with a finite posetP. There is a close interplay between the combinatorial structure ofP and the geometric structure of (P). For instance, the order polynomial (P, m) ofP and Ehrhart polynomiali((P),m) of (P) are related by (P, m+1)=i((P),m). A transfer map then allows us to transfer properties of (P) to (P). In particular, we transfer known inequalities involving linear extensions ofP to some new inequalities.Partially supported by NSF Grant No. 8104855-MCS and by a Guggenheim Fellowship.     

Inversion of adjunction on log canonicity

We prove inversion of adjunction on log canonicity. Mathematics Subject Classification (2000) 14E30, 14N30     

On expansions in orthogonal polynomials

A recently introduced fast algorithm for the computation of the first N terms in an expansion of an analytic function into ultraspherical polynomials consists of three steps: Firstly, each expansion coefficient is represented as a linear combination of derivatives; secondly, it is represented, using the Cauchy integral formula, as a contour integral of the function multiplied by a kernel; finally, the integrand is transformed to accelerate the convergence of the Taylor expansion of the kernel, allowing for rapid computation using Fast Fourier Transform. In the current paper we demonstrate that the first two steps remain valid in the general setting of orthogonal polynomials on the real line with finite support, orthogonal polynomials on the unit circle and Laurent orthogonal polynomials on the unit circle.     

Shelling the coset poset

It is shown that the coset lattice of a finite group has shellable order complex if and only if the group is complemented. Furthermore, the coset lattice is shown to have a Cohen-Macaulay order complex in exactly the same conditions. The group theoretical tools used are relatively elementary, and avoid the classification of finite simple groups and of minimal finite simple groups.     

On the poset of conjugacy classes of subgroups of finite p-groups

This paper is a continuation of the paper “On the Deskins completions, theta completions and theta pairs for maximal subgroups ”.In the former paper, Zhao Yaoqing introduced the concept of θ-completions associated to a maximal subgroup of a finite group. The concept offers a convenience for us to study the completions introduced by Deskins and gives us a way to reveal the relationship between the concepts of completions and θ-pairs, the latter concept is introduced by Mukherjee and Bhattacharya. The present paper is devoted to discussing the π-solvability, π-supersolvability and π-nilpotency of a finite group by using the θ-completions. Moreover, a new proof on the Deskins conjecture concerning the supersolvability is included.     

On convergence of wavelet packet expansions

It is well known that the-Walsh-Fourier expansion of a function from the block space ([0, 1 ) ), 1 ＜q≤∞, converges pointwise a.e. We prove that the same result is true for the expansion of a function from in certain periodixed smooth periodic non-stationary wavelet packets bases based on the Haar filters. We also consider wavelet packets based on the Shannon filters and show that the expansion of Lp-functions, 1＜p＜∞, converges in norm and pointwise almost everywhere.