Timeline for Number of unique sortings of subset-sums
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 27, 2012 at 15:19 | vote | accept | Craig Feinstein | ||
| Sep 21, 2010 at 12:55 | comment | added | Craig Feinstein | Gerry, see rjlipton.wordpress.com/2009/02/17/… | |
| Sep 21, 2010 at 3:56 | comment | added | Gerry Myerson | Craig, can you tell us more than "a theorem by Dobkin and Lipton"? Say, the title of a paper? | |
| Sep 21, 2010 at 2:27 | answer | added | Tracy Hall | timeline score: 9 | |
| Sep 20, 2010 at 15:25 | comment | added | Tracy Hall | @David Speyer: Don't forget hyperplanes like $a_1=a_3$. (For uniqueness, either the sets or their complements can be taken to be disjoint, but not necessarily both.) | |
| Sep 20, 2010 at 14:24 | comment | added | Tracy Hall | One simplifying observation: If you make the additional assumption that the $a_i$ are all positive, it reduces the number of sortings by a factor of exactly $2^n$. (Replacing any one number by its negative gives the same ordering under complementation with respect to that one index.) | |
| Sep 20, 2010 at 14:24 | comment | added | Craig Feinstein | I am guessing that the answer is $2^{\Theta(n^2/2)}$, because of a theorem by Dobkin and Lipton. | |
| Sep 20, 2010 at 13:53 | comment | added | David E Speyer |
Nice question. One way to phrase it is to ask how many regions $\mathbb{R}^n$ is divided into by the hyperplanes of the form $\sum_{i \in I} a_i = \sum_{j \not \in I} a_j$. I feel like this example should be in some survey on combinatorics of hyperplane arrangements, but I don't know which one.
|
|
| Sep 20, 2010 at 13:47 | history | edited | David E Speyer | CC BY-SA 2.5 |
Fixed Latex
|
| Sep 20, 2010 at 13:45 | comment | added | Craig Feinstein | I tried to put all 8 sortings of S_2, but it stopped me. Here they are: {0<a_1<a_2<a_1+a_2, 0<a_2<a_1<a_1+a_2, a_2<0<a_1+a_2<a_1, a_1<0<a_1+a_2<a_2, a_2<a_1+a_2<0<a_1, a_1<a_1+a_2<0<a_2, a_1+a_2<a_1<a_2<0, a_1+a_2<a_2<a_1<0. | |
| Sep 20, 2010 at 13:39 | history | asked | Craig Feinstein | CC BY-SA 2.5 |