Skip to Main Content

Journal of the American Mathematical Society

Published by the American Mathematical Society, the Journal of the American Mathematical Society (JAMS) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Journal of the American Mathematical Society is 4.79.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Linear decision trees, subspace arrangements and Möbius functions
HTML articles powered by AMS MathViewer

by Anders Björner and László Lovász PDF
J. Amer. Math. Soc. 7 (1994), 677-706 Request permission

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
    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. A. Björner, Topological methods, Handbook of Combinatorics (R. Graham, M. Grötschel, and L. Lovász, eds.), North-Holland, Amsterdam, 1994. —, Subspace arrangements, Proc. 1st European Congress Math. (Paris, 1992) (A. Joseph and R. Rentschler, eds.), Birkhäuser, Basel-Boston, 1994.
  • Anders Björner and Gil Kalai, An extended Euler-Poincaré theorem, Acta Math. 161 (1988), no. 3-4, 279–303. MR 971798, DOI 10.1007/BF02392300
  • A. Björner, L. Lovász, S. Vrećica, and R. Živaljević, Chessboard complexes and matching complexes, J. London Math. Soc. (to appear). 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. A. Björner and V. Welker, The homology of “$k$-equal” manifolds and related partition lattices, Adv. in Math. (to appear).
  • 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), no. 2, 288–320. MR 850222, DOI 10.1112/plms/s3-53.2.288
  • David P. Dobkin and Richard J. Lipton, On the complexity of computations under varying sets of primitives, Automata theory and formal languages (Second GI Conf., Kaiserslautern, 1975), Lecture Notes in Comput. Sci., Vol. 33, Springer, Berlin, 1975, pp. 110–117. MR 0405920
  • Mark Goresky and Robert MacPherson, Stratified Morse theory, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 14, Springer-Verlag, Berlin, 1988. MR 932724, DOI 10.1007/978-3-642-71714-7
  • Friedhelm Meyer auf der Heide, A polynomial linear search algorithm for the $n$-dimensional knapsack problem, J. Assoc. Comput. Mach. 31 (1984), no. 3, 668–676. MR 819161, DOI 10.1145/828.322450
  • J. Milnor, On the Betti numbers of real varieties, Proc. Amer. Math. Soc. 15 (1964), 275–280. MR 161339, DOI 10.1090/S0002-9939-1964-0161339-9
  • James R. Munkres, Elements of algebraic topology, Addison-Wesley Publishing Company, Menlo Park, CA, 1984. MR 755006
  • O. A. Oleĭnik, Estimates of the Betti numbers of real algebraic hypersurfaces, Mat. Sbornik N.S. 28(70) (1951), 635–640 (Russian). MR 0044864
  • I. G. Petrovskiĭ and O. A. Oleĭnik, On the topology of real algebraic surfaces, Izvestiya Akad. Nauk SSSR. Ser. Mat. 13 (1949), 389–402 (Russian). MR 0034600
  • 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.
  • Richard P. Stanley, Binomial posets, Möbius inversion, and permutation enumeration, J. Combinatorial Theory Ser. A 20 (1976), no. 3, 336–356. MR 409206, DOI 10.1016/0097-3165(76)90028-5
  • Richard P. Stanley, Exponential structures, Stud. Appl. Math. 59 (1978), no. 1, 73–82. MR 0480063, DOI 10.1002/sapm197859173
  • —, Enumerative combinatorics, Vol. 1, Wadsworth & Brooks/ Cole, Monterey, CA, 1986.
  • J. Michael Steele and Andrew C. Yao, Lower bounds for algebraic decision trees, J. Algorithms 3 (1982), no. 1, 1–8. MR 646886, DOI 10.1016/0196-6774(82)90002-5
  • G. Szegö, Über eine Eigenschaft der Exponentialreihe, Sitzungsber. Berlin Math. Gesellschaft 23 (1924), 50-64.
  • René Thom, Sur l’homologie des variétés algébriques réelles, Differential and Combinatorial Topology (A Symposium in Honor of Marston Morse), Princeton Univ. Press, Princeton, N.J., 1965, pp. 255–265 (French). MR 0200942
  • Paul Turán, Eine neue Methode in der Analysis und deren Anwendungen, Akadémiai Kiadó, Budapest, 1953 (German). MR 0060548
  • Richard S. Varga, Scientific computation on mathematical problems and conjectures, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 60, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1990. MR 1068317, DOI 10.1137/1.9781611970111
  • 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.
  • Günter M. Ziegler and Rade T. Živaljević, Homotopy types of subspace arrangements via diagrams of spaces, Math. Ann. 295 (1993), no. 3, 527–548. MR 1204836, DOI 10.1007/BF01444901
Similar Articles
Additional Information
  • © Copyright 1994 American Mathematical Society
  • Journal: J. Amer. Math. Soc. 7 (1994), 677-706
  • MSC: Primary 52B55; Secondary 05C05, 06A09, 57M99, 68Q25
  • DOI: https://doi.org/10.1090/S0894-0347-1994-1243770-0
  • MathSciNet review: 1243770