The discrete fundamental group of the order complex of <Emphasis Type="Italic">B</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

A few years ago Kramer and Laubenbacher introduced a discrete notion of homotopy for simplicial complexes. In this paper, we compute the discrete fundamental group of the order complex of the Boolean lattice. As it turns out, it is equivalent to computing the discrete homotopy group of the 1-skeleton of the permutahedron. To compute this group we introduce combinatorial techniques that we believe will be helpful in computing discrete fundamental groups of other polytopes. More precisely, we use the language of words, over the alphabet of simple transpositions, to obtain conditions that are necessary and sufficient to characterize the equivalence classes of cycles. The proof requires only simple combinatorial arguments. As a corollary, we also obtain a combinatorial proof of the fact that the first Betti number of the complement of the 3-equal arrangement is equal to 2 ^n?3(n ²?5n+8)?1. This formula was originally obtained by Björner and Welker in 1995.     

A Geometric Characterization of Poly-antimatroids

The concept of "antimatroid with repetition" was coined by Bjorner, Lovasz and Shor in 1991 as an extension of the notion of antimatroid in the framework of non-simple languages [Björner A., L. Lovász, and P. R. Shor, Chip-firing games on graphs, European Journal of Combinatorics 12 (1991), 283–291]. There are some equivalent ways to define antimatroids. They may be separated into two categories: antimatroids defined as set systems and antimatroids defined as languages. For poly-antimatroids we use the set system approach. In this research we concentrate on interrelations between geometric, algorithmic, and lattice properties of poly-antimatroids. Much to our surprise it turned out that even the two-dimensional case is not trivial.     

A combinatorial decomposition of simplicial complexes

We find a decomposition of simplicial complexes that implies and sharpens the characterization (due to Björner and Kalai) of thef-vector and Betti numbers of a simplicial complex. It generalizes a result of Stanley, who proved the acyclic case, and settles a conjecture of Stanley and Kalai.     

On quotients of Coxeter groups under the weak order

We consider quotients of finitely generated Coxeter groups under the weak order. Björner and Wachs proved that every such quotient is a meet semi-lattice, and in the finite case is a lattice [Björner and Wachs, Trans. Amer. Math. Soc. 308 (1988) 1–37]. Our result is that the quotient of an affine Weyl group by the corresponding finite Weyl group is a lattice, and that up to isomorphism, these are the only quotients of infinite Coxeter groups that are lattices. In this paper, we restrict our attention to the non-affine case; the affine case appears in [Waugh, Order 16 (1999) 77–87]. We reduce to the hyperbolic case by an argument using induced subgraphs of Coxeter graphs. Within each quotient, we produce a set of elements with no common upper bound, generated by a Maple program. The number of cases is reduced because the sets satisfy the following conjecture: if a set of elements does not have an upper bound in a particular Coxeter group, then it does not have an upper bound in any Coxeter group whose graph can be obtained from the graph of the original group by increasing edge weights.     

The Möbius function of a composition poset

We determine the Möbius function of a poset of compositions of an integer. In fact, we give two proofs of this formula, one using an involution and one involving discrete Morse theory. This composition poset turns out to be intimately connected with subword order, whose Möbius function was determined by Björner. We show that, using a generalization of subword order, we can obtain both Björner’s results and our own as special cases.     

Lower bound on testing membership to a polyhedron by algebraic decision and computation trees

We introduce a new method of proving lower bounds on the depth of algebraicd-degree decision (resp. computation) trees and apply it to prove a lower bound Ω (logN) (resp. Ω (log N/log logN)) for testing membership to an n-dimensional convex polyhedron havingN faces of all dimensions, provided thatN > (nd)^Ω(n) (resp.N > n^Ω(n)). This bound apparently does not follow from the methods developed by Ben-Or, Björner, Lovasz, and Yao [1], [4], [24] because topological invariants used in these methods become trivial for convex polyhedra     

The lexicographic sum of Cohen-Macaulay and shellable ordered sets

We study the problem of determining when the lexicographic sum ∑ _q∈Q P _q of a family of posets {P _q/qεQ} over a posetQ is Cohen-Macaulay or shellable. Our main result, a characterization of when the lexicographic sum is Cohen-Macaulay, is proven using combinatorial methods introduced by Garsia. A similar characterization for when the lexicographic sum is CL (chainwise-lexicographically)-shellable, is derived using the recursive atom ordering method due to Björner and Wachs.     

