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 20, 2023 at 22:08	history	edited	Luc Guyot	CC BY-SA 4.0	Highlight the best upper bound up to now (although it's certainly far from optimal, see Tony Huyn's lead and OP's conjecture)
Dec 20, 2023 at 10:45	history	edited	Luc Guyot	CC BY-SA 4.0	Gives an improved bound for the case of 3 multisets. Formulate the reduction to a seemingly simpler problem.
Dec 17, 2023 at 22:36	history	edited	Luc Guyot	CC BY-SA 4.0	Adds a (disappointing) corrigendum for the claim and a seemingly more interesting proposition whose proof follows OP's suggestion
Dec 16, 2023 at 15:36	history	edited	Luc Guyot	CC BY-SA 4.0	Fixes a typo
Dec 16, 2023 at 15:28	comment	added	Fabius Wiesner		Thank you for the effort and the detailed work.
Dec 16, 2023 at 14:35	comment	added	Luc Guyot		@FabiusWiesner I have tried to illustrate how Lemma 1 (for values of $\lambda < \frac{1}{2}$) could be useful with the computation of an upper bound for the number of swaps in the case of three multisets.
Dec 16, 2023 at 14:34	history	edited	Luc Guyot	CC BY-SA 4.0	Provides an upper for the number of swaps in the case of 3 multisets. Add details to proof of Lemma 1.
Dec 15, 2023 at 11:24	history	edited	Luc Guyot	CC BY-SA 4.0	Tightens the approximation error to 1/2.
Dec 15, 2023 at 11:21	comment	added	Luc Guyot		The 2nd order finite difference of $(s_i)$ is: $m_{i + 1} - m_i - (M_{i + 1} - M_i)$. For $\lambda = 1/2$, you get simultaneous approximation of the mean sum. But I felt that using smaller values of $\lambda$ could be useful when applying the lemma iteratively. I'll try to examplify this by proving the $3n/2$ bound.
Dec 15, 2023 at 10:51	comment	added	Fabius Wiesner		Thank you. It's not clear to me why the second order finite difference is non-negative. Also, shouldn't we check also $\sigma(B')$ together with $\sigma(A')$?
Dec 15, 2023 at 9:52	history	answered	Luc Guyot	CC BY-SA 4.0