COUNTING COLORFUL MULTIDIMENSIONAL TREES

被引:20
作者
ADIN, RM [1 ]
机构
[1] HEBREW UNIV JERUSALEM,INST MATH,JERUSALEM,ISRAEL
关键词
AMS subject classification code (1991): 05C50; 05C05; 05C30; 05C65; 15A18;
D O I
10.1007/BF01285814
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let V be a disjoint union of r finite sets V1,...,V(tau) ("colors"). A collection T of subsets of V is colorful if each member if T contains at most one point of each color. A k-dimensional colorful tree is a colorful collection T of subsets of V, each of size k + 1, such that if we add to T all the colorful subsets of V of size k or less, we get a Q-acyclic simplicial complex DELTA(T). We count (using the Binet-Cauchy theorem) the k-dimensional colorful trees on V (for all k), where each tree T is counted with weight \H(k-1)BAR(DELTA(T)\2 (H* = reduced homology). The result confirms, in a way, a formula suggested by Bolker (for k = r - 1). It extends, on one hand, a result of Kalai on weighted counting of k-dimensional trees and, on the other hand, enumeration formulas for multi-partite (1-dimensional) trees. All these results are extensions of Cayley's celebrated tree-counting formula, now 100 years old.
引用
收藏
页码:247 / 260
页数:14
相关论文
共 9 条
[1]  
Austin T. L., 1960, CAN J MATH, V12, P535, DOI [10.4153/cjm-1960-047-1, DOI 10.4153/CJM-1960-047-1]
[2]   SIMPLICIAL GEOMETRY AND TRANSPORTATION POLYTOPES [J].
BOLKER, ED .
TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1976, 217 (MAR) :121-142
[3]  
Cayley Arthur, 1889, Q J PURE APPL MATH, V23, P376, DOI [10.1017/cbo9780511703799.010, DOI 10.1017/CBO9780511703799]
[4]  
Fiedler M., 1958, CASOPIS PEST MAT, V83, P214, DOI 10.21136/cpm.1958.108301
[5]  
Gantmacher F.R., 1960, THEORY MATRICES
[6]   ENUMERATION OF Q-ACYCLIC SIMPLICIAL COMPLEXES [J].
KALAI, G .
ISRAEL JOURNAL OF MATHEMATICS, 1983, 45 (04) :337-351
[7]  
MOON JW, 1970, CANADIAN MATH C
[8]  
Munkres J.R.., 2007, TOPOLOGY
[9]  
Spanier E. H., 1966, ALGEBRAIC TOPOLOGY, DOI 10.1007/978-1-4684-9322-1