Repetition in reduced decompositions

Given a permutation w, we show that the number of repeated letters in a reduced decomposition of w is always less than or equal to the number of 321- and 3412-patterns appearing in w. Moreover, we prove bijectively that the two quantities are equal if and only if w avoids the ten patterns 4321, 34 512, 45 123, 35 412, 43 512, 45 132, 45 213, 53 412, 45 312, and 45 231.     

A pattern avoidance criterion for free inversion arrangements

We show that the hyperplane arrangement of a coconvex set in a finite root system is free if and only if it is free in corank 4. As a consequence, we show that the inversion arrangement of a Weyl group element w is free if and only if w avoids a finite list of root system patterns. As a key part of the proof, we use a recent theorem of Abe and Yoshinaga to show that if the root system does not contain any factors of type C or F, then Peterson translation of coconvex sets preserves freeness. This also allows us to give a Kostant–Shapiro–Steinberg rule for the coexponents of a free inversion arrangement in any type.     

Characteristic-independence of Betti numbers of graph ideals

In this paper, we study the Betti numbers of Stanley-Reisner ideals generated in degree 2. We show that the first 6 Betti numbers do not depend on the characteristic of the ground field. We also show that, if the number of variables n is at most 10, all Betti numbers are independent of the ground field. For n=11, there exists precisely 4 examples in which the Betti numbers depend on the ground field. This is equivalent to the statement that the homology of flag complexes with at most 10 vertices is torsion free and that there exists precisely 4 non-isomorphic flag complexes with 11 vertices whose homology has torsion.In each of the 4 examples mentioned above the 8th Betti numbers depend on the ground field and so we conclude that the highest Betti number which is always independent of the ground field is either 6 or 7; if the former is true then we show that there must exist a graph with 12 vertices whose 7th Betti number depends on the ground field.     

The r-major index

The r-major index is a new permutation statistic that is suggested by the work of Carlitz and Gansner on Foulkes' skew-hook rule for computing the r-Eulerian numbers. The new statistic (1) generalizes both the major index and the inversion number of a permutation and (2) leads to a q-analog of the r-Eulerian numbers.     

Growth of Betti numbers

We discuss growth rates of Betti numbers in a family of coverings of a compact cell complex X, when the corresponding L² Betti number of X is zero. We show that the Betti numbers are bounded by a function, sub-linear in the order of the covering. If the appropriate Novikov-Shubin invariant of X is positive, the rate bounds are improved. For well behaved families (such as congruence covers of symmetric spaces), if the L² spectrum of X? has a gap at zero then the growth rate is bounded by the order of the covering raised to a power less than one.     

The Möbius function of separable and decomposable permutations

We give a recursive formula for the Möbius function of an interval [σ,π] in the poset of permutations ordered by pattern containment in the case where π is a decomposable permutation, that is, consists of two blocks where the first one contains all the letters 1,2,…,k for some k. This leads to many special cases of more explicit formulas. It also gives rise to a computationally efficient formula for the Möbius function in the case where σ and π are separable permutations. A permutation is separable if it can be generated from the permutation 1 by successive sums and skew sums or, equivalently, if it avoids the patterns 2413 and 3142.We also show that the Möbius function in the poset of separable permutations admits a combinatorial interpretation in terms of normal embeddings among permutations. A consequence of this interpretation is that the Möbius function of an interval [σ,π] of separable permutations is bounded by the number of occurrences of σ as a pattern in π. Another consequence is that for any separable permutation π the Möbius function of (1,π) is either 0, 1 or −1.     

Counting matrices over finite fields with support on skew Young diagrams and complements of Rothe diagrams

We consider the problem of finding the number of matrices over a finite field with a certain rank and with support that avoids a subset of the entries. These matrices are a q-analogue of permutations with restricted positions (i.e., rook placements). For general sets of entries, these numbers of matrices are not polynomials in q (Stembridge in Ann. Comb. 2(4):365, 1998); however, when the set of entries is a Young diagram, the numbers, up to a power of q?1, are polynomials with nonnegative coefficients (Haglund in Adv. Appl. Math. 20(4):450, 1998). In this paper, we give a number of conditions under which these numbers are polynomials in q, or even polynomials with nonnegative integer coefficients. We extend Haglund’s result to complements of skew Young diagrams, and we apply this result to the case where the set of entries is the Rothe diagram of a permutation. In particular, we give a necessary and sufficient condition on the permutation for its Rothe diagram to be the complement of a skew Young diagram up to rearrangement of rows and columns. We end by giving conjectures connecting invertible matrices whose support avoids a Rothe diagram and Poincaré polynomials of the strong Bruhat order.     