General lexicographic shellability and orbit arrangements

We introduce a new poset property which we call EC-shellability. It is more general than the more established concept of EL-shellability, but it still implies shellability. Because of Theorem 3.10, EC-shellability is entitled to be called general lexicographic shellability. As an application of our new concept, we prove that intersection lattices Π_λ of orbit arrangementsA _λ are EC-shellable for a very large class of partitions λ. This allows us to compute the topology of the link and the complement for these arrangements. In particular, for this class of λs, we are able to settle a conjecture of Björner [B94, Conjecture 13.3.2], stating that the cohomology groups of the complement of the orbit arrangements are torsion-free. We also present a class of partitions for which Π_λ is not shellable, along with other issues scattered throughout the paper.     

A multivariate “inv” hook formula for forests

Björner and Wachs provided two q-generalizations of Knuth’s hook formula counting linear extensions of forests: one involving the major index statistic, and one involving the inversion number statistic. We prove a multivariate generalization of their inversion number result, motivated by specializations related to the modular invariant theory of finite general linear groups.     

A Conformal Averaging Process on the Circle

In this paper we consider one of the simplest discrete conformally natural averaging processes. We start with a collection P of n ≥ 5 cyclically ordered points on the circle and produce a new collection P′ of n cyclically ordered points on the circle. The naturality means that (T(P))′=T(P′) for T any Möbius transformation of the circle. Let P ^(k) denote the kth iterate of P under the process. We show, for any initial choice P, that the limit lim _k→∞ P ^(K) exists and is conformally equivalent to a collection of n evenly spaced points. The convergence is exponentially fast. We also consider our process on projective 1-manifolds, which are topological circles equipped with exotic geometric structures based on the Lie group PSL₂(R).     

Involutive solutions for toda and langmuir lattices through nonlinearization of lax pairs

Under the constraint determined by a relation (a _n ,b _n )^T={f(?)} _n between the reflectionless potentials and the eigenfunctions of the general discrete Schrödinger eigenvalue problem, the Lax pair of the Toda lattice is nonlinearized to be a finite-dimensional difference system and a nonlinear evolution equation, while the solution varietyN of the former is an invariant set of S-flows determined by the latter, and the constants of the motion for the algebraic system are presented.f maps the solution of the algebraic system into the solution of a certain stationary Toda equation. Similar results concerning the Langmuir lattice are given, and a relation between the two difference systems, which are the spatial parts of the nonlinearized Lax pairs of the Toda lattice and Langmuir lattice, is discussed.     

On Lovász’ lattice reduction and the nearest lattice point problem

Answering a question of Vera Sós, we show how Lovász’ lattice reduction can be used to find a point of a given lattice, nearest within a factor ofc ^d (c = const.) to a given point in R ^d . We prove that each of two straightforward fast heuristic procedures achieves this goal when applied to a lattice given by a Lovász-reduced basis. The verification of one of them requires proving a geometric feature of Lovász-reduced bases: ac ₁ ^d lower bound on the angle between any member of the basis and the hyperplane generated by the other members, wherec ₁ = √2/3. As an application, we obtain a solution to the nonhomogeneous simultaneous diophantine approximation problem, optimal within a factor ofC ^d . In another application, we improve the Grötschel-Lovász-Schrijver version of H. W. Lenstra’s integer linear programming algorithm. The algorithms, when applied to rational input vectors, run in polynomial time.     

New polytopes from products

We construct a new 2-parameter family Emn, m,n?3, of self-dual 2-simple and 2-simplicial 4-polytopes, with flexible geometric realisations. E₄₄ is the 24-cell. For large m,n the f-vectors have “fatness” close to 6. The Et-construction of Paffenholz and Ziegler applied to products of polygons yields cellular spheres with the combinatorial structure of Emn. Here we prove polytopality of these spheres. More generally, we construct polytopal realisations for spheres obtained from the Et-construction applied to products of polytopes in any dimension d?3, if these polytopes satisfy some consistency conditions. We show that the projective realisation space of E₃₃ is at least nine-dimensional and that of E₄₄ at least four-dimensional. This proves that the 24-cell is not projectively unique. All Emn for relatively prime m,n?5 have automorphisms of their face lattice not induced by an affine transformation of any geometric realisation. The group Zm×Zn generated by rotations in the two polygons is a subgroup of the automorphisms of the face lattice of Emn. However, there are only five pairs (m,n) for which this subgroup is geometrically realisable.     

