Abstrakt
Rodina permutací $F \subseteq S_n$ s daným pravděpodobnostním rozdělením se nazývá 'k-restricted min-wise independent', pokud platí $Pr[min \pi(X) = \pi(x)] = 1/|X|$ pro libovolnou podmnožinu $X \subseteq [n]$ splňující $|X| l.e. k$, libovolné $x\in X$, a náhodně zvolené $\pi\in F$. Ukážeme jednoduchý důkaz Norinova výsledku, že každá taková rodina má velikost aspoň $\binom{n-1}{\lceil k-1/2\rceil}$.
Nejlepší známý dolní odhad na velikost takové rodiny je $1 + \Sum_{j=2}^k (j - 1)\binom{n}{j}$. Ukážeme, že tento odhad je těsný, pokud je snahou napodobit nikoliv rovnoměrné rozdělení na $S_n$, ale rozdělení určené prioritami prvků $[n]$.
Zkoumáme také případy, kdy se podmínka na nezávislost vyžaduje pouze pro množiny $X$ velikosti přesně $k$ (kdy máme pouze dolní odhad $\Omega(log log n + k)$) a pro množiny velikosti $k$ a $k - 1$ (kdy získáme dolní odhad $n - k + 2$).