A greedoid and a matroid inspired by Bhargava's \(p\)-orderings
The electronic journal of combinatorics, Tome 28 (2021) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Consider a finite set $E$. Assume that each $e \in E$ has a "weight" $w \left(e\right) \in \mathbb{R}$ assigned to it, and any two distinct $e, f \in E$ have a "distance" $d \left(e, f\right) = d \left(f, e\right) \in \mathbb{R}$ assigned to them, such that the distances satisfy the ultrametric triangle inequality $d(a,b)\leqslant \max \left\{d(a,c),d(b,c)\right\}$. We look for a subset of $E$ of given size with maximum perimeter (where the perimeter is defined by summing the weights of all elements and their pairwise distances). We show that any such subset can be found by a greedy algorithm (which starts with the empty set, and then adds new elements one by one, maximizing the perimeter at each step). We use this to define numerical invariants, and also to show that the maximum-perimeter subsets of all sizes form a strong greedoid, and the maximum-perimeter subsets of any given size are the bases of a matroid. This essentially generalizes the "$P$-orderings" constructed by Bhargava in order to define his generalized factorials, and is also similar to the strong greedoid of maximum diversity subsets in phylogenetic trees studied by Moulton, Semple and Steel. We further discuss some numerical invariants of $E, w, d$ stemming from this construction, as well as an analogue where maximum-perimeter subsets are replaced by maximum-perimeter tuples (i.e., elements can appear multiple times).
DOI : 10.37236/9046
Classification : 05B35, 52B40, 90C27, 92B10
Mots-clés : greedy algorithm, Bhargava greedoid

Darij Grinberg  1   ; Fedor Petrov  2

1 University of Minnesota, Twin Cities
2 St. Petersburg State University
@article{10_37236_9046,
     author = {Darij Grinberg and Fedor Petrov},
     title = {A greedoid and a matroid inspired by {Bhargava's} \(p\)-orderings},
     journal = {The electronic journal of combinatorics},
     year = {2021},
     volume = {28},
     number = {3},
     doi = {10.37236/9046},
     zbl = {1467.05027},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9046/}
}
TY  - JOUR
AU  - Darij Grinberg
AU  - Fedor Petrov
TI  - A greedoid and a matroid inspired by Bhargava's \(p\)-orderings
JO  - The electronic journal of combinatorics
PY  - 2021
VL  - 28
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9046/
DO  - 10.37236/9046
ID  - 10_37236_9046
ER  - 
%0 Journal Article
%A Darij Grinberg
%A Fedor Petrov
%T A greedoid and a matroid inspired by Bhargava's \(p\)-orderings
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/9046/
%R 10.37236/9046
%F 10_37236_9046
Darij Grinberg; Fedor Petrov. A greedoid and a matroid inspired by Bhargava's \(p\)-orderings. The electronic journal of combinatorics, Tome 28 (2021) no. 3. doi: 10.37236/9046

Cité par Sources :