Let Delta be a thick and locally finite building with the property that no edge of the associated Coxerer diagram has label "infinity". The chamber graph G(Delta), whose edges are the pairs of adjacent chambers in Delta is known to be q-regular for a certain number q = q(Delta). Our main result is that G(Delta) is q-connected in the sense of graph theory. In the language of building theory this means that every pair of chambers of Delta is connected by q pairwise disjoint galleries. Similar results are proved for the chamber graphs of Coxeter complexes and for order complexes of geometric lattices.

We study a group action on permutations due to Foata and Strehl and use it to prove that the descent generating polynomial of certain sets of permutations has a non-negative expansion in the basis {t(i) (1 + t)(n-1-2i)}(i=0)(m), m = [(n - 1)/2]. This property implies symmetry and unimodality. We prove that the action is invariant under stack sorting which strengthens recent unimodality results of Bona. We prove that the generalized permutation patterns (13-2) and (2-31) are invariant under the action and use this to prove unimodality properties for a q-analog of the Eulerian numbers recently studied by Corteel, Postnikov, Steingrimsson and Williams. We also extend the action to linear extensions of sign-graded posets to give a new proof of the unimodality of the (P, omega)-Eulerian polynomials of sign-graded posets and a combinatorial interpretations (in terms of Stembridge's peak polynomials) of the corresponding coefficients when expanded in the above basis. Finally, we prove that the statistic defined as the number of vertices of even height in the unordered decreasing tree of a permutation has the same distribution as the number of descents on any set of permutations invariant under the action. On restricting to the set of stack sortable permutations we recover a result of Kreweras.

KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).

Independence complexes of claw-free graphs2008In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 29, no 1, p. 234-241Article in journal (Refereed)

Abstract [en]

We study the class of independence complexes of claw-free graphs. The main theorem gives good bounds on the connectivity of these complexes, given bounds for a few subcomplexes of the same class. Two applications are presented. Firstly, we show that the independence complex of a claw-free graph with n vertices and maximal degree d is (cn/d + epsilon)-connected, where c = 2/3. This can be compared with the result of Szabo and Tardos that c = 1/2 is optimal with no restrictions on the graphs. Secondly, we calculate the connectivity of a family of complexes used in Babson and Kozlov's proof of the Lovasz conjecture.

The Witten index for certain supersymmetric lattice models treated by de Boer, van Eerten, Fendley, and Schoutens, can be formulated as a topological invariant of simplicial complexes, arising as independence complexes of graphs. We prove a general theorem on independence complexes, using discrete Morse theory: if G is a graph and D a subset of its vertex set such that G\D is a forest, then Sigma(i) dim (H) over bar (i)(Ind(G): Q) <= |Ind(G|D|)|. We use the theorem to calculate upper bounds on the Witten index for several classes of lattices. These bounds confirm some of the computer calculations by van Eerten on small lattices.

The cohomological method and the 3-rule of Fendley et al. is a special case of when G\D lacks edges. We prove a generalized 3-rule and introduce lattices in arbitrary dimensions satisfying it.

In this paper we verify a conjecture by Kozlov [D.N. Kozlov, Convex Hulls of f- and beta-vectors, Discrete Comput. Geom. 18 (1997) 421-431], which describes the convex hull of the set of face vectors of r-colorable complexes on n vertices. As part of the proof we derive a generalization of Turn's graph theorem.

In this paper we consider the relation between the spectrum and the number of short cycles in large graphs. Suppose G(1), G(2), G(3), ... is a sequence of finite and connected graphs that share a common universal cover T and such that the proportion of eigenvalues of G(n) that lie within the support of the spectrum of T tends to 1 in the large n limit. This is a weak notion of being Ramanujan. We prove such a sequence of graphs is asymptotically locally tree-like. This is deduced by way of an analogous theorem proved for certain infinite sofic graphs and unimodular networks, which extends results for regular graphs and certain infinite Cayley graphs.

KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).

Link complexes of subspace arrangements2007In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 28, no 3, p. 781-790Article in journal (Refereed)

Abstract [en]

Given a simplicial hyperplane arrangement H and a subspace arrangement A embedded in H, we define a simplicial complex Delta(A,H) as the subdivision of the link of A induced by R. In particular, this generalizes Steingrimsson's coloring complex of a graph. We do the following: (1) When A is a hyperplane arrangement, Delta(A,H) is shown to be shellable. As a special case, we answer affirmatively a question of Steingrimsson on coloring complexes. (2) For H a Coxeter arrangement of type A or B we obtain a close connection between the Hilbert series of the Stanley-Reisner ring Of Delta(A,H) and the characteristic polynomial of A. This extends results of Steingrimsson and provides an interpretation of chromatic polynomials of hypergraphs and signed graphs in terms of Hilbert polynomials.

Polygraph arrangements2002In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 23, no 8, p. 937-948Article in journal (Refereed)

Abstract [en]

A class of subspace arrangements, Z(n, m), known as polygraph arrangements was exploited by Haiman in order to prove the n! theorem. By showing that their intersection lattices, L(Z(n, m)), are EL-shellable, we determine the cohomology groups of the complements of the arrangements. Moreover, we generalize the shellability results to a class of lattices which deserve to be called Dowling generalizations of L (Z (n, m)). As a consequence, we obtain the cohomology groups of the complements of certain Dowling analogues of polygraph arrangements.

There are 10(n) zero-sum words of length 5n in the alphabet {+3, -2} such that no zero-sum consecutive subword that starts with +3 may be followed immediately by -2.

We give a simple bijective proof of the conjecture in its original and more general setting. To do this we reformulate the problem in terms of cylindrical lattice walks.

KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).

On the sign-imbalance of skew partition shapes2007In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 28, no 6, p. 1582-1594Article in journal (Refereed)

Abstract [en]

Let the sign of a skew standard Young tableau be the sign of the permutation you get by reading it row by row from left to right, like a book. We examine how the sign property is transferred by the skew Robinson-Schensted correspondence invented by Sagan and Stanley. The result is a remarkably simple generalization of the ordinary non-skew formula.The sum of the signs of all standard tableaux on a given skew shape is the sign-imbalance of that shape. We generalize previous results on the sign-imbalance of ordinary partition shapes to skew ones.