Expand all Collapse all | Results 26 - 50 of 58 |
26. CJM 2008 (vol 60 pp. 266)
Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables 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.
Categories:16W30, 05A18;, 05E10 |
27. CJM 2008 (vol 60 pp. 297)
Transitive Factorizations in the Hyperoctahedral Group 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.
Categories:05A15, 14H10, 58D29 |
28. CJM 2008 (vol 60 pp. 64)
Classification of Linear Weighted Graphs Up to Blowing-Up and Blowing-Down We classify linear weighted graphs up to the
blowing-up and blowing-down operations which are relevant for the
study of algebraic surfaces.
Keywords:weighted graph, dual graph, blowing-up, algebraic surface Categories:14J26, 14E07, 14R05, 05C99 |
29. CJM 2007 (vol 59 pp. 828)
Non-Backtracking Random Walks and Cogrowth of Graphs 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.
Keywords:graph, oriented line grap, covering tree, random walk, cogrowth, amenability Categories:05C75, 60G50, 20F69 |
30. CJM 2007 (vol 59 pp. 225)
Harmonic Analysis on Metrized Graphs This paper studies the Laplacian operator on a metrized graph, and its
spectral theory.
Keywords:metrized graph, harmonic analysis, eigenfunction Categories:43A99, 58C40, 05C99 |
31. CJM 2007 (vol 59 pp. 36)
Classification of Ding's Schubert Varieties: Finer Rook Equivalence 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.
Keywords:Schubert variety, rook placement, Ferrers board, flag manifold, cohomology ring, nilpotence Categories:14M15, 05E05 |
32. CJM 2006 (vol 58 pp. 1026)
Karamata Renewed and Local Limit Results 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.
Categories:30B10, 30E15, 41A60, 60J35, 05A16 |
33. CJM 2005 (vol 57 pp. 82)
Jordan Structures of Totally Nonnegative Matrices 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.
Keywords:totally nonnegative matrices, planar diagrams,, principal rank, Jordan canonical form Categories:15A21, 15A48, 05C38 |
34. CJM 2004 (vol 56 pp. 871)
Lie Elements and Knuth Relations 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.
Keywords:symmetric group, descent set, coplactic relation, Hopf algebra,, convolution product Categories:17B01, 05E10, 20C30, 16W30 |
35. CJM 2002 (vol 54 pp. 1086)
Combinatorics of the Heat Trace on Spheres 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].
Categories:05A19, 58J35 |
36. CJM 2002 (vol 54 pp. 757)
Strongly Projective Graphs 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$.
Categories:05C15, 06A99 |
37. CJM 2002 (vol 54 pp. 795)
Structure Theory of Totally Disconnected Locally Compact Groups via Graphs and Permutations 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.
Keywords:totally disconnected locally compact groups, scale function, permutation groups, groups acting on graphs Categories:22D05, 20B07, 20B27, 05C25 |
38. CJM 2002 (vol 54 pp. 239)
Elementary Symmetric Polynomials in Numbers of Modulus $1$ 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$.
Categories:05E05, 33C45, 30C15, 51E24 |
39. CJM 2001 (vol 53 pp. 696)
Avoiding Patterns in the Abelian Sense 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.
Categories:05, 68 |
40. CJM 2001 (vol 53 pp. 758)
Inequivalent Transitive Factorizations into Transpositions 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.
Keywords:transitive, transposition, factorization, commutation, cut-and-join Categories:05C38, 15A15, 05A15, 15A18 |
41. CJM 2001 (vol 53 pp. 212)
Group Actions and Codes 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.
Keywords:Involutions, $3$-manifolds, codes Categories:55M35, 57M60, 94B05, 05E20 |
42. CJM 2000 (vol 52 pp. 1057)
The Spectrum of an Infinite Graph 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.
Keywords:infinite graph, discrete Laplacian, spectrum, essential spectrum Categories:05C50, 58G25 |
43. CJM 1999 (vol 51 pp. 1226)
Semi-Affine Coxeter-Dynkin Graphs and $G \subseteq \SU_2(C)$ The semi-affine Coxeter-Dynkin graph is introduced, generalizing
both the affine and the finite types.
Categories:20C99, 05C25, 14B05 |
44. CJM 1999 (vol 51 pp. 326)
Association Schemes for Ordered Orthogonal Arrays and $(T,M,S)$-Nets 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.
Categories:05B15, 05E30, 65C99 |
45. CJM 1998 (vol 50 pp. 1176)
Isomorphism problem for metacirculant graphs of order a product of distinct primes 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$.
Categories:05, 20 |
46. CJM 1998 (vol 50 pp. 739)
Eigenpolytopes of distance regular graphs 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$.
Categories:05E30, 05C50 |
47. CJM 1998 (vol 50 pp. 525)
Nilpotent orbit varieties and the atomic decomposition of the $q$-Kostka polynomials 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.
Keywords:$q$-Kostka polynomials, atomic decomposition, nilpotent conjugacy classes, nilpotent orbit varieties Categories:05E10, 14M99, 20G05, 05E15 |
48. CJM 1998 (vol 50 pp. 16)
Asymptotic shape of finite packings 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.
Categories:52C17, 05B40 |
49. CJM 1998 (vol 50 pp. 167)
Murnaghan-Nakayama rules for characters of Iwahori-Hecke algebras of the complex reflection groups $G(r,p,n)$ |
Murnaghan-Nakayama rules for characters of Iwahori-Hecke algebras of the complex reflection groups $G(r,p,n)$ 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}.
Categories:20C05, 05E05 |
50. CJM 1997 (vol 49 pp. 1281)
Pieri's formula via explicit rational equivalence 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.
Keywords:Pieri's formula, rational equivalence, Grassmannian, Schensted insertion Categories:14M15, 05E10 |