Simplicial geometry and transportation polytopes
Author:
Ethan D. Bolker
Journal:
Trans. Amer. Math. Soc. 217 (1976), 121142
MSC:
Primary 05B25; Secondary 57C05
MathSciNet review:
0411983
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
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.
 [1]
Ethan
D. Bolker, Transportation polytopes, J. Combinatorial Theory
Ser. B. 13 (1972), 251–262. MR 0311297
(46 #10389)
 [2]
, Counting trees in simplicial complexes, Notices Amer. Math. Soc. 21 (1974), A32. Abstract #7110512.
 [3]
Henry
H. Crapo and GianCarlo
Rota, On the foundations of combinatorial theory: Combinatorial
geometries, Preliminary edition, The M.I.T. Press, Cambridge,
Mass.London, 1970. MR 0290980
(45 #74)
 [4]
W.
B. Jurkat and H.
J. Ryser, Extremal configurations and decomposition theorems.
I, J. Algebra 8 (1968), 194–222. MR 0220615
(36 #3667)
 [5]
Victor
Klee and Christoph
Witzgall, Facets and vertices of transportation polytopes,
Mathematics of the Decision Sciences, Part I (Seminar, Stanford, Calif.,
1967) Amer. Math. Soc., Providence, R.I., 1968, pp. 257–282.
MR
0235832 (38 #4134)
 [6]
Albert
T. Lundell, A Bott map for nonstable homotopy of the unitary
group, Topology 8 (1969), 209–217. MR 0238319
(38 #6595)
 [7]
Edwin
H. Spanier, Algebraic topology, McGrawHill Book Co., New
YorkToronto, Ont.London, 1966. MR 0210112
(35 #1007)
 [8]
E.
C. Zeeman, On the dunce hat, Topology 2
(1964), 341–358. MR 0156351
(27 #6275)
 [9]
H.
Bruggesser and P.
Mani, Shellable decompositions of cells and spheres, Math.
Scand. 29 (1971), 197–205 (1972). MR 0328944
(48 #7286)
 [1]
 E. D. Bolker, Transportation polytopes, J. Combinatorial Theory, 13 (1972), 251262. MR 0311297 (46:10389)
 [2]
 , Counting trees in simplicial complexes, Notices Amer. Math. Soc. 21 (1974), A32. Abstract #7110512.
 [3]
 H. Crapo and G. C. Rota, On the foundations of combinatorial theory: Combinatorial geometries, Preliminary edition, M.I.T. Press, Cambridge, Mass., 1970. MR 45 #74. MR 0290980 (45:74)
 [4]
 W. B. Jurkat and H. J. Ryser, Extremal configurations and decomposition theorems, J. Algebra 8 (1968), 194222. MR 36 #3667. MR 0220615 (36:3667)
 [5]
 V. Klee and C. Witzgall, Facets and vertices of transportation polytopes, Lectures in Appl. Math., vol. 11, Amer. Math. Soc., Providence, R. I., 1968, pp. 257282. MR 38 #4134. MR 0235832 (38:4134)
 [6]
 A. T. Lundell and S. Weingram, The topology of CW complexes, Van Nostrand Reinhold, New York, 1969. MR 0238319 (38:6595)
 [7]
 E. H. Spanier, Algebraic topology, McGrawHill, New York, 1966. MR 35 #1007. MR 0210112 (35:1007)
 [8]
 E. C. Zeeman, On the dunce hat, Topology 2 (1963), 341358. MR 27 #6275. MR 0156351 (27:6275)
 [9]
 H. Bruggesser and P. Mani, Shellable decompositions of cells and spheres, Math. Scand. 29 (1971), 197205. MR 48 #7286. MR 0328944 (48:7286)
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC:
05B25,
57C05
Retrieve articles in all journals
with MSC:
05B25,
57C05
Additional Information
DOI:
http://dx.doi.org/10.1090/S00029947197604119839
PII:
S 00029947(1976)04119839
Keywords:
Simplicial geometry,
transportation polytope,
combinatorial geometry,
matroid,
tree,
homology of finite complex
Article copyright:
© Copyright 1976
American Mathematical Society
