Timeline for Convex hull of total orders
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Feb 15, 2017 at 21:57 | history | suggested | Rodrigo de Azevedo |
added new tag
|
|
| Feb 15, 2017 at 21:39 | review | Suggested edits | |||
| S Feb 15, 2017 at 21:57 | |||||
| Aug 12, 2014 at 4:13 | answer | added | Christian Remling | timeline score: 8 | |
| Aug 11, 2014 at 18:55 | vote | accept | Mostafa - Free Palestine | ||
| Aug 11, 2014 at 18:54 | vote | accept | Mostafa - Free Palestine | ||
| Aug 11, 2014 at 18:54 | |||||
| S Aug 11, 2014 at 18:49 | history | bounty ended | Per Alexandersson | ||
| S Aug 11, 2014 at 18:49 | history | notice removed | Per Alexandersson | ||
| Aug 11, 2014 at 16:30 | answer | added | David E Speyer | timeline score: 16 | |
| Aug 11, 2014 at 16:19 | comment | added | David E Speyer | @JairoBochi There can't be such a map. The convex hull of the $v_{ij}$ only has dimension $\binom{n}{2}$; the Birkhoff-von Neumann polytope has dimension $(n-1)^2$. | |
| S Aug 7, 2014 at 14:56 | history | bounty started | Per Alexandersson | ||
| S Aug 7, 2014 at 14:56 | history | notice added | Per Alexandersson | Draw attention | |
| Jun 17, 2014 at 23:35 | comment | added | Jairo Bochi | Given a total order $t$ we can associate a permutation $P_t$ matrix in an obvious way. There is a theorem by Birkhoff and von Neumann which says that the convex hull of permutation matrices is the set of doubly stochastic matrices. My first idea would be to relate your question with this theorem. However, it's not clear how to do that. Question: Is there a linear map $L$ such that if a vector $(v_{ij})$ comes (by the rule above) from a total order $t$ then its image $L((v_{ij}))$ is the permutation matrix $P_t$? I don't know. | |
| Jun 15, 2014 at 11:51 | comment | added | Per Alexandersson | Nice! It is really a stronger condition (in fact very strong). For example, your polytope has a totally unimodular triangulation, and is therefore also integrally closed. | |
| Jun 14, 2014 at 14:15 | comment | added | Per Alexandersson | It depends on the structure of matrix that determines the inequalities and equalities, but since it is very sparse, it might be possible. But it is a very strong condition to be totally unimodular. Check wikipedia about totally unimodular matrices, there are some conditions that might be somewhat strightforward to check. | |
| Jun 14, 2014 at 12:27 | history | edited | Mostafa - Free Palestine | CC BY-SA 3.0 |
deleted 6 characters in body
|
| Jun 14, 2014 at 12:26 | comment | added | Mostafa - Free Palestine | @PerAlexandersson Thanks, But how one can check the modularity of this big set of inequalities? | |
| Jun 13, 2014 at 20:49 | comment | added | Per Alexandersson | Ok, so, it is clear that all total orders are in this polytope, and also that every lattice point in this polytope defines a total order. Thus, you need to show that this polytope has only integer vertices, right? Can it be perhaps that this polytope is totally unimodular? That would be a nice property. | |
| Jun 13, 2014 at 19:10 | comment | added | Mostafa - Free Palestine | @PerAlexandersson If $i\prec j$ and $j\prec k$ then $v_{ji}=v_{kj}=0$ so by 3) $v_{ki}=0$ then $i\prec k$. In fact 3) is equivalent to transitivity of order. | |
| Jun 13, 2014 at 16:59 | comment | added | Per Alexandersson | Is it obvious that $i<i$ and $j<k$ implies $i<k$, under these conditions? Is this what 3) is supposed to say? I dont think the current version works. | |
| Jun 13, 2014 at 16:51 | history | asked | Mostafa - Free Palestine | CC BY-SA 3.0 |