The Homology of Partitions with an Even Number of Blocks

Let denote the subposet obtained by selecting even ranks in the partition lattice . We show that the homology of has dimension , where is the tangent number. It is thus an integral multiple of both the Genocchi number and an André or simsun number. Using the general theory of rank-selected homology representations developed in [22], we show that, for the special case of , the character of the symmetric group S _2n on the homology is supported on the set of involutions. Our proof techniques lead to the discovery of a family of integers b _i(n), 2 i n, defined recursively. We conjecture that, for the full automorphism group S _2n, the homology is a sum of permutation modules induced from Young subgroups of the form , with nonnegative integer multiplicity b _i(n). The nonnegativity of the integers b _i(n) would imply the existence of new refinements, into sums of powers of 2, of the tangent number and the André or simsun number a _n(2n).Similarly, the restriction of this homology module to S _2n–1 yields a family of integers d _i(n), 1 i n – 1, such that the numbers 2^–i d _i(n) refine the Genocchi number G _2n . We conjecture that 2^–i d _i(n) is a positive integer for all i.Finally, we present a recursive algorithm to generate a family of polynomials which encode the homology representations of the subposets obtained by selecting the top k ranks of , 1 k n – 1. We conjecture that these are all permutation modules for S _2n .     

Unimodular Triangulations and Coverings of Configurations Arising from Root Systems

Existence of a regular unimodular triangulation of the configuration , where ⁺ is the collection of the positive roots of a root system and where (0, 0,...,0 ) is the origin of , will be shown for = B _n , C _n , D _n and BC _n . Moreover, existence of a unimodular covering of a certain subconfiguration of the configuration A _n+1 ⁺ will be studied.     

Divergence of a Random Walk Through Deterministic and Random Subsequences

Let {S _n} _n0 be a random walk on the line. We give criteria for the existence of a nonrandom sequence n _i for which respectively We thereby obtain conditions for to be a strong limit point of {S _n} or {S _n /n}. The first of these properties is shown to be equivalent to for some sequence a _i , where T(a) is the exit time from the interval [–a,a]. We also obtain a general equivalence between and for an increasing function fand suitable sequences n _i and a _i. These sorts of properties are of interest in sequential analysis. Known conditions for and (divergence through the whole sequence n) are also simplified.     

Quotient Complexes and Lexicographic Shellability

Let _n,k,k and _n,k,h , h < k, denote the intersection lattices of the k-equal subspace arrangement of type _n and the k,h-equal subspace arrangement of type _n respectively. Denote by the group of signed permutations. We show that ( _n,k,k )/ is collapsible. For ( _n,k,h )/ , h < k, we show the following. If n 0 (mod k), then it is homotopy equivalent to a sphere of dimension . If n h (mod k), then it is homotopy equivalent to a sphere of dimension . Otherwise, it is contractible. Immediate consequences for the multiplicity of the trivial characters in the representations of on the homology groups of ( _n,k,k ) and ( _n,k,h ) are stated.The collapsibility of ( _n,k,k )/ is established using a discrete Morse function. The same method is used to show that ( _n,k,h )/ , h < k, is homotopy equivalent to a certain subcomplex. The homotopy type of this subcomplex is calculated by showing that it is shellable. To do this, we are led to introduce a lexicographic shelling condition for balanced cell complexes of boolean type. This extends to the non-pure case work of P. Hersh (Preprint, 2001) and specializes to the CL-shellability of A. Björner and M. Wachs (Trans. Amer. Math. Soc. 4 (1996), 1299–1327) when the cell complex is an order complex of a poset.     

Young Straightening in a Quotient Sn-Module

We describe a straightening algorithm for the action of S _n on a certain graded ring . The ring appears in the work of C. de Concini and C. Procesi [2] and T. Tanisaki [8], and more recently in the work of A. Garsia and C. Procesi [4]. This ring is a graded version of the permutation representation resulting from the action of S _n on the left cosets of a Young subgroup. As a corollary of our straightening algorithm we obtain a combinatorial proof of the fact that the top degree component of affords the irreducible representation of S _n indexed by .     

The Lattice of Interpretability Types of Cantor Varieties

