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.     

Counting Finite Lattices

The correct values for the number of all unlabeled lattices on n elements are known for . We present a fast orderly algorithm generating all unlabeled lattices up to a given size n. Using this algorithm, we have computed the number of all unlabeled lattices as well as that of all labeled lattices on an n-element set for each . Received April 4, 2000; accepted in final form November 2, 2001. RID="h1" ID="h1" Presented by R. Freese.     

Exact Counting of Unlabeled Rigid Interval Posets Regarding or Disregarding Height

In this paper, the author gives the exact counting of unlabeled rigid interval posets regarding or disregarding the height by using generating functions. The counting technique follows those introduced in El-Zahar (1989), Hanlon (Trans Amer Math Soc 272:383?C426, 1982), Khamis (Discrete Math 275:165?C175, 2004). The main advantage of the suggested technique is that a very simple recursive construction of unlabeled rigid interval poset from small ones leads to derive the given generating function for unlabeled rigid interval posets whose coefficients can be easily computed. Moreover, it is proven that the sets of n-element unlabeled rigid interval posets and upper triangular 0?C1 matrices with n ones and no zero rows or columns are in one-to-one correspondence. In addition, n-element unlabeled interval posets are counted for n????1, using the given generating function for rigid ones. Upper and lower bounds for the number of n-element unlabeled rigid interval posets are given. Also, an asymptotic estimate for the required numbers is obtained. Numerical results for unlabeled interval posets coincide with those given in El-Zahar (1989) and Khamis (Discrete Math 275:165?C175, 2004). The exact numbers of n-element unlabeled rigid and general interval posets with and without height k are included, for 1????k????n????15.     

The Number of Hierarchical Orderings

An ordered set-partition (or preferential arrangement) of n labeled elements represents a single “hierarchy” these are enumerated by the ordered Bell numbers. In this note we determine the number of “hierarchical orderings” or “societies”, where the n elements are first partitioned into m ≤ n subsets and a hierarchy is specified for each subset. We also consider the unlabeled case, where the ordered Bell numbers are replaced by the composition numbers. If there is only a single hierarchy, we show that the average rank of an element is asymptotic to n/(4 log 2) in the labeled case and to n/4 in the unlabeled case. This revised version was published online in September 2006 with corrections to the Cover Date.     

Counting finite posets and topologies

A refinement of an algorithm developed by Culberson and Rawlins yields the numbers of all partially ordered sets (posets) with n points and k antichains for n11 and all relevant integers k. Using these numbers in connection with certain formulae derived earlier by the first author, one can now compute the numbers of all quasiordered sets, posets, connected posets etc. with n points for n14. Using the well-known one-to-one correspondence between finite quasiordered sets and finite topological spaces, one obtains the numbers of finite topological spaces with n points and k open sets for n11 and all k, and then the numbers of all topologies on n14 points satisfying various degrees of separation and connectedness properties, respectively. The number of (connected) topologies on 14 points exceeds 10²³.     

Almost all trees are almost graceful

The Graceful Tree Conjecture of Rosa from 1967 asserts that the vertices of each tree T of order n can be injectively labeled by using the numbers {1,2,…,n} in such a way that the absolute differences induced on the edges are pairwise distinct. We prove the following relaxation of the conjecture for each γ>0 and for all n>n₀(γ). Suppose that (i) the maximum degree of T is bounded by ), and (ii) the vertex labels are chosen from the set {1,2,…,?(1+γ)n?}. Then there is an injective labeling of V(T) such that the absolute differences on the edges are pairwise distinct. In particular, asymptotically almost all trees on n vertices admit such a labeling. The proof proceeds by showing that a certain very natural randomized algorithm produces a desired labeling with high probability.     

Recursive reconstruction on periodic trees

