A Characterisation of Posets that Are nearly Antichains

We present a characterisation of posets of size n with linear discrepancy n − 2. These are the posets that are “furthest” from a linear order without being an antichain. This revised version was published online in September 2006 with corrections to the Cover Date.     

Maximal σ‐polynomials of connected 3‐chromatic graphs

In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if c_i(G) ≤ c_i(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where c_i(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003     

Compatibility and Marginality

We present a way of introducing joint distibution function and its marginal distribution functions for non-compatible observables. Each such marginal distribution function has the property of commutativity. Models based on this approach can be used to better explain some classical phenomena in stochastic processes.     

Large-Scale Regularities of Lattice Embeddings of Posets

Let N denote the set of natural numbers and let P =(N ^k , ) be a countably infinite poset on the k-dimensional lattice N ^k . Given x N ^k , we write max(x) (min(x)) for the maximum (minimum) coordinate of x. Let be the directed-incomparability graph of P which is defined to be the graph with vertex set equal to N ^k and edge set equal to the set of all (x, y) such that max(x) max(y) and x and y not comparable in P. For any subset D N ^k , we let P _D and _D denote the restrictions of P and to D. Points x N ^k with min(x) = 0 will be called boundary points. We define a geometrically natural notion of when a point is interior to P or relative to the lattice N ^k , and an analogous notion of monotone interior with respect to or _D . We wish to identify situations where most of these interior points are exposed to the boundary of the lattice or, in the case of monotone interior points, not concealed very much from the boundary. All of these ideas restrict to finite sublattices F ^k and/or infinite sublattices E ^k of N ^k . Our main result shows that for any poset P and any arbitarily large integer M > 0, there is an F E with F = M where, relative to the sublattices F ^k E ^k , the ideal situation of total exposure of interior points and very little concealment of monotone interior points must occur. Precisely, we prove that for any P =(N ^k , ) and any integer M > 0, there is an infinite E N and a finite D F ^k with F E and F = M such that (1) every interior vertex of P _{E k} or _{E k} is exposed and (2) there is a fixed set C E, C k ^k , such that every monotone-interior point of _D belonging to F ^k has its monotone concealment in the set C. In addition, we show that if P ¹ =(N ^k , ₁),..., P ^r =(N ^k , _r ) is any sequence of posets, then we can find E,D, and F so that the properties (1) and (2) described above hold simultaneously for each P ⁱ . We note that the main point of (2) is that the bound k ^k depends only on the dimension of the lattice and not on the poset P. Statement (1) is derived from classical Ramsey theory while (2) is derived from a recent powerful extension of Ramsey theory due to H. Friedman and shown by Friedman to be independent of ZFC, the usual axioms of set theory. The fact that our result is proved as a corollary to a combinatorial theorem that is known to be independent of the usual axioms of mathematics does not, of course, mean that it cannot be proved using ZFC (we just couldn"t find such a proof). This puts our geometrically natural combinatorial result in a somewhat unusual position with regard to the axioms of mathematics.     

Homotopy of Non-Modular Partitions and the Whitehouse Module

We present a class of subposets of the partition lattice _n with the following property: The order complex is homotopy equivalent to the order complex of _n – 1, and the S _n -module structure of the homology coincides with a recently discovered lifting of the S _n – 1-action on the homology of _n – 1. This is the Whitehouse representation on Robinson's space of fully-grown trees, and has also appeared in work of Getzler and Kapranov, Mathieu, Hanlon and Stanley, and Babson et al.One example is the subposet P _n ⁿ – 1 of the lattice of set partitions _n , obtained by removing all elements with a unique nontrivial block. More generally, for 2 k n – 1, let Q _n ^k denote the subposet of the partition lattice _n obtained by removing all elements with a unique nontrivial block of size equal to k, and let P _n ^k = _{i = 2} ^k Q _n ⁱ . We show that P _n ^k is Cohen-Macaulay, and that P _n ^k and Q _n ^k are both homotopy equivalent to a wedge of spheres of dimension (n – 4), with Betti number . The posets Q _n ^k are neither shellable nor Cohen-Macaulay. We show that the S _n -module structure of the homology generalises the Whitehouse module in a simple way.We also present a short proof of the well-known result that rank-selection in a poset preserves the Cohen-Macaulay property.     

Function Spaces of Posets with Projections

This paper investigates function spaces of structures consisting of a partially ordered set together with some directed family of projections.More precisely, given a fixed directed index set (I,), we consider triples (D,,(p _i ) _iI ) with (D,) a poset and (p _i ) _iI a monotone net of projections of D. We call them (I,)-pop's (posets with projections). Our main purpose is to study structure preserving maps between (I,)-pop's. Such homomorphisms respect both order and projections.Any (I,)-pop is known to induce a uniformity and thus a topology. The set of all homomorphisms between two (I,)-pop's turns out to form an (I,)-pop itself. We show that its uniformity is the uniformity of uniform convergence. This enables us to prove that properties such as completeness and compactness transfer to function pop's.Concerning categorical properties of (I,)-pop's, we will see that we are in a lucky situation from a computer scientist's point of view: we obtain Cartesian closed categories. Moreover, by a D -construction we get (I,)-pop's that are isomorphic to their own exponent. This yields new models for the untyped -calculus.     

An Asymptotic Ratio in the Complete Binary Tree

Let T _n be the complete binary tree of height n considered as the Hasse-diagram of a poset with its root 1 _n as the maximum element. For a rooted tree T, define two functions counting the embeddings of T into T _n as follows A(n;T)=|{S T _n  : 1 _n ∈S, S≅T}|, and B(n;T)=|{S T _n :1 _n ∉S, S≅T}|. In this paper we investigate the asymptotic behavior of the ratio A(n;T)/B(n;T), and we show that lim  _n→∞[A(n;T)/B(n;T)]=2^ℓ;−1−1, for any tree T with ℓ leaves. This revised version was published online in June 2006 with corrections to the Cover Date.     

Orbits of rational n-sets of projective spaces under the action of the linear group

Let k=Fq be a finite field. We enumerate k-rational n-sets of (unordered) points in a projective space PN over k, and we compute the generating function for the numbers of PGLN+1(k)-orbits of these n-sets. For N=1,2 we obtain a formula for these numbers of orbits as a polynomial in q with integer coefficients.