Timeline for Scheduling "parent talks" at school
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 12, 2023 at 12:13 | vote | accept | Dominic van der Zypen | ||
| Jan 9, 2023 at 16:32 | comment | added | Sam Hopkins | @KasperAndersen: yes, the connection to non-zero permanents of $(0,1)$-matrices with constant row sums is clear (see the comment of Matt F.). | |
| Jan 9, 2023 at 16:24 | comment | added | Kasper Andersen | Let $p(n,k)$ be the sought probability. For $n\geq 1$ obviously $p(n,0)=0$, $p(n,1)=n!/n^n$ and $p(n,n)=1$. Moreover $p(n,n-1)=1-n^{-(n-1)}$. For $n\leq 5$ the computer says that $p(n,2)=\text{A174586}(n)/\binom{n}{2}^n$. OEIS reference is A174586 | |
| Jan 9, 2023 at 16:09 | comment | added | Dominic van der Zypen | Thanks @SamHopkins -- this is exactly what I had in mind, and now it's written in a very clear and concise way. | |
| Jan 9, 2023 at 13:32 | comment | added | Sam Hopkins | I rewrote the "formal version" to match what I think is the intended meaning. | |
| Jan 9, 2023 at 13:31 | history | edited | Sam Hopkins | CC BY-SA 4.0 |
deleted 283 characters in body
|
| Jan 9, 2023 at 7:43 | comment | added | Random | My guess is that the threshold is about $\log n$, that is for $k > (1 + \varepsilon) \log n$ there should be a bijection. Here is a heuristic: in Hall's theorem the only obstruction should come from very large sets of parents, and in very large sets of parents the obstruction comes from a certain set of times that only few parents accept (then, removing the parents that accept those times we get the obstruction in Hall's theorem). However looking at the Wikipedia page on the coupon collector's problem, it seems that for $k > (1 + \varepsilon) \log n$ every time is accepted by many parents. | |
| Jan 9, 2023 at 7:19 | comment | added | Random | Not a full answer, but using Hall's theorem we can get a lower bound of $\log n$: by the coupon collector's problem we see that if $k < \log n$ with high probability at least one element of $\{1, \dots, n\}$ does not appear in any of the tuples, so we get a contradiction to Hall's theorem when taking the set of all parents. | |
| Jan 9, 2023 at 5:39 | answer | added | Robert Israel | timeline score: 4 | |
| Jan 8, 2023 at 23:33 | comment | added | Sam Hopkins | @FedorPetrov: the motivation suggests to me that it should be a random tuple (of $k$-element subsets), but I guess as written it is unclear. | |
| Jan 8, 2023 at 23:30 | comment | added | user44143 | Another statement: Given an $n\times n$ matrix of zeroes and ones with $k$ ones in each row, what is the probability that some rearrangement of rows produces ones all along the main diagonal? Or what is the least value of $k$ making that probability at least $\frac12$? | |
| Jan 8, 2023 at 23:25 | comment | added | Fedor Petrov | @SamHopkins is $\mathcal{S}$ a random set or a random sequence or a random multiset? I read the question as a "random set", then there is unique $n$-subset of $[n]^1$. | |
| Jan 8, 2023 at 22:57 | comment | added | Sam Hopkins | @FedorPetrov: I don't understand your suggestion. If $k=1$ then each parent has selects only one time slot and with high probability there is a collision between parents' selections, hence no perfect matching. | |
| Jan 8, 2023 at 21:46 | comment | added | Fedor Petrov | Is not it $k=1$? | |
| Jan 8, 2023 at 19:58 | history | edited | Dominic van der Zypen |
edited tags
|
|
| Jan 8, 2023 at 19:57 | comment | added | Dominic van der Zypen | Thanks - exactly this is the setting. Maybe given your hint, it is easy to find an exact formula answering my question? In that case I will delete it. | |
| Jan 8, 2023 at 19:56 | comment | added | Sam Hopkins | To check if a collection has the "satisfiability property" there is of course the famous "Hall's marriage theorem": en.wikipedia.org/wiki/Hall%27s_marriage_theorem. Presumably the condition in Hall's theorem will also be useful for answering your probabilistic question. | |
| Jan 8, 2023 at 19:53 | history | asked | Dominic van der Zypen | CC BY-SA 4.0 |