Simplicial geometry and transportation polytopes

Bolker, Ethan D.

doi:10.1090/S0002-9947-1976-0411983-9

Simplicial geometry and transportation polytopes
HTML articles powered by AMS MathViewer

by Ethan D. Bolker PDF

Trans. Amer. Math. Soc. 217 (1976), 121-142 Request permission

Abstract:

The classical transportation problem is the study of the set of nonnegative matrices with prescribed nonnegative row and column sums. It is aesthetically satisfying and perhaps potentially useful to study more general higher dimensional rectangular arrays whose sums on some subarrays are specified. We show how such problems can be rewritten as problems in homology theory. That translation explains the appearance of bipartite graphs in the study of the classical transportation problem. In our generalization, higher dimensional cell complexes occur. That is why the general problem requires a substantial independent investigation of simplicial geometry, the name given to the class of theorems on the geometry of a cell complex which depend on a particular cellular decomposition. The topological invariants of the complex are means, not ends. Thus simplicial geometry attempts to do for complexes what graph theory does for graphs. The dual title of this paper indicates that we shall spend as much time studying simplicial geometry for its own sake as applying the results to transportation problems. Our results include formulas for inverting the boundary operator of an acyclic cell complex, and some information on the number of such subcomplexes of a given complex.

References

Ethan D. Bolker, Transportation polytopes, J. Combinatorial Theory Ser. B 13 (1972), 251–262. MR 311297, DOI 10.1016/0095-8956(72)90060-3

Counting trees in simplicial complexes

21

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
W. B. Jurkat and H. J. Ryser, Extremal configurations and decomposition theorems. I, J. Algebra 8 (1968), 194–222. MR 220615, DOI 10.1016/0021-8693(68)90045-8
Victor Klee and Christoph Witzgall, Facets and vertices of transportation polytopes, Mathematics of the Decision Sciences, Part 1 (Seminar, Stanford, Calif., 1967) Amer. Math. Soc., Providence, R.I., 1968, pp. 257–282. MR 0235832
Albert T. Lundell, A Bott map for non-stable homotopy of the unitary group, Topology 8 (1969), 209–217. MR 238319, DOI 10.1016/0040-9383(69)90011-1
Edwin H. Spanier, Algebraic topology, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1966. MR 0210112
E. C. Zeeman, On the dunce hat, Topology 2 (1964), 341–358. MR 156351, DOI 10.1016/0040-9383(63)90014-4
H. Bruggesser and P. Mani, Shellable decompositions of cells and spheres, Math. Scand. 29 (1971), 197–205 (1972). MR 328944, DOI 10.7146/math.scand.a-11045