We introduce a natural Hopf algebra structure on the space of noncommutative symmetric functions. The bases for this algebra are indexed by set partitions. We show that there exists a natural inclusion of the Hopf algebra of noncommutative symmetric functions in this larger space. We also consider this algebra as a subspace of noncommutative polynomials and use it to understand the structure of the spaces of harmonics and coinvariants with respect to this collection of noncommutative polynomials and conclude two analogues of Chevalley's theorem in the noncommutative setting.

The classical Hurwitz enumeration problem has a presentation in terms of transitive factorizations in the symmetric group. This presentation suggests a generalization from type~$A$ to other finite reflection groups and, in particular, to type~$B$. We study this generalization both from a combinatorial and a geometric point of view, with the prospect of providing a means of understanding more of the structure of the moduli spaces of maps with an $\gS_2$-symmetry. The type~$A$ case has been well studied and connects Hurwitz numbers to the moduli space of curves. We conjecture an analogous setting for the type~$B$ case that is studied here.

We classify linear weighted graphs up to the blowing-up and blowing-down operations which are relevant for the study of algebraic surfaces.

Let $X$ be a locally finite, connected graph without vertices of degree $1$. Non-backtracking random walk moves at each step with equal probability to one of the ``forward'' neighbours of the actual state, \emph{i.e.,} it does not go back along the preceding edge to the preceding state. This is not a Markov chain, but can be turned into a Markov chain whose state space is the set of oriented edges of $X$. Thus we obtain for infinite $X$ that the $n$-step non-backtracking transition probabilities tend to zero, and we can also compute their limit when $X$ is finite. This provides a short proof of old results concerning cogrowth of groups, and makes the extension of that result to arbitrary regular graphs rigorous. Even when $X$ is non-regular, but \emph{small cycles are dense in} $X$, we show that the graph $X$ is non-amenable if and only if the non-backtracking $n$-step transition probabilities decay exponentially fast. This is a partial generalization of the cogrowth criterion for regular graphs which comprises the original cogrowth criterion for finitely generated groups of Grigorchuk and Cohen.

This paper studies the Laplacian operator on a metrized graph, and its spectral theory.

K.~Ding studied a class of Schubert varieties $X_\lambda$ in type A partial flag manifolds, indexed by integer partitions $\lambda$ and in bijection with dominant permutations. He observed that the Schubert cell structure of $X_\lambda$ is indexed by maximal rook placements on the Ferrers board $B_\lambda$, and that the integral cohomology groups $H^*(X_\lambda;\:\Zz)$, $H^*(X_\mu;\:\Zz)$ are additively isomorphic exactly when the Ferrers boards $B_\lambda, B_\mu$ satisfy the combinatorial condition of \emph{rook-equivalence}. We classify the varieties $X_\lambda$ up to isomorphism, distinguishing them by their graded cohomology rings with integer coefficients. The crux of our approach is studying the nilpotence orders of linear forms in the cohomology ring.

Connections between behaviour of real analytic functions (with no negative Maclaurin series coefficients and radius of convergence one) on the open unit interval, and to a lesser extent on arcs of the unit circle, are explored, beginning with Karamata's approach. We develop conditions under which the asymptotics of the coefficients are related to the values of the function near $1$; specifically, $a(n)\sim f(1-1/n)/ \alpha n$ (for some positive constant $\alpha$), where $f(t)=\sum a(n)t^n$. In particular, if $F=\sum c(n) t^n$ where $c(n) \geq 0$ and $\sum c(n)=1$, then $f$ defined as $(1-F)^{-1}$ (the renewal or Green's function for $F$) satisfies this condition if $F'$ does (and a minor additional condition is satisfied). In come cases, we can show that the absolute sum of the differences of consecutive Maclaurin coefficients converges. We also investigate situations in which less precise asymptotics are available.

An $n \times n$ matrix is said to be totally nonnegative if every minor of $A$ is nonnegative. In this paper we completely characterize all possible Jordan canonical forms of irreducible totally nonnegative matrices. Our approach is mostly combinatorial and is based on the study of weighted planar diagrams associated with totally nonnegative matrices.

A coplactic class in the symmetric group $\Sym_n$ consists of all permutations in $\Sym_n$ with a given Schensted $Q$-symbol, and may be described in terms of local relations introduced by Knuth. Any Lie element in the group algebra of $\Sym_n$ which is constant on coplactic classes is already constant on descent classes. As a consequence, the intersection of the Lie convolution algebra introduced by Patras and Reutenauer and the coplactic algebra introduced by Poirier and Reutenauer is the direct sum of all Solomon descent algebras.