For integers 1 m < n, a Cantor variety with m basic n-ary operations _i and n basic m-ary operations _k is a variety of algebras defined by identities _k(₁( ), ... , _m( )) = _k and i(₁( ), ... ,_n( )) = y _i, where = (x ₁., ... , x _n) and = (y ₁, ... , y _m). We prove that interpretability types of Cantor varieties form a distributive lattice, , which is dual to the direct product ₁ × ₂ of a lattice, ₁, of positive integers respecting the natural linear ordering and a lattice, ₂, of positive integers with divisibility. The lattice is an upper subsemilattice of the lattice of all interpretability types of varieties of algebras.     

A Geometric Characterization of Fischer's Baby Monster

The sporadic simple group F ₂ known as Fischer's Baby Monster acts flag-transitively on a rank 5 P-geometry . P-geometries are geometries with string diagrams, all of whose nonempty edges except one are projective planes of order 2 and one terminal edge is the geometry of the Petersen graph. Let be a flag-transitive P-geometry of rank 5. Suppose that each proper residue of is isomorphic to the corresponding residue in . We show that in this case is isomorphic to . This result realizes a step in classification of the flag-transitive P-geometries and also plays an important role in the characterization of the Fischer–Griess Monster in terms of its 2-local parabolic geometry.     

Spin Models and Strongly Hyper-Self-Dual Bose-Mesner Algebras

We introduce the notion of hyper-self-duality for Bose-Mesner algebras as a strengthening of formal self-duality. Let denote a Bose-Mesner algebra on a finite nonempty set X. Fix p X, and let and denote respectively the dual Bose-Mesner algebra and the Terwilliger algebra of with respect to p. By a hyper-duality of , we mean an automorphism of such that for all ; and is a duality of . is said to be hyper-self-dual whenever there exists a hyper-duality of . We say that is strongly hyper-self-dual whenever there exists a hyper-duality of which can be expressed as conjugation by an invertible element of . We show that Bose-Mesner algebras which support a spin model are strongly hyper-self-dual, and we characterize strong hyper-self-duality via the module structure of the associated Terwilliger algebra.     

A Characterisation of the Generalized Quadrangle Q (5, q) Using Cohomology

If a GQ S of order (s, s) is contained in a GQ S of order (s, s ²) as a subquadrangle, then for each point X of S\S the set of points of S collinear with X form an ovoid of S. Thas and Payne proved that if S= (4,q),q even, and is an elliptic quadric for each XS\S,thenS (5,q). In this paper we provide a single proof for the q odd and q even cases by establishing a link between the geometry involved and the first cohomology group of a related simplicial complex.     

Distance-Regular Graphs Related to the Quantum Enveloping Algebra of sl(2)

We investigate a connection between distance-regular graphs and U _q(sl(2)), the quantum universal enveloping algebra of the Lie algebra sl(2). Let be a distance-regular graph with diameter d 3 and valency k 3, and assume is not isomorphic to the d-cube. Fix a vertex x of , and let (x) denote the Terwilliger algebra of with respect to x. Fix any complex number q {0, 1, –1}. Then is generated by certain matrices satisfying the defining relations of U _q(sl(2)) if and only if is bipartite and 2-homogeneous.     

On a Family of Hyperplane Arrangements Related to the Affine Weyl Groups

Let be an irreducible crystallographic rootsystem in a Euclidean space V, with ⁺ theset of positive roots. For , , let be the hyperplane . We define a set of hyperplanes . This hyperplane arrangement is significant inthe study of the affine Weyl groups. In this paper it is shown that thePoincaré polynomial of is , where n is the rank of and h is the Coxeter number of the finiteCoxeter group corresponding to .     

Popularity of Sets Represented by the Partitions of n

Let us say that a partition of the positive integer n represents a, 0 a n, if there is a submultiset of the multiset of the parts whose sum is a. Erd os and Szalay have proved that almost all partitions of n represent all integers a, 0 a n. If is a finite set of positive integers, let us denote by p~(n, ) the number of partitions of n which represent all integers a, 0 a n, a , n – a but do not represent a for a . For instance, p~(n,) is the number of partitions of n which represent all integers between 0 and n; the result of Erd os and Szalay can be reformulated as p~(n,) p(n), where p(n) is the total number of partitions of n. The aim of this paper is the study of p~(n, ): we shall compare the values of p~(n, ) for small sets and we shall give a close formula for p~(n, ) when is the set of the first k integers.     

Finite splitting fields of normal subgroups

