Motivation. My friend works in an organization that is re-organizing itself in the following somewhat laborious way: There are $n$ people currently sitting on $n$ jobs in total (everyone has one job). Everyone has to apply for exacty $3$ jobs. They are allowed to apply for the job they are currently on, but they don't have to. This prompts the question: how probable is it that in the end everyone can be matched with one of the jobs they applied for? Let's put this in a formal question.
Formal version. Let $k\leq n\in\mathbb{N}$ be positive integers. We write $[n]$ for the set $\{1,\ldots,n\}$. Denote the set of "employees" by $E_n := [n] \times\{1\}$, and the set of "jobs" by $J_n :=[n]\times \{2\}$. So $E_n, J_n$ each have $n$ elements, but they are disjoint.
A $k$-job selection is a set $S \subseteq E_n\times J_n$ such that for every $e\in E_n$ there are exactly $k$ elements $j\in J_n$ with $(e,j)\in S$. Hall's Marriage Theorem gives us a criterion that tells us when the resulting bipartite graph $(E_n \cup J_n, S)$ has a perfect matching.
For $n\in\mathbb{N}$, let $k(n)$ be the smallest positive integer such that at least for half of the $k(n)$-job selections $S\subseteq E_n\times J_n$ the bipartite graph $(E_n \cup J_n, S)$ has a perfect matching. That is $k(n)$ is the smallest integer such that if everyone applies for $k(n)$ jobs, the probability is at least $50\%$ that everyone can be matched with one of the jobs they applied for.
I am interested in the asymptotic behaviour of $k(n)$. More precisely: Is there an explicit formula for $k(n)$? If not, what is the value of $\lim\sup_{n\to\infty}k(n)/n$?
