Timeline for Minimum number of swaps to make multisets elements sums close
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 18, 2023 at 16:07 | comment | added | Luc Guyot | Let us continue this discussion in chat. | |
| Dec 18, 2023 at 15:38 | comment | added | Tony Huynh | I think the situation you describe is impossible since the fourth set always has sum at least $S/4$ while the first two always each have sum at most $S/4$. Thus, the largest element from the fourth set will always be at least as large as the smallest element from one of the first two sets. Also, I think we might not be done without performing the last swap. For example, $d_1=d_2=d_3=-0.33$ and $d_4=0.99$ is possible (in the first case). Feel free to send me an email if it is still unclear (my email can be easily found online). | |
| Dec 18, 2023 at 15:17 | comment | added | Luc Guyot | Thanks a lot for the additions, that's very kind of you. About: "we conclude that $\sigma(Y_3') \le \sigma(Y_1)$. What if after applying the last swap to $X_3$, we apply some swaps to the multisets with the lower sums, with the effect of not increasing these sums but lowering them? We wouldn't be able to conclude that $\sigma(Y_3') \le \sigma(Y_1)$. Can we rule such a situation out? Side remark: "Thus, after swapping $m_4$ and $\ell_1$, we are done." You are already done before the swap. (If it's too many questions in the comments, I can send them by emails instead). | |
| Dec 18, 2023 at 14:44 | comment | added | Tony Huynh | I added more details. Please let me know if it is clear. I think I can also prove the full theorem (without any special assumptions). I will write it up here when I have time. | |
| Dec 18, 2023 at 14:35 | history | edited | Tony Huynh | CC BY-SA 4.0 |
added 795 characters in body
|
| Dec 18, 2023 at 13:41 | comment | added | Luc Guyot | About "the other cases are similar". I thought I had successfully checked those other cases but I now find myself stuck with the case $\sigma(Y_1) \le \sigma(Y_2) \le \frac{S}{4}$. We certainly have $0 \le d_4 := d_1 + d_2 - d_3 < m_4 - \ell_1 \le 1$, but the subsequent discussion calls for more sub-cases and I fail to conclude. | |
| Dec 18, 2023 at 11:39 | comment | added | Luc Guyot | Thanks, got it! | |
| Dec 18, 2023 at 10:48 | comment | added | Tony Huynh | Thanks! Regarding your question, $\ell_1$ is the minimum of $Y_1$ but the $(n_1+1)$th smallest element of $X_1$ is a candidate for $\ell_1$, so the inequalities become even better if $\ell_1$ is not the $(n_1+1)$th smallest element of $X_1$. | |
| Dec 18, 2023 at 9:15 | comment | added | Luc Guyot | Wonderfully slick and simple! Checking my understanding: the integer $\ell_1$ is the $(n_1 + 1)$-th element of $X_1$ sorted in ascending order, but not necessarily the minimum of $Y_1$, right? (similar question for $m_4$). | |
| Dec 18, 2023 at 0:33 | history | edited | Tony Huynh | CC BY-SA 4.0 |
added 17 characters in body
|
| Dec 18, 2023 at 0:21 | history | edited | Tony Huynh | CC BY-SA 4.0 |
added 1985 characters in body
|
| Dec 17, 2023 at 16:07 | history | edited | Tony Huynh | CC BY-SA 4.0 |
added 67 characters in body
|
| Dec 17, 2023 at 16:01 | history | edited | Tony Huynh | CC BY-SA 4.0 |
added 67 characters in body
|
| Dec 17, 2023 at 15:54 | history | edited | Tony Huynh | CC BY-SA 4.0 |
added 67 characters in body
|
| Dec 17, 2023 at 12:30 | history | answered | Tony Huynh | CC BY-SA 4.0 |