Remote Access Journal of the American Mathematical Society
Green Open Access

Journal of the American Mathematical Society

ISSN 1088-6834(online) ISSN 0894-0347(print)



Linear decision trees, subspace arrangements and Möbius functions

Authors: Anders Björner and László Lovász
Journal: J. Amer. Math. Soc. 7 (1994), 677-706
MSC: Primary 52B55; Secondary 05C05, 06A09, 57M99, 68Q25
MathSciNet review: 1243770
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Topological methods are described for estimating the size and depth of decision trees where a linear test is performed at each node. The methods are applied, among others, to the questions of deciding by a linear decision tree whether given $ n$ real numbers (1) some $ k$ of them are equal, or (2) some $ k$ of them are unequal. We show that the minimum depth of a linear decision tree for these problems is at least (1) $ {\text{max}}\{ n - 1,\quad n\;{\text{lo}}{{\text{g}}_3}(n/3k)\} $, and (2) $ {\text{max}}\{ n - 1,\quad n\;{\text{lo}}{{\text{g}}_3}(k - 1) - k + 1\} $.

Our main lower bound for the size of linear decision trees for polyhedra $ P$ in $ {{\mathbf{R}}^n}$ is given by the sum of Betti numbers for the complement $ {{\mathbf{R}}^n}\backslash P$. The applications of this general topological bound involve the computation of the Möbius function of intersection lattices of certain subspace arrangements. In particular, this leads to computing various expressions for the Möbius function of posets of partitions with restricted block sizes. Some of these formulas have topological meaning. For instance, we derive a formula for the Euler characteristic of the subset of $ {{\mathbf{R}}^n}$ of points with no $ k$ coordinates equal in terms of the roots of the truncated exponential $ \sum\nolimits_{i < k} {{x^i}} /i!$.

References [Enhancements On Off] (What's this?)

  • [BO] M. Ben-Or, Lower bounds for algebraic computation trees, Proc. 15th Annual ACM Sympos. on Theory of Computing, ACM Press, New York, 1983, pp. 80-86.
  • [B1] A. Björner, Topological methods, Handbook of Combinatorics (R. Graham, M. Grötschel, and L. Lovász, eds.), North-Holland, Amsterdam, 1994.
  • [B2] -, Subspace arrangements, Proc. 1st European Congress Math. (Paris, 1992) (A. Joseph and R. Rentschler, eds.), Birkhäuser, Basel-Boston, 1994.
  • [BK] A. Björner and G. Kalai, An extended Euler-Poincaré theorem, Acta Math. 161 (1988), 279-303. MR 971798 (89m:52009)
  • [BLVŽ] A. Björner, L. Lovász, S. Vrećica, and R. Živaljević, Chessboard complexes and matching complexes, J. London Math. Soc. (to appear).
  • [BLY] A. Björner, L. Lovász, and A. C.-C. Yao, Linear decision trees: volume estimates and topological bounds, Proc. 24th Annual ACM Sympos. on Theory of Computing, ACM Press, New York, 1992, pp. 170-177.
  • [BW] A. Björner and V. Welker, The homology of ``$ k$-equal'' manifolds and related partition lattices, Adv. in Math. (to appear).
  • [CHR] A. R. Calderbank, P. Hanlon, and R. W. Robinson, Partitions into even and odd block size and some unusual characters of the symmetric groups, Proc. London Math. Soc. (3) 53 (1986), 288-320. MR 850222 (87m:20042)
  • [DL] D. Dobkin and R. Lipton, On the complexity of computations under varying sets of primitives, Automata Theory and Formal Languages (H. Bradhage, ed.), Lecture Notes in Comput. Sci., vol. 33, Springer-Verlag, New York and Berlin, 1975, pp. 110-117. MR 0405920 (53:9712)
  • [GM] M. Goresky and R. MacPherson, Stratified Morse theory, Ergeb. Math. Grenzgeb. (3), Band 14, Springer-Verlag, Berlin, 1988. MR 932724 (90d:57039)
  • [MH] F. Meyer auf der Heide, A polynomial linear search algorithm for the $ n$-dimensional knapsack problem, J. Assoc. Comput. Mach. 31 (1984), 668-676.. MR 819161
  • [Mi] J. Milnor, On the Betti numbers of real algebraic varieties, Proc. Amer. Math. Soc. 15 (1964), 275-280. MR 0161339 (28:4547)
  • [Mu] J. R. Munkres, Elements of algebraic topology, Addison-Wesley, Menlo Park, 1984. MR 755006 (85m:55001)
  • [O] O. A. Oleinik, Estimates of the Betti numbers of real algebraic hypersurfaces, Math. Sb. 28 (1951), 635-640. MR 0044864 (13:489b)
  • [OP] O. A. Oleinik and I. B. Petrovsky, On the topology of real algebraic surfaces, Izv. Akad. Nauk SSSR 13 (1949), 389-402; English transl., Amer. Math. Soc. Transl. Ser. 1, vol. 7, Amer. Math. Soc., Providence, RI, 1962, pp. 399-417. MR 0034600 (11:613h)
  • [R] E. M. Reingold, Computing the maxima and the median, Proc. 12th IEEE Annual Sympos. on Switching and Automata Theory, IEEE, Piscataway, NJ, 1971, pp. 216-218.
  • [S1] R. P. Stanley, Binomial posets, Möbius inversion and permutation enumeration, J. Combin. Theory Ser. A 20 (1976), 336-356. MR 0409206 (53:12968)
  • [S2] -, Exponential structures, Stud. Appl. Math. 59 (1978), 73-82. MR 0480063 (58:262)
  • [S3] -, Enumerative combinatorics, Vol. 1, Wadsworth & Brooks/ Cole, Monterey, CA, 1986.
  • [SY] M. Steele and A. Yao, Lower bounds for algebraic decision trees, J. Algorithms 3 (1982), 1-8. MR 646886 (83i:68076)
  • [Sz] G. Szegö, Über eine Eigenschaft der Exponentialreihe, Sitzungsber. Berlin Math. Gesellschaft 23 (1924), 50-64.
  • [Th] R. Thom, Sur l'homologie des variétés algébriques réelles, Differential and Algebraic Topology (S. S. Cairns, ed.), Princeton Univ. Press, Princeton, NJ, 1965. MR 0200942 (34:828)
  • [Tu] P. Turán, Eine neue Methode in der Analysis und deren Anwendungen, Akad. Kiadó, Budapest, 1953. MR 0060548 (15:688b)
  • [V] R. S. Varga, Scientific computation on mathematical problems and conjectures, CBMS-NSF Regional Conf. Ser. in Appl. Math., vol. 60, SIAM, Philadelphia, PA, 1990. MR 1068317 (92b:65012)
  • [Y] A. C.-C. Yao, Algebraic decision trees and Euler characteristics, Proc. 33rd Annual IEEE Sympos on Foundations of Computer Science, October 1992, pp. 268-277.
  • [ZŽ] G. M. Ziegler and R. T. Živaljević, Homotopy types of arrangements via diagrams of spaces, Math. Ann. 295 (1993), 527-548. MR 1204836 (94c:55018)

Similar Articles

Retrieve articles in Journal of the American Mathematical Society with MSC: 52B55, 05C05, 06A09, 57M99, 68Q25

Retrieve articles in all journals with MSC: 52B55, 05C05, 06A09, 57M99, 68Q25

Additional Information

Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society