Phylogenetic diversity and the maximum coverage problem

For a weighted hypergraph (H,ω)(H,ω), with vertex set XX, edge set EE, and weighting ω:E→R≥0ω:E→R≥0, the maximum coverage problem is to find a kk-element subset Y⊆XY⊆X that maximizes the total weight of those edges that have non-empty intersection with YY among all kk-element subsets of XX. Such a subset YY is called optimal. Recently, within the field of phylogenetics it has been shown that for certain weighted hypergraphs coming from phylogenetic trees the collection of optimal subsets of XX forms a so-called strong greedoid. We call hypergraphs having this latter property strongly greedy  . In this note we characterize the rr-uniform hypergraphs HH with unit edge weights that are strongly greedy in the case where rr is a prime number.