Timeline for Minimum number of swaps to make multisets elements sums close
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 19, 2023 at 21:42 | comment | added | Luc Guyot | In relation with this question and your arrangement approach, I would have asked: "Consider $m$ sets with $n$ balls. Each set contains balls of the same colour and two distinct sets have distinct colours. Fill $m$ bins of size $n$ with the $mn$ coloured balls. What is the minimum number of swaps that render all bins monochrome? (we look for a number that is valid for every possible filling)." | |
| Dec 19, 2023 at 19:06 | comment | added | Fabius Wiesner | I have reformulated the minimum number of swaps for the "ordered arrangement" into this question and removed the previous one. | |
| Dec 18, 2023 at 11:26 | comment | added | Fabius Wiesner | @LucGuyot sorry I have no actual proof, I thought to have one but it wasn't that simple. I still suppose (but it is just a conjecture) that the actual bound might be lower than about $2n$. I have started a related question at math.stackexchange regarding the "ordered arrangement". | |
| Dec 18, 2023 at 11:21 | history | edited | Fabius Wiesner | CC BY-SA 4.0 |
added 93 characters in body
|
| Dec 17, 2023 at 23:46 | comment | added | Luc Guyot | In your last paragraph, you have sketched an approach leading to the upper bound of $\frac{3}{2}n$ swaps. Following this approach, I obtain the upper bound of $\frac{23}{12}n$ swaps (see updated answer). You certainly have a much clever way of choosing of swaps. Would you be kind enough to share some insight? | |
| Dec 17, 2023 at 12:30 | answer | added | Tony Huynh | timeline score: 4 | |
| Dec 15, 2023 at 20:12 | history | edited | Fabius Wiesner | CC BY-SA 4.0 |
Added conjectured maximum needed swaps for $q$ multisets
|
| Dec 15, 2023 at 9:52 | answer | added | Luc Guyot | timeline score: 1 | |
| Dec 15, 2023 at 7:16 | history | edited | Fabius Wiesner | CC BY-SA 4.0 |
added 6 characters in body
|
| Dec 14, 2023 at 10:57 | history | edited | Fabius Wiesner | CC BY-SA 4.0 |
edited body
|
| Dec 14, 2023 at 10:51 | history | asked | Fabius Wiesner | CC BY-SA 4.0 |