We present a concise explicit expression for the heat trace coefficients of spheres. Our formulas yield certain combinatorial identities which are proved following ideas of D.~Zeilberger. In particular, these identities allow to recover in a surprising way some known formulas for the heat trace asymptotics. Our approach is based on a method for computation of heat invariants developed in [P].

We introduce the notion of strongly projective graph, and characterise these graphs in terms of their neighbourhood poset. We describe certain exponential graphs associated to complete graphs and odd cycles. We extend and generalise a result of Greenwell and Lov\'asz \cite{GreLov}: if a connected graph $G$ does not admit a homomorphism to $K$, where $K$ is an odd cycle or a complete graph on at least 3 vertices, then the graph $G \times K^s$ admits, up to automorphisms of $K$, exactly $s$ homomorphisms to $K$.

Willis's structure theory of totally disconnected locally compact groups is investigated in the context of permutation actions. This leads to new interpretations of the basic concepts in the theory and also to new proofs of the fundamental theorems and to several new results. The treatment of Willis's theory is self-contained and full proofs are given of all the fundamental results.

We describe the set of numbers $\sigma_k(z_1,\ldots,z_{n+1})$, where $z_1,\ldots,z_{n+1}$ are complex numbers of modulus $1$ for which $z_1z_2\cdots z_{n+1}=1$, and $\sigma_k$ denotes the $k$-th elementary symmetric polynomial. Consequently, we give sharp constraints on the coefficients of a complex polynomial all of whose roots are of the same modulus. Another application is the calculation of the spectrum of certain adjacency operators arising naturally on a building of type ${\tilde A}_n$.

We classify all 3 letter patterns that are avoidable in the abelian sense. A short list of four letter patterns for which abelian avoidance is undecided is given. Using a generalization of Zimin words we deduce some properties of $\o$-words avoiding these patterns.

The question of counting minimal factorizations of permutations into transpositions that act transitively on a set has been studied extensively in the geometrical setting of ramified coverings of the sphere and in the algebraic setting of symmetric functions. It is natural, however, from a combinatorial point of view to ask how such results are affected by counting up to equivalence of factorizations, where two factorizations are equivalent if they differ only by the interchange of adjacent factors that commute. We obtain an explicit and elegant result for the number of such factorizations of permutations with precisely two factors. The approach used is a combinatorial one that rests on two constructions. We believe that this approach, and the combinatorial primitives that have been developed for the ``cut and join'' analysis, will also assist with the general case.

A $\mathbb{Z}_2$-action with ``maximal number of isolated fixed points'' ({\it i.e.}, with only isolated fixed points such that $\dim_k (\oplus_i H^i(M;k)) =|M^{\mathbb{Z}_2}|, k = \mathbb{F}_2)$ on a $3$-dimensional, closed manifold determines a binary self-dual code of length $=|M^{\mathbb{Z}_2}|$. In turn this code determines the cohomology algebra $H^*(M;k)$ and the equivariant cohomology $H^*_{\mathbb{Z}_2}(M;k)$. Hence, from results on binary self-dual codes one gets information about the cohomology type of $3$-manifolds which admit involutions with maximal number of isolated fixed points. In particular, ``most'' cohomology types of closed $3$-manifolds do not admit such involutions. Generalizations of the above result are possible in several directions, {\it e.g.}, one gets that ``most'' cohomology types (over $\mathbb{F}_2)$ of closed $3$-manifolds do not admit a non-trivial involution.

In this paper, we consider the (essential) spectrum of the discrete Laplacian of an infinite graph. We introduce a new quantity for an infinite graph, in terms of which we give new lower bound estimates of the (essential) spectrum and give also upper bound estimates when the infinite graph is bipartite. We give sharp estimates of the (essential) spectrum for several examples of infinite graphs.

The semi-affine Coxeter-Dynkin graph is introduced, generalizing both the affine and the finite types.

In an earlier paper~\cite{stinmar}, we studied a generalized Rao bound for ordered orthogonal arrays and $(T,M,S)$-nets. In this paper, we extend this to a coding-theoretic approach to ordered orthogonal arrays. Using a certain association scheme, we prove a MacWilliams-type theorem for linear ordered orthogonal arrays and linear ordered codes as well as a linear programming bound for the general case. We include some tables which compare this bound against two previously known bounds for ordered orthogonal arrays. Finally we show that, for even strength, the LP bound is always at least as strong as the generalized Rao bound.

In this paper, we solve the isomorphism problem for metacirculant graphs of order $pq$ that are not circulant. To solve this problem, we first extend Babai's characterization of the CI-property to non-Cayley vertex-transitive hypergraphs. Additionally, we find a simple characterization of metacirculant Cayley graphs of order $pq$, and exactly determine the full isomorphism classes of circulant graphs of order $pq$.