Generic initial ideals of Artinian ideals having Lefschetz properties or the strong Stanley property

For a standard Artinian k-algebra A=R/I, we give equivalent conditions for A to have the weak (or strong) Lefschetz property or the strong Stanley property in terms of the minimal system of generators of gin(I). Using the equivalent condition for the weak Lefschetz property, we show that some graded Betti numbers of gin(I) are determined just by the Hilbert function of I if A has the weak Lefschetz property. Furthermore, for the case that A is a standard Artinian k-algebra of codimension 3, we show that every graded Betti number of gin(I) is determined by the graded Betti numbers of I if A has the weak Lefschetz property. And if A has the strong Lefschetz (respectively Stanley) property, then we show that the minimal system of generators of gin(I) is determined by the graded Betti numbers (respectively by the Hilbert function) of I.     

Partial vexillarity and bigrassmannian permutations

We define two closely related notions of degree for permutation patterns of type 2143. These give rise to classes of “m-vexillary elements” in the symmetric group. Using partitions, the Ehresmann–Bruhat partial order, and sets constructed from permutation inversions, we characterize the m-vexillary elements. We relate the maximal bigrassmannian permutations in the (Ehresmann–Bruhat) order ideal generated by any given m-vexillary element w to the maximal rectangles contained in the shape of w.     

Homology representations arising from the half cube

