Majorization, packing, covering and matroids (Q1309465)

Two partial ordering relations on the set \(S\) of all nonincreasing sequences of positive integers are studied: lower weak majorization and upper weak majorization. It is shown that the set \(S\) is a lattice under each of these relations. The main result of the paper states that (under some assumptions) the sets of sequences in \(S\) that give cardinalities of sets forming packings, coverings and partitions are order ideals (or filters) in these lattices. Consequently, these sets can be characterized by specifying maximal (minimal) elements in the appropriate ideals (filters). The results apply to matroids (packing, coverings and partitioning with independent sets). Some other applications for hypergraph and graph problems are also mentioned.