Semimodular functions and combinatorial geometries

Nguyen, Hien Quang

doi:10.1090/S0002-9947-1978-0491269-9

Semimodular functions and combinatorial geometries
HTML articles powered by AMS MathViewer

by Hien Quang Nguyen PDF

Trans. Amer. Math. Soc. 238 (1978), 355-383 Request permission

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

Thomas H. Brylawski, A decomposition for combinatorial geometries, Trans. Amer. Math. Soc. 171 (1972), 235–282. MR 309764, DOI 10.1090/S0002-9947-1972-0309764-6
Tom Brylawski, Modular constructions for combinatorial geometries, Trans. Amer. Math. Soc. 203 (1975), 1–44. MR 357163, DOI 10.1090/S0002-9947-1975-0357163-6
Thomas H. Brylawski, An affine representation for transversal geometries, Studies in Appl. Math. 54 (1975), no. 2, 143–160. MR 462992, DOI 10.1002/sapm1975542143
Gustave Choquet, Theory of capacities, Ann. Inst. Fourier (Grenoble) 5 (1953/54), 131–295 (1955). MR 80760, DOI 10.5802/aif.53

Algebraic theory of lattices

Henry H. Crapo, Single-element extensions of matroids, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 55–65. MR 190045, DOI 10.6028/jres.069B.003
Henry H. Crapo, Erecting geometries, Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and its Applications (Univ. North Carolina, Chapel Hill, N.C., 1970) Univ. North Carolina, Chapel Hill, N.C., 1970, pp. 74–99. MR 0272655
Henry H. Crapo and Gian-Carlo Rota, On the foundations of combinatorial theory: Combinatorial geometries, Preliminary edition, The M.I.T. Press, Cambridge, Mass.-London, 1970. MR 0290980
Thomas A. Dowling and Douglas G. Kelly, Elementary strong maps between combinatorial geometries, Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973) Atti dei Convegni Lincei, No. 17, Accad. Naz. Lincei, Rome, 1976, pp. 121–152 (English, with Italian summary). MR 0543658
Jack Edmonds, Matroid partition, Mathematics of the Decision Sciences, Part 1 (Seminar, Stanford, Calif., 1967) Amer. Math. Soc., Providence, R.I., 1968, pp. 335–345. MR 0237366
Jack Edmonds, Submodular functions, matroids, and certain polyhedra, Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) Gordon and Breach, New York, 1970, pp. 69–87. MR 0270945

Submodular set functions

A lattice order on the set of all matroids on a set

9

D. A. Higgs, Maps of geometries, J. London Math. Soc. 41 (1966), 612–618. MR 202034, DOI 10.1112/jlms/s1-41.1.612
D. A. Higgs, Strong maps of geometries, J. Combinatorial Theory 5 (1968), 185–191. MR 231761, DOI 10.1016/S0021-9800(68)80054-7
J. S. Pym and Hazel Perfect, Submodular functions and independence structures, J. Math. Anal. Appl. 30 (1970), 1–31. MR 263668, DOI 10.1016/0022-247X(70)90180-0
J. Rosenmüller and H. G. Weidner, A class of extreme convex set functions with finite carrier, Advances in Math. 10 (1973), 1–38. MR 321553, DOI 10.1016/0001-8708(73)90095-9
Lloyd S. Shapley, Cores of convex games, Internat. J. Game Theory 1 (1971/72), 11–26; errata, ibid. 1 (1971/72), 199. MR 311338, DOI 10.1007/BF01753431
W. T. Tutte, Lectures on matroids, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 1–47. MR 179781, DOI 10.6028/jres.069B.001
D. J. A. Welsh, On matroid theorems of Edmonds and Rado, J. London Math. Soc. (2) 2 (1970), 251–256. MR 258663, DOI 10.1112/jlms/s2-2.2.251
D. J. A. Welsh, Related classes of set functions, Studies in pure mathematics (presented to Richard Rado), Academic Press, London, 1971, pp. 261–269. MR 0304213
Hassler Whitney, On the Abstract Properties of Linear Dependence, Amer. J. Math. 57 (1935), no. 3, 509–533. MR 1507091, DOI 10.2307/2371182