Séminaire Lotharingien de Combinatoire, 84B.47 (2020), 12 pp.
Darij Grinberg and Fedor Petrov
The Bhargava Greedoid
Abstract.
The greedoids (as defined in 1981 by Korte and Lóvász)
are a class of set systems similar to the matroids (but more permissive).
Inspired by Bhargava's generalized factorials, we
introduce a greedoid of maximum-perimeter subsets in a finite ultrametric
space (actually, in a somewhat more general setting than that). We prove that
it is a Gaussian elimination greedoid over any sufficiently large
(e.g., infinite) field; this is a greedoid analogue of a representable
matroid. We establish further properties of this greedoid, generalizing two
facts shown by Bhargava. We also briefly discuss its relation to a greedoid
appearing in phylogenetics, as well as a multiset analogue.
Received: November 20, 2019.
Accepted: February 20, 2020.
Final version: April 30, 2020.
The following versions are available: