Geodesic
Linear decision trees, subspace arrangements and Möbius functions
Journal of the American Mathematical Society, Tome 07 (1994) no. 3, pp. 677-706 Cet article a éte moissonné depuis la source American Mathematical Society

Voir la notice de l'article

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!$. 
@article{10_1090_S0894_0347_1994_1243770_0,
     author = {Bj\"orner, Anders and Lov\'asz, L\'aszl\'o},
     title = {Linear decision trees, subspace arrangements and {M\"obius} functions},
     journal = {Journal of the American Mathematical Society},
     pages = {677--706},
     year = {1994},
     volume = {07},
     number = {3},
     doi = {10.1090/S0894-0347-1994-1243770-0},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1994-1243770-0/}
}
TY  - JOUR
AU  - Björner, Anders
AU  - Lovász, László
TI  - Linear decision trees, subspace arrangements and Möbius functions
JO  - Journal of the American Mathematical Society
PY  - 1994
SP  - 677
EP  - 706
VL  - 07
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1994-1243770-0/
DO  - 10.1090/S0894-0347-1994-1243770-0
ID  - 10_1090_S0894_0347_1994_1243770_0
ER  - 
%0 Journal Article
%A Björner, Anders
%A Lovász, László
%T Linear decision trees, subspace arrangements and Möbius functions
%J Journal of the American Mathematical Society
%D 1994
%P 677-706
%V 07
%N 3
%U http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-1994-1243770-0/
%R 10.1090/S0894-0347-1994-1243770-0
%F 10_1090_S0894_0347_1994_1243770_0
Björner, Anders; Lovász, László. Linear decision trees, subspace arrangements and Möbius functions. Journal of the American Mathematical Society, Tome 07 (1994) no. 3, pp. 677-706. doi: 10.1090/S0894-0347-1994-1243770-0

[1] Björner, Anders, Kalai, Gil An extended Euler-Poincaré theorem Acta Math. 1988 279 303

[2] Calderbank, A. R., Hanlon, P., Robinson, R. W. Partitions into even and odd block size and some unusual characters of the symmetric groups Proc. London Math. Soc. (3) 1986 288 320

[3] Dobkin, David P., Lipton, Richard J. On the complexity of computations under varying sets of primitives 1975 110 117

[4] Goresky, Mark, Macpherson, Robert Stratified Morse theory 1988

[5] Meyer Auf Der Heide, Friedhelm A polynomial linear search algorithm for the 𝑛-dimensional knapsack problem J. Assoc. Comput. Mach. 1984 668 676

[6] Milnor, J. On the Betti numbers of real varieties Proc. Amer. Math. Soc. 1964 275 280

[7] Munkres, James R. Elements of algebraic topology 1984

[8] Oleĭnik, O. A. Estimates of the Betti numbers of real algebraic hypersurfaces Mat. Sbornik N.S. 1951 635 640

[9] Petrovskiĭ, I. G., Oleĭnik, O. A. On the topology of real algebraic surfaces Izv. Akad. Nauk SSSR Ser. Mat. 1949 389 402

[10] Stanley, Richard P. Binomial posets, Möbius inversion, and permutation enumeration J. Combinatorial Theory Ser. A 1976 336 356

[11] Stanley, Richard P. Exponential structures Stud. Appl. Math. 1978 73 82

[12] Steele, J. Michael, Yao, Andrew C. Lower bounds for algebraic decision trees J. Algorithms 1982 1 8

[13] Thom, René Sur l’homologie des variétés algébriques réelles 1965 255 265

[14] Turán, Paul Eine neue Methode in der Analysis und deren Anwendungen 1953 196

[15] Varga, Richard S. Scientific computation on mathematical problems and conjectures 1990

[16] Ziegler, Günter M., Živaljević, Rade T. Homotopy types of subspace arrangements via diagrams of spaces Math. Ann. 1993 527 548

Cité par Sources :