A periodic tree T_n consists of full n-level copies of a finite tree T. The tree T_n is labeled by random bits. The root label is chosen randomly, and the probability of two adjacent vertices to have the same label is 1−ϵ. This model simulates noisy propagation of a bit from the root, and has significance both in communication theory and in biology. Our aim is to find an algorithm which decides for every set of values of the boundary bits of T, if the root is more probable to be 0 or 1. We want to use this algorithm recursively to reconstruct the value of the root of T_n with a probability bounded away from ½ for all n. In this paper we find for all T, the values of ϵ for which such a reconstruction is possible. We then compare the ϵ values for recursive and nonrecursive algorithms. Finally, we discuss some problems concerning generalizations of this model. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 81–97, 1998     

Asymptotic enumeration ofN-free partial orders

LetN(n) andN ^* (n) denote, respectively, the number of unlabeled and labeledN-free posets withn elements. It is proved thatN(n)=2 ^{n logn+o(n logn)} andN ^*(n)=2^{2n logn+o(n logn)}. This is obtained by considering the class ofN-free interval posets which can be easily counted.     

Involutions in triangular groups

We describe involutions, i.e. elements of order 2, in the groups T _n (K) – of upper triangular matrices of dimension n (n?∈??), and T _∞(K) – of upper triangular infinite matrices, where K is a field of characteristic different from 2. Using the obtained result, we give a formula for the number of all involutions in T _n (K) in the case when K is a finite field.     

Enumeration of totally positive Grassmann cells

Postnikov (Webs in totally positive Grassmann cells, in preparation) has given a combinatorially explicit cell decomposition of the totally nonnegative part of a Grassmannian, denoted Gr_k,n⁺, and showed that this set of cells is isomorphic as a graded poset to many other interesting graded posets. The main result of our work is an explicit generating function which enumerates the cells in Gr_k,n⁺ according to their dimension. As a corollary, we give a new proof that the Euler characteristic of Gr_k,n⁺ is 1. Additionally, we use our result to produce a new q-analog of the Eulerian numbers, which interpolates between the Eulerian numbers, the Narayana numbers, and the binomial coefficients.     

Partition Lattice q-Analogs Related to q-Stirling Numbers

We construct a family of partially ordered sets (posets) that are q-analogs of the set partition lattice. They are different from the q-analogs proposed by Dowling [5]. One of the important features of these posets is that their Whitney numbers of the first and second kind are just the q-Stirling numbers of the first and second kind, respectively. One member of this family [4] can be constructed using an interpretation of Milne [9] for S[n, k] as sequences of lines in a vector space over the Galois field F _q. Another member is constructed so as to mirror the partial order in the subspace lattice.     

Degrees of freedom versus dimension for containment orders

Given a family of sets L, where the sets in L admit k degrees of freedom, we prove that not all (k+1)-dimensional posets are containment posets of sets in L. Our results depend on the following enumerative result of independent interest: Let P(n, k) denote the number of partially ordered sets on n labeled elements of dimension k. We show that log P(n, k)nk log n where k is fixed and n is large.Research supported in part by Allon Fellowship and by a grant from Bat Sheva de Rothschild Foundation.Research supported in part by the Office of Naval Research, contract number N00014-85-K0622.     

Planar Graphs, via Well-Orderly Maps and Trees

The family of well-orderly maps is a family of planar maps with the property that every connected planar graph has at least one plane embedding which is a well-orderly map. We show that the number of well-orderly maps with n nodes is at most 2^αn+O(logn), where α≈4.91. A direct consequence of this is a new upper bound on the number p(n) of unlabeled planar graphs with n nodes, log₂p(n)≤4.91n. The result is then used to show that asymptotically almost all (labeled or unlabeled), (connected or not) planar graphs with n nodes have between 1.85n and 2.44n edges. Finally we obtain as an outcome of our combinatorial analysis an explicit linear-time encoding algorithm for unlabeled planar graphs using, in the worst-case, a rate of 4.91 bits per node and of 2.82 bits per edge.     

Extended symmetric spaces and θ-twisted involution graphs

Abstract

For a Weyl group G and an automorphism θ of order 2, the set of involutions and θ-twisted involutions can be generated by considering actions by basis elements, creating a poset structure on the elements. Haas and Helminck showed that there is a relationship between these sets and their Bruhat posets. We extend that result by considering other bases and automorphisms. We show for G = S_n, θ an involution, and any basis consisting of transpositions, the extended symmetric space is generated by a similar algorithm. Moreover, there is an isomorphism of the poset graphs for certain bases and θ.     

