Timeline for Greedy simplices in an ultrametric space (generalized Bhargava $p$-orderings)
Current License: CC BY-SA 4.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 3, 2018 at 18:55 | comment | added | Fedor Petrov | I think, both your questions about matroids and greedoids have positive answer, please see chat | |
| Oct 30, 2018 at 19:01 | history | edited | darij grinberg | CC BY-SA 4.0 |
improved (I like to think) writing
|
| Oct 30, 2018 at 18:23 | history | edited | Fedor Petrov | CC BY-SA 4.0 |
deleted 2 characters in body
|
| Oct 30, 2018 at 17:56 | history | edited | Fedor Petrov | CC BY-SA 4.0 |
deleted 96 characters in body
|
| Oct 30, 2018 at 17:34 | comment | added | darij grinberg | ... the $m+1$ sets $\left\{w_0, w_1, \ldots, w_i\right\}$ for $i \in \left\{0,1,\ldots,m\right\}$ maximizes $f$ (among all sets of size $i+1$). This criterion is easy to prove (the "if" direction follows from the definition of greediness, whereas the "only if" direction follows from your $(\star)$). Note: I should probably talk of multisets, not of sets, since for $m \geq \left|U\right|$ we would start encountering the same elements twice. | |
| Oct 30, 2018 at 17:34 | comment | added | Fedor Petrov | Let us continue this discussion in chat. | |
| Oct 30, 2018 at 17:33 | comment | added | darij grinberg | ... must be an equality, because your claim $(\ast)$ yields $f\left(\left\{v_0, v_1, \ldots, v_m\right\}\right) \geq f\left(\left(v_0, v_1, \ldots, v_{i-1}, v, v_{i+1}, v_{i+2}, \ldots, v_m\right)\right)$. Thus, these inequalities all become equalities. So $d\left(v_j, v_i\right) = d\left(v_j, v\right)$. Now, it suffices to note the following criterion for greediness: An $m$-simplex $\left(w_0, w_1, \ldots, w_m\right)$ is greedy if and only if each of ... | |
| Oct 30, 2018 at 17:31 | comment | added | darij grinberg | In other news, I've got a "greedy" analogue of your exchange lemma: If $\left(v_0, v_1, \ldots, v_m\right)$ is a greedy $m$-simplex, and if $v \in U$, then there exists some $0 \leq i \leq m$ such that $\left(v_0, v_1, \ldots, v_{i-1}, v, v_{i+1}, v_{i+2}, \ldots, v_m\right)$ is a greedy $m$-simplex as well. To prove this, I choose $i$ such that $d\left(v, v_i\right)$ is minimal. Then, the ultrametric axiom yields $d\left(v_j, v_i\right) \leq d\left(v_j, v\right)$ for all $j$. But the sum of these inequalities ... | |
| Oct 30, 2018 at 17:27 | comment | added | darij grinberg | Why can you enumerate the elements in this way? | |
| Oct 30, 2018 at 17:24 | comment | added | Fedor Petrov | Well, I was too fast, need thinking. Now why maximal sets are greedy. Let above $T$ be maximal. Then we enumerate the elements of $T$ by $u_0,u_1,\dots,u_m$ so that $d(u_i,u_k)=d(v_i,u_k)$ for all $i<k$ and also for all $i$, $\sum_{j<i} d(v_i,v_j)=\sum_{j<i}d(u_i,v_j)$ - since all above inequalities must turn into equalities.Thus $\sum_{j<i} d(u_i,u_j)=\sum_{j<i} d(u_i,v_j)=\sum_{j<i} d(v_i,v_j)$ and our set is indeed greedy. | |
| Oct 30, 2018 at 17:16 | comment | added | darij grinberg | I don't see why it is obvious. For the basis axiom, you have to exchange an element from $B_2 \setminus B_1$ for an element of $B_1 \setminus B_2$, not just for an element of $B_1$. | |
| Oct 30, 2018 at 17:13 | comment | added | Fedor Petrov | Maximum perimeter sets of given size are bases of a matroid, this follows from the exchange lemma, does not it? | |
| Oct 30, 2018 at 16:28 | comment | added | darij grinberg | Also, probably a non-equivalent questions: Do the greedy $m$-simplices regarded as sets form the bases of a matroid? | |
| Oct 30, 2018 at 16:23 | comment | added | darij grinberg | Greedoids, at least defined as in Section 1 of A. Bjorner, L. Lovasz, P. W. Shor, Chip-firing games on graphs, are something like a noncommutative analogue of matroids (in the sense that independent sets have become independent tuples). Anyway, forget about greedoids for now: The greedy simplices don't form a greedoid (it's not locally free). But maybe the $m$-element subsets with maximum perimeter are the bases of a matroid? | |
| Oct 30, 2018 at 16:20 | comment | added | Fedor Petrov | For me too, also I do not know what are greedoids:) | |
| Oct 30, 2018 at 16:15 | comment | added | darij grinberg | This is beautiful! And the exchange lemma reminds me even more of matroids (or greedoids, for $n$-simplices are not just subsets). | |
| Oct 30, 2018 at 16:13 | vote | accept | darij grinberg | ||
| Oct 30, 2018 at 14:52 | history | edited | Fedor Petrov | CC BY-SA 4.0 |
added 15 characters in body
|
| Oct 30, 2018 at 14:38 | history | edited | Fedor Petrov | CC BY-SA 4.0 |
added 39 characters in body
|
| Oct 30, 2018 at 14:32 | history | answered | Fedor Petrov | CC BY-SA 4.0 |