Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Semimodular functions and combinatorial geometries

Author: Hien Quang Nguyen
Journal: Trans. Amer. Math. Soc. 238 (1978), 355-383
MSC: Primary 05B35
MathSciNet review: 0491269
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A point-lattice $ \mathfrak{L}$ being given, to any normalized, nondecreasing, integer-valued, semimodular function f defined on $ \mathfrak{L}$, we can associate a class of combinatorial geometries called expansions of f. The family of expansions of f is shown to have a largest element for the weak map order, $ E(f)$, the free expansion of f. Expansions generalize and clarify the relationship between two known constructions, one defined by R. P. Dilworth, the other by J. Edmonds and G.-C. Rota.

Further applications are developed for solving two extremal problems of semimodular functions: characterizing

(1) extremal rays of the convex cone of real-valued, nondecreasing, semimodular functions defined on a finite set;

(2) combinatorial geometries which are extremal for the decomposition into a sum.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05B35

Retrieve articles in all journals with MSC: 05B35

Additional Information

Article copyright: © Copyright 1978 American Mathematical Society