Lower bounds for the condition number of Vandermonde matrices

Summary We derive lower bounds for the -condition number of then×n-Vandermonde matrixV _n(x) in the cases where the node vectorx _T=[x₁, x₂,...,x_n] has positive elements or real elements located symmetrically with respect to the origin. The bounds obtained grow exponentially inn. withO(2ⁿ) andO(2^n/2), respectively. We also compute the optimal spectral condition numbers ofV _n(x) for the two node configurations (including the optimal nodes) and compare them with the bounds obtained.Dedicated to the memory of James H. WilkinsonSupported, in part, by the National Science Foundation under grant CCR-8704404     

Entropy of C(K)-Valued Operators

We investigate how the entropy numbers (e_n(T)) of an arbitrary Hölder-continuous operator T: E→C(K) are influenced by the entropy numbers (_n(K)) of the underlying compact metric space K and the geometry of E. We derive diverse universal inequalities relating finitely many _n(K)'s with finitely many e_n(T)'s which yield statements about the asymptotically optimal behaviour of the sequence (e_n(T)) in terms of the sequence (_n(K)). As an application we present new methods for estimating the entropy numbers of a precompact and convex subset in a Banach space E, provided that the entropy numbers of its extremal points are known.     

Angle orders,regular n-gon orders and the crossing number

A finite poset P(X,<) on a set X={ x ₁,...,x _m} is an angle order (regular n-gon order) if the elements of P(X,<) can be mapped into a family of angular regions on the plane (a family of regular polygons with n sides and having parallel sides) such that x _ij if and only if the angular region (regular n-gon) for x _i is contained in the region (regular n-gon) for x _j. In this paper we prove that there are partial orders of dimension 6 with 64 elements which are not angle orders. The smallest partial order previously known not to be an angle order has 198 elements and has dimension 7. We also prove that partial orders of dimension 3 are representable using equilateral triangles with the same orientation. This results does not generalizes to higher dimensions. We will prove that there is a partial order of dimension 4 with 14 elements which is not a regular n-gon order regardless of the value of n. Finally, we prove that partial orders of dimension 3 are regular n-gon orders for n3.This research was supported by the Natural Sciences and Engineering Research Council of Canada, grant numbers A0977 and A2415.     

Strongly continuous posets and the local Scott topology

In this paper, the concept of strongly continuous posets (SC-posets, for short) is introduced. A new intrinsic topology—the local Scott topology is defined and used to characterize SC-posets and weak monotone convergence spaces. Four notions of continuity on posets are compared in detail and some subtle counterexamples are constructed. Main results are: (1) A poset is an SC-poset iff its local Scott topology is equal to its Scott topology and is completely distributive iff it is a continuous precup; (2) For precups, PI-continuity, LC-continuity, SC-continuity and the usual continuity are equal, whereas they are mutually different for general posets; (3) A T₀-space is an SC-poset equipped with the Scott topology iff the space is a weak monotone convergence space with a completely distributive topology contained in the local Scott topology of the specialization order.     

A strong convergence theorem for asymptotically nonexpansive mappings in Banach spaces

Let C be a closed, convex subset of a uniformly convex Banach space whose norm is uniformly Gâteaux differentiable and let T be an asymptotically nonexpansive mapping from C into itself such that the set F (T) of fixed points of T is nonempty. Let {a_n} be a sequence of real numbers with 0 ￡ a_n ￡ 10 \leq a_n \leq 1, and let x and x₀ be elements of C. In this paper, we study the convergence of the sequence {x_n} defined by¶¶x_n+1=a_n x + (1-a_n) [1/(n+1)] ?_j=0ⁿ T^j x_n   x_{n+1}=a_n x + (1-a_n) {1\over n+1} \sum\limits_{j=0}^n T^j x_n\quad for n=0,1,2,...  . n=0,1,2,\dots \,.