Anders Björner

TCS Journal 2006 Journal Article

Rationality of the Möbius function of a composition poset

• Anders Björner
• Bruce E. Sagan

We consider the zeta and Möbius functions of a partial order on integer compositions first studied by Bergeron, Bousquet-Mélou, and Dulucq. The Möbius function of this poset was determined by Sagan and Vatter. We prove rationality of various formal power series in noncommuting variables whose coefficients are evaluations of the zeta function, ζ, and the Möbius function, μ. The proofs are either directly from the definitions or by constructing finite-state automata. We also obtain explicit expressions for generating functions obtained by specializing the variables to commutative ones. We reprove Sagan and Vatter's formula for μ using this machinery. These results are closely related to those of Björner and Reutenauer about subword order, and we discuss a common generalization.

TCS Journal 1993 Journal Article

The Möbius function of factor order

• Anders Björner

Intervals in the factor ordering of a free monoid are investigated. It was shown by Farmer (1982) that such intervals (β, α) are contractible or homotopy spheres in case β is the empty word. We observe here that the same is true in general. This implies that the Möbius function of factor order takes values in {0, + 1, −1}. A recursive rule for this Möbius function is given, which allows efficient computation via the Knuth—Morris—Pratt algorithm. The Möbius function of subword order was studied in Björner (1990). We give here a simpler proof (a parity-changing involution) for its combinatorial interpretation.

STOC Conference 1992 Conference Paper

Linear Decision Trees: Volume Estimates and Topological Bounds

• Anders Björner
• László Lovász 0001
• Andrew Chi-Chih Yao

TCS Journal 1992 Journal Article

Rationality of the Möbius function of subword order

• Anders Björner
• Christophe Reutenauer

We prove the rationality of various noncommutative formal power series, whose coefficients are determined by the Möbius function or zeta function of the subword partial order of noncommutative monomials. We also give explicit expressions for the corresponding commutative generating functions.