51. CJM 2002 (vol 54 pp. 757)
 Larose, Benoit

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 

52. CJM 2002 (vol 54 pp. 795)
 Möller, Rögnvaldur G.

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 selfcontained 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 

53. CJM 2002 (vol 54 pp. 239)
 Cartwright, Donald I.; Steger, Tim

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 

54. CJM 2001 (vol 53 pp. 696)
 Currie, J.; Linek, V.

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 

55. CJM 2001 (vol 53 pp. 758)
 Goulden, I. P.; Jackson, D. M.; Latour, F. G.

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, cutandjoin Categories:05C38, 15A15, 05A15, 15A18 

56. CJM 2001 (vol 53 pp. 212)
 Puppe, V.

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 selfdual
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 selfdual
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 nontrivial involution.
Keywords:Involutions, $3$manifolds, codes Categories:55M35, 57M60, 94B05, 05E20 

57. CJM 2000 (vol 52 pp. 1057)
 Urakawa, Hajime

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 

58. CJM 1999 (vol 51 pp. 1226)
59. CJM 1999 (vol 51 pp. 326)
 Martin, W. J.; Stinson, D. R.

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 codingtheoretic approach to ordered orthogonal
arrays. Using a certain association
scheme, we prove a MacWilliamstype 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 

60. CJM 1998 (vol 50 pp. 1176)
 Dobson, Edward

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 CIproperty to
nonCayley vertextransitive 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 

61. CJM 1998 (vol 50 pp. 739)
 Godsil, C. D.

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 semidefinite. 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 

62. CJM 1998 (vol 50 pp. 525)
 Brockman, William; Haiman, Mark

Nilpotent orbit varieties and the atomic decomposition of the $q$Kostka polynomials
We study the coordinate rings~$k[\Cmubar\cap\hbox{\Frakvii t}]$ of
schemetheoretic
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
nonnegative integer coefficients, and Lascoux proposed a
corresponding decomposition in the cohomology model.
Our work provides a geometric interpretation of the atomic
decomposition. The Frobeniussplitting results of Mehta and van der
Kallen~\cite{Mehta&vanderKallen} imply a directsum 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 directsum
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 

63. CJM 1998 (vol 50 pp. 16)
 Böröczky, Károly; Schnell, Uwe

Asymptotic shape of finite packings
Let $K$ be a convex body in $\ed$ and denote by $\cn$
the set of centroids of $n$ nonoverlapping 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 

64. CJM 1998 (vol 50 pp. 167)
 Halverson, Tom; Ram, Arun

MurnaghanNakayama rules for characters of IwahoriHecke algebras of the complex reflection groups $G(r,p,n)$
IwahoriHecke 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
MurnaghanNakayama 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
MurnaghanNakayama rules for the characters of the
IwahoriHecke 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 MurnaghanNakayama formula for irreducible symmetric
group characters by summing diagonal matrix entries in Young's
seminormal representations. We use the analogous representations
of the IwahoriHecke algebra of $G(r,p,n)$ given by Ariki and
Koike~\cite{AK} and Ariki ~\cite{Ari}.
Categories:20C05, 05E05 

65. CJM 1997 (vol 49 pp. 1281)
 Sottile, Frank

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 

66. CJM 1997 (vol 49 pp. 865)
 Goulden, I. P.; Jackson, D. M.

Maps in locally orientable surfaces and integrals over real symmetric surfaces
The genus series for maps is the generating series for the
number of rooted maps with a given number of vertices and
faces of each degree, and a given number of edges. It captures
topological information about surfaces, and appears in questions
arising in statistical mechanics, topology, group rings,
and certain aspects of free probability theory. An expression
has been given previously for the genus series for maps in
locally orientable surfaces in terms of zonal polynomials. The
purpose of this paper is to derive an integral representation
for the genus series. We then show how this can be used in
conjunction with integration techniques to determine the genus
series for monopoles in locally orientable surfaces. This
complements the analogous result for monopoles in orientable
surfaces previously obtained by Harer and Zagier. A conjecture,
subsequently proved by Okounkov, is given for the evaluation
of an expectation operator acting on the Jack symmetric function.
It specialises to known results for Schur functions and zonal
polynomials.
Categories:05C30, 05A15, 05E05, 15A52 

67. CJM 1997 (vol 49 pp. 883)
68. CJM 1997 (vol 49 pp. 641)
 Burris, Stanley; Compton, Kevin; Odlyzko, Andrew; Richmond, Bruce

Fine spectra and limit laws II Firstorder 01 laws.
Using FefermanVaught techniques a condition on the fine
spectrum of an admissible class of structures is found
which leads to a firstorder 01 law.
The condition presented is best possible in the
sense that if it is violated then one can find an admissible
class with the same fine spectrum which does not have
a firstorder 01 law.
If the condition is satisfied (and hence we have a firstorder %% 01 law)
Categories:03N45, 11N45, 11N80, 05A15, 05A16, 11M41, 11P81 

69. CJM 1997 (vol 49 pp. 617)
 Stahl, Saul

