Rank axiom of modular supermatroids: a connection with directional DR submodular functions

DOI10.1016/J.AAM.2021.102304zbMATH Open1480.05027arXiv2009.00200OpenAlexW3082809647WikidataQ114016455 ScholiaQ114016455MaRDI QIDQ2070084FDOQ2070084

Takanori Maehara, So Nakashima

Publication date: 21 January 2022

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: A matroid has been one of the most important combinatorial structures since it was introduced by Whitney as an abstraction of linear independence. As an important property of a matroid, it can be characterized by several different (but equivalent) axioms, such as the augmentation, the base exchange, or the rank axiom. A supermatroid is a generalization of a matroid defined on lattices. Here, the central question is whether a supermatroid can be characterized by several equivalent axioms similar to a matroid. Barnabei, Nicoletti, and Pezzoli characterized supermatroids on distributive lattices, and Fujishige, Koshevoy, and Sano generalized the results for cg-matroids (supermatroids on lower locally distributive lattices). In this study, we focus on modular lattices, which are an important superclass of distributive lattices, and provide equivalent characterizations of supermatroids on modular lattices. We characterize supermatroids on modular lattices using the rank axiom in which the rank function is a directional DR-submodular function, which is a generalization of a submodular function introduced by the authors. Using a characterization based on rank functions, we further prove the strong exchange property of a supermatroid, which has application in optimization. We also reveal the relation between the axioms of a supermatroid on lower semimodular lattices, which is a common superclass of a lower locally distributive lattice and a modular lattice.

Full work available at URL: https://arxiv.org/abs/2009.00200

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Matroids on partially ordered sets
• Valuated matroids
• Meet-distributive lattices and the anti-exchange closure
• On the Abstract Properties of Linear Dependence
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• A geometric description of modular lattices
• Matroids on convex geometries (cg-matroids)
• Rank functions of strict cg-matroids
• Global rank axioms for poset matroids
• Base axioms of modular supermatroids
• Maximizing monotone submodular functions over the integer lattice
• Submodular Function Maximization on the Bounded Integer Lattice
• Weakly submodular rank functions, supermatroids, and the flat lattice of a distributive super\-matroid

Cited In (1)

• Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice -- continuous greedy algorithm on median complex --

This page was built for publication: Rank axiom of modular supermatroids: a connection with directional DR submodular functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2070084)