Small Families of Partially Shattering Permutations

Abstract We say that a family of permutations t -shatters a set if it induces at least t distinct permutations on that set. What is the minimum number $$f_k(n,t)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>f</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>t</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> of permutations of $$\{1, \dots , n\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>{</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> that t -shatter all subsets of size k ? For $$t \le 2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>t</mml:mi> <mml:mo>≤</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> , $$f_k(n,t) = \Theta (1)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>f</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>t</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>Θ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> . Spencer showed that $$f_k(n,t) = \Theta (\log \log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>f</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>t</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>Θ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> for $$3 \le t \le k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>≤</mml:mo> <mml:mi>t</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>k</mml:mi> </mml:mrow> </mml:math> and $$f_k(n,k!) = \Theta (\log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>f</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>k</mml:mi> <mml:mo>!</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>Θ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> . In 1996, Füredi asked whether partial shattering with permutations must always fall into one of these three regimes. Johnson and Wickes recently settled the case $$k = 3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> affirmatively and proved that $$f_k(n,t) = \Theta (\log n)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>f</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>t</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>Θ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> for $$t &gt; 2 (k-1)!$$ <mml:mat