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
DOI: https://doi.org/10.1090/S0002-9947-1978-0491269-9
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?)

  • [1] T. H. Brylawski, A decomposition for combinatorial geometries, Trans. Amer. Math. Soc. 171 (1972), 235-282. MR 46 #8869. MR 0309764 (46:8869)
  • [2] -, Modular constructions for combinatorial geometries, Trans. Amer. Math. Soc. 203 (1975), 1-44. MR 50 #9631. MR 0357163 (50:9631)
  • [3] -, An affine representation for transversal geometries, SIAM 54 (1975), 143-160. MR 0462992 (57:2956)
  • [4] G. Choquet, Theory of capacities, Ann. Inst. Fourier (Grenoble) 5 (1953-1954), 131-295 (1955). MR 18, 295. MR 0080760 (18:295g)
  • [5] P. Crawley and R. P. Dilworth, Algebraic theory of lattices, Prentice-Hall, Englewood Cliffs, N.J., 1973.
  • [6] H. H. Crapo, Single-element extensions of matroids, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 55-65. MR 32 #7461. MR 0190045 (32:7461)
  • [7] -, Erecting geometries, Proc. 2nd Chapel Hill Conf. on Combinatorial Mathematics and its Applications, Dept. Statist., Univ. North Carolina, Chapel Hill, N.C., 1970, pp. 74-99. MR 42 #7536. MR 0272655 (42:7536)
  • [8] H. H. Crapo and G.-C. Rota, On the foundations of combinatorial theory: Combinatorial geometries, MIT Press, Cambridge, Mass., 1970. MR 45 #74. MR 0290980 (45:74)
  • [9] T. A. Dowling and D. G. Kelly, Elementary strong maps between combinatorial geometries, University of North Carolina, Chapel Hill, N.C. (preprint). MR 0543658 (58:27567)
  • [10] J. Edmonds, Matroid partition, Mathematics of the Decision Sciences, Part I, Lectures in Appl. Math., vol. 11, Amer. Math. Soc., Providence, R.I., 1968, pp. 335-345. MR 38 #5654. MR 0237366 (38:5654)
  • [11] -, Submodular functions, matroids, and certain polyhedra, Combinatorial Structures and their Applications, Gordon and Breach, New York, 1970, pp. 69-87. MR 42 #5828. MR 0270945 (42:5828)
  • [12] J. Edmonds and G.-C. Rota, Submodular set functions (Abstract, Waterloo Combinatorics Conf.), Univ. of Waterloo, Ontario, 1966.
  • [13] D. A. Higgs, A lattice order on the set of all matroids on a set, Canad. Math. Bull. 9 (1966), 684-685.
  • [14] -, Maps of geometries, J. London Math. Soc. 41 (1966), 612-618. MR 34 #1910. MR 0202034 (34:1910)
  • [15] -, Strong maps of geometries, J. Combinatorial Theory 5 (1968), 185-191. MR 38 #89. MR 0231761 (38:89)
  • [16] J. S. Pym and H. Perfect, Submodular functions and independence structures, J. Math. Anal. Appl. 30 (1970), 1-31. MR 41 #8269. MR 0263668 (41:8269)
  • [17] 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 47 #10086. MR 0321553 (47:10086)
  • [18] L. S. Shapley, Cores of convex games, Rand Corp., RM-4571-PR, 1965; RM-P-4620, 1971. MR 0311338 (46:10430)
  • [19] W. T. Tutte, Lectures on matroids, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 1-47. MR 31 #4023. MR 0179781 (31:4023)
  • [20] D. J. A. Welsh, On matroid theorems of Edmonds and Rodo, J. London Math. Soc. (2) 2 (1970), 251-256. MR 41 #3309. MR 0258663 (41:3309)
  • [21] -, Related classes of set functions, Studies in Pure Math., Academic Press, London, 1971. MR 46 #3348. MR 0304213 (46:3348)
  • [22] H. Whitney, On the abstract properties of linear dependence, Amer. J. Math. 57 (1935), 509-533. MR 1507091

Similar Articles

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

Retrieve articles in all journals with MSC: 05B35


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1978-0491269-9
Article copyright: © Copyright 1978 American Mathematical Society

American Mathematical Society