The crossing number of posets (Q1338132)

Given a finite poset \(P\) represented by a continuous function \(\xi= \{f_ x\}_{x\in P}\) on \([0,1]\) whose graphs \(G(f_ x)\) have certain intersection properties and such that \(x<y\) in \(P\) if \(f_ x(t)< f_ y(t)\) for all \(t\in [0,1]\), the crossing number \(\chi(P)\) is the minimum of \(\chi(\xi)= \max\{ G(f_ x)\cap G(f_ y)\mid x,y\in P, x\neq y\}\), where \(\xi\) ranges over all possible representations \(\xi\). This crossing number is thus an invariant of a ``geometric nature'', as is evident for some main results connecting it tightly to dimension theory for finite posets \(P\). Since the variety of possible \(\xi\)'s is very large, determining such numbers is usually no simple matter. These crossing numbers and their properties have nevertheless been found useful in demonstrating existence or non-existence of certain special posets, classified by dimension. It is therefore meaningful to add to general techniques for computing or estimating crossing numbers (as is done in this paper) as well as to determine the crossing number of particular posets (also done in this paper). In particular, products and lexicographic products are compared with components and the effect of removing maximal elements is studied. Also certain posets \(\psi_ n\), rank 1, rank \(n-1\) and middle rank(s) of \(B_ n= 2^ n\) are looked at in detail and shown to be crossing critical, i.e., removing points lowers crossing number. Thus, both as a general and a particular investigation this paper adds very worthwhile information to the subject area.