Let $X$ be a graph with vertex set $V$ and let $A$ be its adjacency matrix. If $E$ is the matrix representing orthogonal projection onto an eigenspace of $A$ with dimension $m$, then $E$ is positive semi-definite. Hence it is the Gram matrix of a set of $|V|$ vectors in $\re^m$. We call the convex hull of a such a set of vectors an eigenpolytope of $X$. The connection between the properties of this polytope and the graph is strongest when $X$ is distance regular and, in this case, it is most natural to consider the eigenpolytope associated to the second largest eigenvalue of $A$. The main result of this paper is the characterisation of those distance regular graphs $X$ for which the $1$-skeleton of this eigenpolytope is isomorphic to $X$.

We study the coordinate rings~$k[\Cmubar\cap\hbox{\Frakvii t}]$ of scheme-theoretic intersections of nilpotent orbit closures with the diagonal matrices. Here $\mu'$ gives the Jordan block structure of the nilpotent matrix. de Concini and Procesi~\cite{deConcini&Procesi} proved a conjecture of Kraft~\cite{Kraft} that these rings are isomorphic to the cohomology rings of the varieties constructed by Springer~\cite{Springer76,Springer78}. The famous $q$-Kostka polynomial~$\Klmt(q)$ is the Hilbert series for the multiplicity of the irreducible symmetric group representation indexed by~$\lambda$ in the ring $k[\Cmubar\cap\hbox{\Frakvii t}]$. \LS~\cite{L&S:Plaxique,Lascoux} gave combinatorially a decomposition of~$\Klmt(q)$ as a sum of ``atomic'' polynomials with non-negative integer coefficients, and Lascoux proposed a corresponding decomposition in the cohomology model. Our work provides a geometric interpretation of the atomic decomposition. The Frobenius-splitting results of Mehta and van der Kallen~\cite{Mehta&vanderKallen} imply a direct-sum decomposition of the ideals of nilpotent orbit closures, arising from the inclusions of the corresponding sets. We carry out the restriction to the diagonal using a recent theorem of Broer~\cite{Broer}. This gives a direct-sum decomposition of the ideals yielding the $k[\Cmubar\cap \hbox{\Frakvii t}]$, and a new proof of the atomic decomposition of the $q$-Kostka polynomials.

Let $K$ be a convex body in $\ed$ and denote by $\cn$ the set of centroids of $n$ non-overlapping translates of $K$. For $\varrho>0$, assume that the parallel body $\cocn+\varrho K$ of $\cocn$ has minimal volume. The notion of parametric density (see~\cite{Wil93}) provides a bridge between finite and infinite packings (see~\cite{BHW94} or~\cite{Hen}). It is known that there exists a maximal $\varrho_s(K)\geq 1/(32d^2)$ such that $\cocn$ is a segment for $\varrho<\varrho_s$ (see~\cite{BHW95}). We prove the existence of a minimal $\varrho_c(K)\leq d+1$ such that if $\varrho>\varrho_c$ and $n$ is large then the shape of $\cocn$ can not be too far from the shape of $K$. For $d=2$, we verify that $\varrho_s=\varrho_c$. For $d\geq 3$, we present the first example of a convex body with known $\varrho_s$ and $\varrho_c$; namely, we have $\varrho_s=\varrho_c=1$ for the parallelotope.

Iwahori-Hecke algebras for the infinite series of complex reflection groups $G(r,p,n)$ were constructed recently in the work of Ariki and Koike~\cite{AK}, Brou\'e and Malle \cite{BM}, and Ariki~\cite{Ari}. In this paper we give Murnaghan-Nakayama type formulas for computing the irreducible characters of these algebras. Our method is a generalization of that in our earlier paper ~\cite{HR} in which we derived Murnaghan-Nakayama rules for the characters of the Iwahori-Hecke algebras of the classical Weyl groups. In both papers we have been motivated by C. Greene~\cite{Gre}, who gave a new derivation of the Murnaghan-Nakayama formula for irreducible symmetric group characters by summing diagonal matrix entries in Young's seminormal representations. We use the analogous representations of the Iwahori-Hecke algebra of $G(r,p,n)$ given by Ariki and Koike~\cite{AK} and Ariki ~\cite{Ari}.

Pieri's formula describes the intersection product of a Schubert cycle by a special Schubert cycle on a Grassmannian. We present a new geometric proof, exhibiting an explicit chain of rational equivalences from a suitable sum of distinct Schubert cycles to the intersection of a Schubert cycle with a special Schubert cycle. The geometry of these rational equivalences indicates a link to a combinatorial proof of Pieri's formula using Schensted insertion.