On the zeros of some genus polynomials
In the genus polynomial of the graph $G$, the coefficient of $x^k$
is the number of distinct embeddings of the graph $G$ on the
oriented surface of genus $k$. It is shown that for several
infinite families of graphs all the zeros of the genus polynomial
are real and negative. This implies that their coefficients, which
constitute the genus distribution of the graph, are log concave and
therefore also unimodal. The geometric distribution of the zeros
of some of these polynomials is also investigated and some new
genus polynomials are presented.
Categories:05C10, 05A15, 30C15, 26C10 

70. CJM 1997 (vol 49 pp. 468)
 Burris, Stanley; Sárközy, András

Fine spectra and limit laws I. Firstorder laws
Using FefermanVaught techniques we show a certain property of the fine
spectrum of an admissible class of structures leads to a firstorder law.
The condition presented is best possible in the sense that if it is
violated then one can find an admissible class with the same fine
spectrum which does not have a firstorder law. We present three
conditions for verifying that the above property actually holds.
The first condition is that the count function of an admissible class
has regular variation with a certain uniformity of convergence. This
applies to a wide range of admissible classes, including those
satisfying Knopfmacher's Axiom A, and those satisfying Bateman
and Diamond's condition.
The second condition is similar to the first condition, but designed
to handle the discrete case, {\it i.e.}, when the sizes of the structures
in an admissible class $K$ are all powers of a single integer. It applies
when either the class of indecomposables or the whole class satisfies
Knopfmacher's Axiom A$^\#$.
The third condition is also for the discrete case, when there is a
uniform bound on the number of $K$indecomposables of any given size.
Keywords:First order limit laws, generalized number theory Categories:O3C13, 11N45, 11N80, 05A15, 05A16, 11M41, 11P81 

71. CJM 1997 (vol 49 pp. 263)
 Hamel, A. M.

Determinantal forms for symplectic and orthogonal Schur functions
Symplectic and orthogonal Schur functions can be defined
combinatorially in a manner similar to the classical Schur functions.
This paper demonstrates that they can also be expressed as determinants.
These determinants are generated using planar decompositions of tableaux
into strips and the equivalence of these determinants to symplectic or
orthogonal Schur functions is established by GesselViennot lattice path
techniques. Results for rational (also called {\it composite}) Schur functions
are also obtained.
Categories:05E05, 05E10, 20C33 

72. CJM 1997 (vol 49 pp. 301)
 Merlini, Donatella; Rogers, Douglas G.; Sprugnoli, Renzo; Verri, M. Cecilia

On some alternative characterizations of Riordan arrays
We give several new characterizations of Riordan Arrays, the most
important of which is: if $\{d_{n,k}\}_{n,k \in {\bf N}}$ is a lower
triangular array whose generic element $d_{n,k}$ linearly depends on
the elements in a welldefined though large area of the array, then
$\{d_{n,k}\}_{n,k \in {\bf N}}$ is Riordan. We also provide some
applications of these characterizations to the lattice path theory.
Categories:05A15, 05C38 

73. CJM 1997 (vol 49 pp. 193)
 Casali, Maria Rita

Classifying PL $5$manifolds by regular genus: the boundary case
In the present paper, we face the problem of classifying classes of
orientable PL $5$manifolds $M^5$ with $h \geq 1$ boundary components,
by making use of a combinatorial invariant called {\it regular genus}
${\cal G}(M^5)$. In particular, a complete classification up to
regular genus five is obtained:
$${\cal G}(M^5) = \gG \leq 5 \Longrightarrow M^5 \cong \#_{\varrho
 \gbG}(\bdo) \# \smo_{\gbG},$$
where $\gbG = {\cal G}(\partial M^5)$ denotes the regular genus of
the boundary $\partial M^5$ and $\smo_{\gbG}$ denotes the connected
sum of $h\geq 1$ orientable $5$dimensional handlebodies
$\cmo_{\alpha_i}$ of genus $\alpha_i\geq 0$
($i=1,\ldots, h$), so that $\sum_{i=1}^h \alpha_i = \gbG.$
\par
Moreover, we give the following characterizations of orientable PL
$5$manifolds $M^5$ with boundary satisfying particular conditions
related to the ``gap'' between ${\cal G}(M^5)$ and either
${\cal G}(\partial M^5)$ or the rank of their fundamental group
$\rk\bigl(\pi_1(M^5)\bigr)$:
$$\displaylines{{\cal G}(\partial M^5)= {\cal G}(M^5)
= \varrho \Longleftrightarrow M^5 \cong \smo_{\gG}\cr
{\cal G}(\partial M^5)= \gbG = {\cal G}(M^5)1 \Longleftrightarrow
M^5 \cong (\bdo) \# \smo_{\gbG}\cr
{\cal G}(\partial M^5)= \gbG = {\cal G}(M^5)2 \Longleftrightarrow
M^5 \cong \#_2 (\bdo) \# \smo_{\gbG}\cr
{\cal G}(M^5) = \rk\bigl(\pi_1(M^5)\bigr)= \varrho \Longleftrightarrow
M^5 \cong \#_{\gG  \gbG}(\bdo) \# \smo_{\gbG}.\cr}$$
\par
Further, the paper explains how the above results (together with
other known properties of regular genus of PL manifolds) may lead
to a combinatorial approach to $3$dimensional Poincar\'e Conjecture.
Categories:57N15, 57Q15, 05C10 
