Scheduling "parent talks" at school

Question

Real life motivation. In my younger son's class, there are $18$ students. His teacher provided $18$ time slots for the parents of each child to have a 30-minute conversation of their kid's progress in school and asked the parents to provide $4$ possible time slots that would be convenient for them. I wondered how probable it is that given all the choices, the teacher can select a convenient time slot for the parents of every child so that everyone can have the "progress conversation."

Formal version. We say that an $n$-tuple $(S_1,\ldots,S_n)$ of $k$-element subsets of $\{1,\ldots,n\}$ has the satisfiability property if there is a permutation $\sigma \in \mathfrak{S}_n$ with $\sigma(i)\in S_i$ for all $i=1,\ldots,n$.

Given an integer $n>1$, what is the smallest $k$ (in terms of $n$) such that at least half of the $n$-tuples $(S_1,\ldots,S_n)$ of $k$-element subsets of $\{1,\ldots,n\}$ have the satisfiability property? If no exact formula can be given, is there an approximation for when $n\to\infty$?

Answer 1

To restate the question in probabilistic language, each of the $n$ chldren's parents independently and with uniform probabilities chooses a $k$-element subset of $[n]$; say $X_i$ is the choice of child $i$'s parents. You want the probability that there is a successful assignment of parents to slots, corresponding to a permutation $\pi$ of $[n]$, such that $\pi(i) \in X_i$ for all $i$.

I don't know how to answer this question, but here's a related one that gives a bound. Consider a given permutation $\pi$. The probability that $\pi(i) \in X_i$ for all $i$ is $(k/n)^n$. Since there are $n!$ permutations, the expected number of successful permutations is $n! (k/n)^n$. As $n \to \infty$, by Stirling's approximation $n! \sim \sqrt{2\pi} n^{n+1/2} e^{-n}$. Of course the expected number of successful permutations is an upper bound on the probability of existence of at least one of them. Thus as long as $k \ge 3 > e$, the expected number of successful permutations should be greater than $1$ if $n$ is large enough, but if $k \le 2$ it will be less than $1$ (and go to $0$ as $n \to \infty$). For the example given with $k=4$ and $n=18$, $18! (4/18)^n \approx 11182$, while with $k=3$ and $n=18$, $18! (3/18)^n \approx 63$ .

I tried simulations to find the actual probabilities for $k = 3$ and $k=4$ with $n=18$. For $k=4$ I found success in $817$ cases out of $1000$, while for $k=3$ I found success in only $388$ out of $1000$.

Of course, in real life the probabilities are not likely to be uniform: there will be some very popular slots and others that nobody wants.

EDIT: I am not suggesting that with $k = O(1)$ we have a solution with high probability. The probability that a given day is not chosen by anyone (which obviously implies there is no successful permutation) is $(1 - k/n)^n \to e^{-k}$ as $n \to \infty$, and thus the expected number of days not chosen is $n e^{-k}$. If we want high probability of a successful permutation it seems reasonable to require this to go to $0$ as $n \to \infty$, and thus $k - \log(n) \to \infty$.