Clarkson & SHor
--I must correct an error -- Clarkson & Shor's bounds on the number of k-sets (all k combined) were not quite as strong as I'd said. Their lower bound (and my easy upper) are C_D * N^D / f(N) <= #sets <= 2 * (N choose D) where f(N) has to go to infinity with N, arbitrarily slowly... for example loglogloglogN... this valid when N large, D fixed, any fixed epsilon>0. Thus these bounds do not quite match. [But one can match the upper bound when D<=2.] Hence my lower bound on #WilsonOrderings has to be slightly reduced from what I'd said, by a factor f(N). Since for every ordering, we get a halving (namely the set that is the first half of the ordering), we also find from the Lovasz-Seidel lower bound on halvings a different lower bound #Orderings >= N^(D-1) * logN * C_D for N large, D>=2 fixed. This is not as good as my lower bound using Clarkson-Shor as corrected.
There is a substantial gap between the upper and lower bounds...
It now occurs to me how to find a different upper bound for Wilson's ordering problem. For simplicity focus on the case D=3 dimensions, N generic points. Suppose they have some "vertical" ordering. Rotate the point set bodily by the least possible angle needed to change the vertical ordering, minus epsilon. This causes exactly two of the points, A & B, to have almost-equal heights (rotating a bit more would swap them in the order). Now fix the line thru AB, and rotate the point set bodily about said line, by the least possible angle to change the ordering, minus epsilon. Now, we either have exactly 3 points A,B,C at almost same height, or we have two pairs of points A,B and A',B', with both pair members at almost-same height. (Throughout we agree to regard epsilon as infinitesimally small positive.) The point set now is frozen and cannot be rotated further. So in this way, each ordering is associated via a 1-to-1 or 1-to-many map, to either an ordered triple of points A,B,C, or two ordered pairs of points A,B and A',B'. Hence when D=3 the number of orderings is upper bounded by N*(N-1)*(N-2)*(N-3) + N*(N-1)*(N-2) = N*(N-1)*(N-2)^2. Now stop fixing D=3 and allow any dimension. The initial rotation finds two points A & B which then become of almost same height. But now, since we fix the line AB and rotate while preserving line, we have a D-1 dimensional problem. This allows an induction on #dimensions. Thus we find: #orderings(D,N) <= N*(N-1) * #orderings(D-1,N-2). This does not seem as good as my previous upper bound in large dimensions, but might be of some use. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)