Canadian Mathematical Society
Canadian Mathematical Society
  location:  Publicationsjournals
Search results

Search: MSC category 05 ( Combinatorics )

  Expand all        Collapse all Results 51 - 61 of 61

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

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

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

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

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

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

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

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

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

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

61. 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, 2015 :