Re the number of orderings of N points in D-space, in my previous post I showed it was upper bounded by a polynomial in H of degree D-1 and leading coefficient <= 4/D!, where H=N*(N-1)/2. I now produce a lower bound. The new insight is to think about (what have been called in the literature) "k-sets." http://en.wikipedia.org/wiki/K-set_(geometry) A k-set is a k-element subset (or for some other authors, a <=k-element subset) of N points got by chopping a fixed N-point set with a hyperplane, the k-set is what is on one side. Not all 2^N subsets are achievable. The total number of k-sets of a generic N-point set in D-space (for all k combined) is at most 2*(N choose D) because you can move the separating hyperplane until it is about to touch D of the N points, all on one side; this leaves the subset unaffected. This upper bound is, in fact, tight up to (at most) a dimension-dependent multiplicative constant factor. THat was shown by K.L. Clarkson & P.W.Shor: Applications of random sampling, II, Discrete Comput. Geom. 4,1 (1989) 387-421. http://www.cs.duke.edu/courses/spring07/cps296.2/papers/clarkson-shor.pdf Also perhaps of interest: the number of "halving hyperplanes" (k-sets with k=N/2, essentially) is known to be lower bounded by BigOmega( N^(D-1) * logN ) due to L.Lovasz and/or E.Straus in 1971 when D=2, and R.Seidel for D>2. L.Lovasz: On the number of halving lines, Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 14 (1971) 107-108 there also are interesting upper bounds on halvings... Now obviously the number of k-sets is upper bounded by the number of orderings (Wilson's problem) times N/2. Hence Theorem: The number of Wilson-orderings of N generic points in D-space is lower bounded by BigOmega( (4/N) * (N choose D) ) for N large, D fixed. There is a substantial gap between the upper and lower bounds... -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)