This preprint was accepted September 7, 2004
ABSTRACT:
Informally, a family $\F\subseteq S_n$ of permutations
is $k$-rankwise independent if, for any $X\subseteq[n]$ with $|X|\leq k$,
all elements of $X$ are mapped in any possible order equally likely.
It has been shown that $|\F|\geq\frac{n^d}{d!}(1+o(1))$
when $k=2d+1$ is odd, and $|\F|\geq\frac{n^d}{d!2^{d-1}}(1+o(1))$
when $k=2d$ is even.
In this paper we show that $|\F|\geq \frac{!d+!(d+1)}{d!}n^d(1+o(1))$
when $k=2d+1$ is odd, and $|\F|\geq \frac{!d}{d!}n^d(1+o(1))$ when $k=2d$ is even.
Here $!k$ denotes the subfactorial of $k$ given by $!k=k!\sum_{i=0}^k{(-1)^i\over i!}$.
In particular, we improve previously known bound by an extra multiplicative
factor exponential in $k$ and independent of $n$.
[Full text:
(.ps.gz)]