Let G be a finite group, a normal subgroup, p a prime, a finite splitting field of characteristic p for G and We prove that is a splitting field for N, using the action of the Galois group of the field extension on the irreducible representations of N. As is a splitting field for the symmetric group S_n we get as a corollary that is a splitting field for the alternating group A_n. Received: 31 July 2003     

Classifying Arc-Transitive Circulants of Square-Free Order

A circulant is a Cayley graph of a cyclic group. Arc-transitive circulants of square-free order are classified. It is shown that an arc-transitive circulant of square-free order n is one of the following: the lexicographic product , or the deleted lexicographic , where n = bm and is an arc-transitive circulant, or is a normal circulant, that is, Aut has a normal regular cyclic subgroup.     

Generating Random Elements in SL n (F q ) by Random Transvections

This paper studies a random walk based on random transvections in SL _n(F _q ) and shows that, given > 0, there is a constant c such that after n + c steps the walk is within a distance from uniform and that after n – c steps the walk is a distance at least 1 – from uniform. This paper uses results of Diaconis and Shahshahani to get the upper bound, uses results of Rudvalis to get the lower bound, and briefly considers some other random walks on SL _n(F _q ) to compare them with random transvections.     

Vertex-Transitive Non-Cayley Graphs with Arbitrarily Large Vertex-Stabilizer

A construction is given for an infinite family {_n} of finite vertex-transitive non-Cayley graphs of fixed valency with the property that the order of the vertex-stabilizer in the smallest vertex-transitive group of automorphisms of _n is a strictly increasing function ofn . For each n the graph is 4-valent and arc-transitive, with automorphism group a symmetric group of large prime degree . The construction uses Sierpinski's gasket to produce generating permutations for the vertex-stabilizer (a large 2-group).     

Homogeneity of a Distance-Regular Graph Which Supports a Spin Model

A spin model is a square matrix that encodes the basic data for a statistical mechanical construction of link invariants due to V.F.R. Jones. Every spin model W is contained in a canonical Bose-Mesner algebra (W). In this paper we study the distance-regular graphs whose Bose-Mesner algebra satisfies W (W). Suppose W has at least three distinct entries. We show that is 1-homogeneous and that the first and the last subconstituents of are strongly regular and distance-regular, respectively.     

More on Geometries of the Fischer Group Fi 22

We give a new, purely combinatorial characterization of geometries with diagram identifying each under some natural conditions—but not assuming any group action a priori—with one of the two geometries and related to the Fischer 3-transposition group Fi ₂₂ and its non-split central extension 3 · Fi ₂₂, respectively. As a by-product we improve the known characterization of the c-extended dual polar spaces for Fi ₂₂ and 3 · Fi ₂₂ and of the truncation of the c-extended 6-dimensional unitary polar space.     

Dimension Theory and Nonstable K1 of Quadratic Modules

Employing Bak's dimension theory, we investigate the nonstable quadratic K-group K _1,2n (A, ) = G _2n (A, )/E _2n (A, ), n 3, where G _2n (A, ) denotes the general quadratic group of rank n over a form ring (A, ) and E _2n (A, ) its elementary subgroup. Considering form rings as a category with dimension in the sense of Bak, we obtain a dimension filtration G _2n (A, ) G _2n ⁰(A, ) ; G _2n ¹(A, ) ... E _2n (A, ) of the general quadratic group G _2n (A, ) such that G _2n (A, )/G _2n ⁰(A, ) is Abelian, G _2n ⁰(A, ) G _2n ¹(A, ) ... is a descending central series, and G _2n ^d(A)(A, ) = E _2n (A, ) whenever d(A) = (Bass–Serre dimension of A) is finite. In particular K _1,2n (A, ) is solvable when d(A) < .     

An Intersection Theorem on an Unbounded Set and Its Application to the Fair Allocation Problem

We prove the following theorem. Let m and n be any positive integers with mn, and let be a subset of the n-dimensional Euclidean space ⁿ . For each i=1, . . . , m, there is a class of subsets M _i ^j of ^Tn . Assume that for each i=1, . . . , m, that M _i ^j is nonempty and closed for all i, j, and that there exists a real number B(i, j) such that and its jth component _{xjB(i, j)} imply . Then, there exists a partition of {1, . . . , n} such that for all i and We prove this theorem based upon a generalization of a well-known theorem of Birkhoff and von Neumann. Moreover, we apply this theorem to the fair allocation problem of indivisible objects with money and obtain an existence theorem.