location:  Publications → journals
Search results

Search: MSC category 05 ( Combinatorics )

 Expand all        Collapse all Results 26 - 50 of 65

26. CJM 2009 (vol 61 pp. 888)

Novik, Isabella; Swartz, Ed
 Face Ring Multiplicity via CM-Connectivity Sequences The multiplicity conjecture of Herzog, Huneke, and Srinivasan is verified for the face rings of the following classes of simplicial complexes: matroid complexes, complexes of dimension one and two, and Gorenstein complexes of dimension at most four. The lower bound part of this conjecture is also established for the face rings of all doubly Cohen--Macaulay complexes whose 1-skeleton's connectivity does not exceed the codimension plus one as well as for all $(d-1)$-dimensional $d$-Cohen--Macaulay complexes. The main ingredient of the proofs is a new interpretation of the minimal shifts in the resolution of the face ring $\field[\Delta]$ via the Cohen--Macaulay connectivity of the skeletons of $\Delta$. Categories:13F55, 52B05;, 13H15;, 13D02;, 05B35

27. CJM 2009 (vol 61 pp. 904)

Saliola, Franco V.
 The Face Semigroup Algebra of a Hyperplane Arrangement This article presents a study of an algebra spanned by the faces of a hyperplane arrangement. The quiver with relations of the algebra is computed and the algebra is shown to be a Koszul algebra. It is shown that the algebra depends only on the intersection lattice of the hyperplane arrangement. A complete system of primitive orthogonal idempotents for the algebra is constructed and other algebraic structure is determined including: a description of the projective indecomposable modules, the Cartan invariants, projective resolutions of the simple modules, the Hochschild homology and cohomology, and the Koszul dual algebra. A new cohomology construction on posets is introduced, and it is shown that the face semigroup algebra is isomorphic to the cohomology algebra when this construction is applied to the intersection lattice of the hyperplane arrangement. Categories:52C35, 05E25, 16S37

28. CJM 2009 (vol 61 pp. 583)

Hajir, Farshid
 Algebraic Properties of a Family of Generalized Laguerre Polynomials We study the algebraic properties of Generalized Laguerre Polynomials for negative integral values of the parameter. For integers $r,n\geq 0$, we conjecture that $L_n^{(-1-n-r)}(x) = \sum_{j=0}^n \binom{n-j+r}{n-j}x^j/j!$ is a $\Q$-irreducible polynomial whose Galois group contains the alternating group on $n$ letters. That this is so for $r=n$ was conjectured in the 1950's by Grosswald and proven recently by Filaseta and Trifonov. It follows from recent work of Hajir and Wong that the conjecture is true when $r$ is large with respect to $n\geq 5$. Here we verify it in three situations: i) when $n$ is large with respect to $r$, ii) when $r \leq 8$, and iii) when $n\leq 4$. The main tool is the theory of $p$-adic Newton Polygons. Categories:11R09, 05E35

29. CJM 2009 (vol 61 pp. 465)

Woodford, Roger
 On Partitions into Powers of Primes and Their Difference Functions In this paper, we extend the approach first outlined by Hardy and Ramanujan for calculating the asymptotic formulae for the number of partitions into $r$-th powers of primes, $p_{\mathbb{P}^{(r)}}(n)$, to include their difference functions. In doing so, we rectify an oversight of said authors, namely that the first difference function is perforce positive for all values of $n$, and include the magnitude of the error term. Categories:05A17, 11P81

30. CJM 2008 (vol 60 pp. 1108)

 A Classification of Tsirelson Type Spaces We give a complete classification of mixed Tsirelson spaces $T[(\mathcal F_i,\theta_i)_{i=1}^{r}]$ for finitely many pairs of given compact and hereditary families $\mathcal F_i$ of finite sets of integers and $0<\theta_i<1$ in terms of the Cantor--Bendixson indices of the families $\mathcal F_i$, and $\theta_i$ ($1\le i\le r$). We prove that there are unique countable ordinal $\alpha$ and $0<\theta<1$ such that every block sequence of $T[(\mathcal F_i,\theta_i)_{i=1}^{r}]$ has a subsequence equivalent to a subsequence of the natural basis of the $T(\mathcal S_{\omega^\alpha},\theta)$. Finally, we give a complete criterion of comparison in between two of these mixed Tsirelson spaces. Categories:46B20, 05D10

31. CJM 2008 (vol 60 pp. 958)

Chen, Yichao
 A Note on a Conjecture of S. Stahl S. Stahl (Canad. J. Math. \textbf{49}(1997), no. 3, 617--640) conjectured that the zeros of genus polynomial are real. L. Liu and Y. Wang disproved this conjecture on the basis of Example 6.7. In this note, it is pointed out that there is an error in this example and a new generating matrix and initial vector are provided. Keywords:genus polynomial, zeros, realCategories:05C10, 05A15, 30C15, 26C10

32. CJM 2008 (vol 60 pp. 960)

Stahl, Saul
 Erratum: On the Zeros of Some Genus Polynomials No abstract. Categories:05C10, 05A15, 30C15, 26C10

33. CJM 2008 (vol 60 pp. 297)

Bini, G.; Goulden, I. P.; Jackson, D. M.
 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

34. CJM 2008 (vol 60 pp. 266)

Bergeron, Nantel; Reutenauer, Christophe; Rosas, Mercedes; Zabrocki, Mike
 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

35. CJM 2008 (vol 60 pp. 64)

Daigle, Daniel
 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 surfaceCategories:14J26, 14E07, 14R05, 05C99

36. CJM 2007 (vol 59 pp. 828)

Ortner, Ronald; Woess, Wolfgang
 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, amenabilityCategories:05C75, 60G50, 20F69

37. CJM 2007 (vol 59 pp. 225)

Baker, Matt; Rumely, Robert
 Harmonic Analysis on Metrized Graphs This paper studies the Laplacian operator on a metrized graph, and its spectral theory. Keywords:metrized graph, harmonic analysis, eigenfunctionCategories:43A99, 58C40, 05C99

38. CJM 2007 (vol 59 pp. 36)

Develin, Mike; Martin, Jeremy L.; Reiner, Victor
 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, nilpotenceCategories:14M15, 05E05

39. CJM 2006 (vol 58 pp. 1026)

Handelman, David
 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

40. CJM 2005 (vol 57 pp. 82)

Fallat, Shaun M.; Gekhtman, Michael I.
 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 formCategories:15A21, 15A48, 05C38

41. CJM 2004 (vol 56 pp. 871)

Schocker, Manfred
 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 productCategories:17B01, 05E10, 20C30, 16W30

42. CJM 2002 (vol 54 pp. 1086)

Polterovich, Iosif
 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

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

44. 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 graphsCategories:22D05, 20B07, 20B27, 05C25

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

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

47. 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-joinCategories:05C38, 15A15, 05A15, 15A18

48. 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, codesCategories:55M35, 57M60, 94B05, 05E20

49. 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 spectrumCategories:05C50, 58G25

50. 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
 Page Previous 1 2 3 Next
 top of page | contact us | privacy | site map |