Torsion in the matching complex and chessboard complex

Topological properties of the matching complex were first studied by Bouc in connection with Quillen complexes, and topological properties of the chessboard complex were first studied by Garst in connection with Tits coset complexes. Björner, Lovász, Vre?ica and ?ivaljevi? established bounds on the connectivity of these complexes and conjectured that these bounds are sharp. In this paper we show that the conjecture is true by establishing the nonvanishing of integral homology in the degrees given by these bounds. Moreover, we show that for sufficiently large n, the bottom nonvanishing homology of the matching complex Mn is an elementary 3-group, improving a result of Bouc, and that the bottom nonvanishing homology of the chessboard complex Mn,n is a 3-group of exponent at most 9. When , the bottom nonvanishing homology of Mn,n is shown to be Z₃. Our proofs rely on computer calculations, long exact sequences, representation theory, and tableau combinatorics.     

The lattice of integer partitions

In this paper we study the lattice L_n of partitions of an integer n ordered by dominance. We show L_n to be isomorphic to an infimum subsemilattice under the component ordering of certain concave nondecreasing (n+1)-tuples. For L_n, we give the covering relation, maximal covering number, minimal chains, infimum and supremum irreducibles, a chain condition, distinguished intervals; and show that partition conjugation is a lattice antiautomorphism. L_n is shown to have no sublattice having five elements and rank two, and we characterize intervals generated by two cocovers. The Möbius function of L_n is computed and shown to be 0,1 or -1. We then give methods for studying classes of (0,1)-matrices with prescribed row and column sums and compute a lower bound for their cardinalities.     

On first passage time structure of random walks

For continuous time birth-death processes on {0,1,2,…}, the first passage time T⁺_n from n to n + 1 is always a mixture of (n + 1) independent exponential random variables. Furthermore, the first passage time T_0,n+1 from 0 to (n + 1) is always a sum of (n + 1) independent exponential random variables. The discrete time analogue, however, does not necessarily hold in spite of structural similarities. In this paper, some necessary and sufficient conditions are established under which T⁺_n and T_0,n+1 for discrete time birth-death chains become a mixture and a sum, respectively, of (n + 1) independent geometric random variables on {1,2,…};. The results are further extended to conditional first passage times.     

On orthogonal matrices with constant diagonal

In connection with the problem of finding the best projections of k-dimensional spaces embedded in n-dimensional spaces Hermann König asked: Given m∈$\text{R}$ and n∈$\text{N}$, are there n×n matrices C=(c_ij), i, j=1,…,n, such that c_ii=m for all i, |c_ij|=1 for i≠j, and C²=(m²+n?1)I_n? König was especially interested in symmetric C, and we find some families of matrices satisfying this condition. We also find some families of matrices satisfying the less restrictive condition CC^T=(m²+n?1)I_n.     

Stable Comparison of Multidimensional Persistent Homology Groups with Torsion

The present lack of a stable method to compare persistent homology groups with torsion is a relevant problem in current research about Persistent Homology and its applications in Pattern Recognition. In this paper we introduce a pseudo-distance d _T that represents a possible solution to this problem. Indeed, d _T is a pseudo-distance between multidimensional persistent homology groups with coefficients in an Abelian group, hence possibly having torsion. Our main theorem proves the stability of the new pseudo-distance with respect to the change of the filtering function, expressed both with respect to the max-norm and to the natural pseudo-distance between topological spaces endowed with ? ⁿ -valued filtering functions. Furthermore, we prove a result showing the relationship between d _T and the matching distance in the 1-dimensional case, when the homology coefficients are taken in a field and hence the comparison can be made.     

Hyperinvariant subspaces ofC 0-operators over a multiply connected region

In this paper we find a relation between the lattice of hyperinvariant subspaces of an operatorT of classC ₀ over a multiply connected region and that of its Jordan modelT. It is shown that, generally, the lattice corresponding toT can be identified with a retract of that corresponding toT. Thus the Jordan model has the smallest lattice of hyperinvariant subspaces in a given quasisimilarity class.