Timeline for Swaps in a permutation across an index
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 10, 2022 at 12:31 | answer | added | Christian Stump | timeline score: 3 | |
| Dec 24, 2021 at 5:11 | comment | added | David Pal | I think it's a good idea to explain how did I come up with the problem. Trying to solve some linear programs, I ended up studying the following function: $\operatorname{top}_K:\mathbb{R}^N \to \mathbb{R}$, where $\operatorname{top}_K(x_1, x_2, \dots,x_N)$ is defined as the sum of $K$ largest numbers from $x_1, x_2, \dots, x_N$. The function is continuous, convex and piecewise linear. Consider the function along some line $g(t) = \operatorname{top}_K(x_1^{(0)} + t v_1, x_2^{(0)} + t v_2, \dots, x_N^{(0)} + t v_N)$. The function $g(t)$ has at most $S_{N,K}$ breakpoints. | |
| Dec 21, 2021 at 2:29 | history | edited | Sam Hopkins |
edited tags; edited tags
|
|
| Dec 21, 2021 at 2:22 | answer | added | Brian Hopkins | timeline score: 1 | |
| Dec 20, 2021 at 23:17 | comment | added | Sam Hopkins | See for example the introduction of arxiv.org/abs/1802.08934 for an explanation of the connection between sorting networks and reduced decompositions. But really it's just a rephrasing of your question, not an answer. | |
| Dec 20, 2021 at 23:11 | comment | added | David Pal | @SamHopkins I don't understand the meaning of what you are saying. I guess I don't know the appropriate definitions. What is a "simple transposition"? What is a "reduced expression"? Can you please provide references to books or papers? | |
| Dec 20, 2021 at 22:05 | comment | added | Sam Hopkins | $S_{N,K}$ should be the maximum number of copies of the simple transposition $s_k=(k,k+1)$ in a reduced expression for the longest word $w_0 = n, n-1,\ldots, 1$. | |
| S Dec 20, 2021 at 21:56 | review | First questions | |||
| Dec 20, 2021 at 22:05 | |||||
| S Dec 20, 2021 at 21:56 | history | asked | David Pal | CC BY-SA 4.0 |