We construct a CW decomposition Cn of the n-dimensional half cube in a manner compatible with its structure as a polytope. For each 3?k?n, the complex Cn has a subcomplex Cn,k, which coincides with the clique complex of the half cube graph if k=4. The homology of Cn,k is concentrated in degree k−1 and furthermore, the (k−1)st Betti number of Cn,k is equal to the (k−2)nd Betti number of the complement of the k-equal real hyperplane arrangement. These Betti numbers, which also appear in theoretical computer science, numerical analysis and engineering, are the coefficients of a certain Pascal-like triangle (Sloane's sequence A119258). The Coxeter groups of type Dn act naturally on the complexes Cn,k, and thus on the associated homology groups.     

Restricted Simsun Permutations

A permutation is simsun if for all k, the subword of the one-line notation consisting of the k smallest entries does not have three consecutive decreasing elements. Simsun permutations were introduced by Simion and Sundaram, who showed that they are counted by the Euler numbers. In this paper we enumerate simsun permutations avoiding a pattern or a set of patterns of length 3. The results involve Motkzin, Fibonacci, and secondary structure numbers. The techniques in the proofs include generating functions, bijections into lattice paths and generating trees.     

Virtual Betti numbers of real algebraic varieties

We show that for all i?0 the i-th mod 2 Betti number of compact nonsingular real algebraic varieties has a unique extension to a virtual Betti numberβ_i defined for all real algebraic varieties, such that if Y is a closed subvariety of X then β_i(X)=β_i(X?Y)+β_i(Y). We show by example that there is no natural weight filtration on the $\text{Z}{}_2$-cohomology of real algebraic varieties with compact supports such that the virtual Betti numbers are the weighted Euler characteristics. To cite this article: C. McCrory, A. Parusiński, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

Asymptotique des nombres de Betti,invariants $l^2$ et laminations

Let K be a finite simplicial complex. We are interested in the asymptotic behavior of the Betti numbers of a sequence of finite sheeted covers of $K$, when normalized by the index of the covers. W. Lück, has proved that for regular coverings, these sequences of numbers converge to the $l^2$ Betti numbers of the associated (in general infinite) limit regular cover of K. In this article we investigate the non regular case. We show that the sequences of normalized Betti numbers still converge. But this time the good limit object is no longer the associated limit cover of K, but a lamination by simplicial complexes. We prove that the limits of sequences of normalized Betti numbers are equal to the $l^2$ Betti numbers of this lamination. Even if the associated limit cover of K is contractible, its $l^2$ Betti numbers are in general different from those of the lamination. We construct such examples. We also give a dynamical condition for these numbers to be equal. It turns out that this condition is equivalent to a former criterion due to M. Farber. We hope that our results clarify its meaning and show to which extent it is optimal. In a second part of this paper we study non free measure-preserving ergodic actions of a countable group $\Gamma$ on a standard Borel probability space. Extending group-theoretic similar results of the second author, we obtain relations between the $l^{2}$ Betti numbers of $\Gamma$ and those of the generic stabilizers. For example, if $b_1^{(2)} (\Gamma ) \neq 0$, then either almost each stabilizer is finite or almost each stabilizer has an infinite first $l^2$ Betti number.

---

Asymptotique des nombres de Betti, invariants $l^2$ et laminations

     

Bases for permutation groups and matroids

In this paper, we give two equivalent conditions for the irredundant bases of a permutation group to be the bases of a matroid. (These are deduced from a more general result for families of sets.) If they hold, then the group acts geometrically on the matroid, in the sense that the fixed points of any element form a flat. Some partial results towards a classification of such permutation groups are given. Further, if G acts geometrically on a perfect matroid design, there is a formula for the number of G-orbits on bases in terms of the cardinalities of flats and the numbers of G-orbits on tuples. This reduces, in a particular case, to the inversion formula for Stirling numbers.     

Resolutions of letterplace ideals of posets

We investigate resolutions of letterplace ideals of posets. We develop topological results to compute their multigraded Betti numbers, and to give structural results on these Betti numbers. If the poset is a union of no more than c chains, we show that the Betti numbers may be computed from simplicial complexes of no more than c vertices. We also give a recursive procedure to compute the Betti diagrams when the Hasse diagram of P has tree structure.     

Betti numbers of random manifolds

Betti numbers of configuration spaces of mechanical linkages (known also as polygon spaces) depend on a large number of parameters – the lengths of the bars of the linkage. Motivated by applications in topological robotics, statistical shape theory and molecular biology, we view these lengths as random variables and study asymptotic values of the average Betti numbers as the number of links n tends to infinity. We establish a surprising fact that for a reasonably ample class of sequences of probability measures the asymptotic values of the average Betti numbers are independent of the choice of the measure. The main results of the paper apply to planar linkages as well as for linkages in R ³. We also prove results about higher moments of Betti numbers. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Betti numbers of finitely presented groups and very rapidly growing functions

Define the length of a finite presentation of a group G as the sum of lengths of all relators plus the number of generators. How large can the kth Betti number b_k(G)= rank H_k(G) be providing that G has length ≤N and b_k(G) is finite? We prove that for every k≥3 the maximum b_k(N) of the kth Betti numbers of all such groups is an extremely rapidly growing function of N. It grows faster that all functions previously encountered in mathematics (outside of logic) including non-computable functions (at least those that are known to us). More formally, b_k grows as the third busy beaver function that measures the maximal productivity of Turing machines with ≤N states that use the oracle for the halting problem of Turing machines using the oracle for the halting problem of usual Turing machines.We also describe the fastest possible growth of a sequence of finite Betti numbers of a finitely presented group. In particular, it cannot grow as fast as the third busy beaver function but can grow faster than the second busy beaver function that measures the maximal productivity of Turing machines using an oracle for the halting problem for usual Turing machines. We describe a natural problem about Betti numbers of finitely presented groups such that its answer is expressed by a function that grows as the fifth busy beaver function.Also, we outline a construction of a finitely presented group all of whose homology groups are either or trivial such that its Betti numbers form a random binary sequence.     

Permutation Polynomials Modulo 2w

We give an exact characterization of permutation polynomials modulo n=2^w, w≥2: a polynomial P(x)=a₀+a₁x +···+a_dx^d with integral coefficients is a permutation polynomial modulo n if and only if a₁ is odd, (a₂+a₄+a₆+···) is even, and (a₃+a₅+a₇+···) is even. We also characterize polynomials defining latin squares modulo n=2^w, but prove that polynomial multipermutations (that is, a pair of polynomials defining a pair of orthogonal latin squares) modulo n=2^wdo not exist.     

Bigraded Betti numbers of certain simple polytopes

The bigraded Betti numbers β ^?i,2j (P) of a simple polytope P are the dimensions of the bigraded components of the Tor groups of the face ring k[P]. The numbers β ^?i,2j (P) reflect the combinatorial structure of P, as well as the topological structure of the corresponding moment-angle manifold Z _P ; thus, they find numerous applications in combinatorial commutative algebra and toric topology. We calculate certain bigraded Betti numbers of the type β ^?i,2(i+1) for associahedra and apply the calculation of bigraded Betti numbers for truncation polytopes to study the topology of their moment-angle manifolds. Presumably, for these two series of simple polytopes, the numbers β ^?i,2j (P) attain their minimum and maximum values among all simple polytopes P of fixed dimension with a given number of facets.     

Counting nowhere-zero flows on wheels

A wheel is a graph consisting from a vertex w and a circuit C such that each vertex of C is a neighbor of w. Two nowhere-zero group valued flows on a wheel are equivalent if their values differ only on the edges of C. We introduce recursive formulas for the numbers of classes of the same cardinality of this equivalence.