Canadian Mathematical Society
Canadian Mathematical Society
  location:  Publicationsjournals
Search results

Search: MSC category 05 ( Combinatorics )

  Expand all        Collapse all Results 51 - 73 of 73

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

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, cut-and-join
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 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

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)

McKay, John
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

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

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

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

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

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

64. CJM 1998 (vol 50 pp. 167)

Halverson, Tom; Ram, Arun
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

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)

Okounkov, Andrei
Proof of a conjecture of Goulden and Jackson
We prove an integration formula involving Jack polynomials conjectured by I.~P.~Goulden and D.~M.~Jackson in connection with enumeration of maps in surfaces.

Categories:05E05, 43A85, 57M15

68. CJM 1997 (vol 49 pp. 641)

Burris, Stanley; Compton, Kevin; Odlyzko, Andrew; Richmond, Bruce
Fine spectra and limit laws II First-order 0--1 laws.
Using Feferman-Vaught techniques a condition on the fine spectrum of an admissible class of structures is found which leads to a first-order 0--1 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 first-order 0--1 law. If the condition is satisfied (and hence we have a first-order %% 0--1 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. First-order laws
Using Feferman-Vaught techniques we show a certain property of the fine spectrum of an admissible class of structures leads to a first-order 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 first-order 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 Gessel-Viennot 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 well-defined 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
   1 2 3    

© Canadian Mathematical Society, 2018 :