Timeline for Optimal schedule for a soccer tournament
Current License: CC BY-SA 4.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 27, 2023 at 12:56 | comment | added | Dominic van der Zypen | Thanks for putting in such an effort, everyone! As many contributed towards finding an optimal schedule, I would have wished to be able to accept several answers. | |
| Apr 27, 2023 at 12:55 | vote | accept | Dominic van der Zypen | ||
| Apr 27, 2023 at 12:55 | comment | added | Dominic van der Zypen | @JonathanLove Thanks for your thoughts on the definition of ovmax. Your definition is exactly what I had in mind, I have to check whether I made a formal error and will try to mend it. | |
| Apr 27, 2023 at 2:17 | comment | added | Jonathan Love | In fact it's easy to design such a schedule with ovmax = n. So yes, big compared to the predicted optimum ≈ n/2, but far below the (n^2-n)/2 games one team has to wait. It's true this example won't be a super schedule, but what if we found a schedule with ovmin=BESTMIN and ovmax=BESTMAX, but this schedule requires one team to wait, say, 3n turns before first playing, while there are other schedules with no wait (including at beginning and end) longer than n/2+2. Should this schedule really be considered optimal? @DominicvanderZypen which option most closely addresses your original musings? | |
| Apr 27, 2023 at 1:55 | comment | added | Jonathan Love | @PeterTaylor Yes but can't the remaining teams have the rest of their matches fairly well-distributed? In particular, if you design an n-person tournament in which no team has to wait more than n matches (including at the end), and then have each team play the (n+1)st team at the very end, the new ovmax should be < 2n, but team n+1 has to wait on the order of n^2 matches before they can play. So ovmax is really not doing a good job of capturing wait time. | |
| Apr 26, 2023 at 23:39 | comment | added | Peter Taylor | @JonathanLove, a schedule which puts all of one team's games at the very end gives a big ovmax because the teams which played the first match also need to play that team. | |
| Apr 26, 2023 at 22:17 | comment | added | Jonathan Love | I'm curious why we don't define ovmax in terms of the longest consecutive stretch of matches in which team t does not play. (Or equivalently, set sl(t)_0 = 0 and sl(t)_n = nC2 + 1 for all t; eg for opening and closing ceremonies). This feels like a more natural translation of the original problem: under the current setup, a schedule which puts all of one team's games at the very end could have very small ovmax, when in reality the team in question would be pretty upset at having to wait so long before playing. (It's also easier to prove bounds on bestmax using the new definition.) | |
| Apr 26, 2023 at 20:46 | answer | added | David E Speyer | timeline score: 5 | |
| Apr 26, 2023 at 14:44 | answer | added | Peter Taylor | timeline score: 3 | |
| Apr 26, 2023 at 6:09 | answer | added | HenrikRüping | timeline score: 3 | |
| Apr 25, 2023 at 16:34 | comment | added | HenrikRüping | Especially the modified strategy of David Speyer for even $n=2k$ realises $ovmin=k-1$ and $ovmax=k+1$. So Peter Taylors bounds are sharp and this is a super schedule for even $n$. | |
| Apr 25, 2023 at 13:43 | comment | added | Peter Taylor | It's easy to prove that $\textrm{BESTMIN}(n) \le \lfloor \frac{n-1}{2}\rfloor$. I conjecture that this is tight, that $\textrm{BESTMAX}(n) = \lfloor \frac{n+2}{2} \rfloor$, and that there is a super schedule; but I've so far only managed to test it up to $n=7$. | |
| Apr 25, 2023 at 11:16 | answer | added | David E Speyer | timeline score: 3 | |
| Apr 24, 2023 at 20:09 | comment | added | Dominic van der Zypen | I introduced consecutive slots and hope the definitions of both $\text{ovmin}(\sigma)$ and $\text{ovmax}(\sigma)$ work that way. Thanks again to @LeechLattice | |
| Apr 24, 2023 at 20:08 | history | edited | Dominic van der Zypen | CC BY-SA 4.0 |
corrected definition of \text{ovmax}(\sigma}
|
| Apr 24, 2023 at 18:04 | history | edited | Dominic van der Zypen | CC BY-SA 4.0 |
added 103 characters in body
|
| Apr 24, 2023 at 15:50 | comment | added | Dominic van der Zypen | Good point, thanks @LeechLattice! It's actually wrong that $\text{ovmax}(\sigma)$ is the maximum of all breaks that any team has in consecutive games. I need to reformulate $\text{ovmax}(\sigma)$. Will sit down with paper & pencil and edit the post as soon as I (think I) found the correct definition of $\text{ovmax}(\sigma)$. | |
| Apr 24, 2023 at 10:11 | comment | added | LeechLattice | Are you sure that $\text {ovmax}(\sigma )$ is the maximum of all breaks that any team has in consecutive games? | |
| Apr 24, 2023 at 8:16 | history | edited | Dominic van der Zypen | CC BY-SA 4.0 |
amended the informal question
|
| Apr 24, 2023 at 8:08 | comment | added | Dominic van der Zypen | Thanks for your question @fedja, that's correct, there are no parallel games. So for game number $0$ we look at the schedule $\sigma(0) \in [\text{enum}(n)]^2$, which has the form $\sigma(0) = \{a,b\}$, which means that game number $0$ is played between teams $a$ and $b$. Then for the next game, played after game number $0$ we have $\sigma(1) = \{c,d\}$ for some $c,d$, and that game is between teams $c$ and $d$, and so on. | |
| Apr 23, 2023 at 19:46 | comment | added | fedja | You assume that exactly one game is played on each day, right? | |
| Apr 23, 2023 at 16:17 | history | edited | Dominic van der Zypen | CC BY-SA 4.0 |
tried to write better English in the motivational part
|
| Apr 23, 2023 at 15:14 | history | asked | Dominic van der Zypen | CC BY-SA 4.0 |