5
$\begingroup$

Fix sets $T_1,\ldots T_m$ as a $k$-partition of $[m\cdot k]=\{1,2,\ldots,m\cdot k\}$, so that $|T_i|=k$ and $|T_i\cap T_\ell|=0$.

1) For any $j\le k$, how many sets $C\subset [m\cdot k]$ are there such that $|C|=k$ and $\max_{i}|T_i\cap C| = j$? Call this number $n(m,k,j)$ and call $N(m,k,j)$ the cumulative version where $\max_{i}|T_i\cap C| \le j$.

2) More generally, how many sets of the form $\{C_1,\ldots,C_m\}$ are there such that $C_1,\ldots,C_m$ is a $k$-partition of $[k\cdot m]$ where $\max_{i,\ell} |T_i\cap C_\ell| = j$?

Are asymptotic answers known/obvious for either of these two questions?

Note for the first question, an exact but clunky formula is given by the recursion: $$N(m,k,j) = \begin{cases} 0 & j < k/m \\ \binom{m}{k}k^k & j=1\text{ and }m\ge k\\ \sum_{i=0}^{\left\lfloor\frac{k}{j}\right\rfloor} \binom{m}{i} \binom{k}{j}^i N(m-i,k-ji,j-1) & \text{ otherwise} \end{cases}$$ (Choose the $T_i$'s that get exactly $j$ elements of $C$, then the locations of the $j$ elements in each of the chosen $T_i$'s, then choose the rest.)

In addition, the probability that a (uniformly) random set will have intersection more than the mean $k/m$ can be lower-bounded by choosing each element of $C$ independently, then using Chernoff and union bounds: $P[\max_i(T_i\cap C)-k/m > t] \le k e^{-2t^2/k}$. Then $$N(m,k,j) \ge N(m,k,k)(1-k e^{-2(j-\frac{k}{m})^2/k}).$$ A similar result can be shown for the second problem as well. Is this bound asymptotically tight?

$\endgroup$
  • 3
    $\begingroup$ For the asymptotics that interest you, which parameters remain fixed and which go to infinity? $\endgroup$ – Brendan McKay Sep 10 '15 at 1:54
  • $\begingroup$ Just saw this comment. I'm interested in the case when, for $n=mk$, $n$ goes to infinity, $k$ is a function of $n$, say $log(n)$, $m=n/k$, and $j$ is arbitrary. $\endgroup$ – chirpchirp Mar 26 '16 at 20:33
1
$\begingroup$

$N(m,k,j)$ equals the coefficient of $x^k$ in $$\left(\sum_{i=0}^j \binom{k}{i} x^i\right)^m.$$

$\endgroup$
  • 2
    $\begingroup$ This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. $\endgroup$ – Marco Golla Jul 9 '15 at 7:27
  • 10
    $\begingroup$ @MarcoGolla: This is neither critique, nor request for clarification. While it's not a complete answer either, it provides an insight into one of the quantities defined by the author. Comments do not format complex formulae nicely. $\endgroup$ – Max Alekseyev Jul 9 '15 at 15:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.