Canadian Mathematical Society
Canadian Mathematical Society
  location:  Publicationsjournals
Search results

Search: MSC category 05 ( Combinatorics )

  Expand all        Collapse all Results 1 - 25 of 59

1. CJM Online first

Mohar, Bojan; Skoda, Petr
Obstructions of Connectivity 2 for Embedding Graphs into the Torus
The complete set of minimal obstructions for embedding graphs into the torus is still not determined. In this paper, we present all obstructions for the torus of connectivity 2. Furthermore, we describe the building blocks of obstructions of connectivity 2 for any orientable surface.

Keywords:torus, obstruction, minor, connectivity 2
Categories:05C10, 05C83

2. CJM 2013 (vol 65 pp. 1287)

Reihani, Kamran
$K$-theory of Furstenberg Transformation Group $C^*$-algebras
The paper studies the $K$-theoretic invariants of the crossed product $C^{*}$-algebras associated with an important family of homeomorphisms of the tori $\mathbb{T}^{n}$ called Furstenberg transformations. Using the Pimsner-Voiculescu theorem, we prove that given $n$, the $K$-groups of those crossed products, whose corresponding $n\times n$ integer matrices are unipotent of maximal degree, always have the same rank $a_{n}$. We show using the theory developed here that a claim made in the literature about the torsion subgroups of these $K$-groups is false. Using the representation theory of the simple Lie algebra $\frak{sl}(2,\mathbb{C})$, we show that, remarkably, $a_{n}$ has a combinatorial significance. For example, every $a_{2n+1}$ is just the number of ways that $0$ can be represented as a sum of integers between $-n$ and $n$ (with no repetitions). By adapting an argument of van Lint (in which he answered a question of Erdős), a simple, explicit formula for the asymptotic behavior of the sequence $\{a_{n}\}$ is given. Finally, we describe the order structure of the $K_{0}$-groups of an important class of Furstenberg crossed products, obtaining their complete Elliott invariant using classification results of H. Lin and N. C. Phillips.

Keywords:$K$-theory, transformation group $C^*$-algebra, Furstenberg transformation, Anzai transformation, minimal homeomorphism, positive cone, minimal homeomorphism
Categories:19K14, 19K99, 46L35, 46L80, , 05A15, 05A16, 05A17, 15A36, 17B10, 17B20, 37B05, 54H20

3. CJM 2013 (vol 66 pp. 525)

Berg, Chris; Bergeron, Nantel; Saliola, Franco; Serrano, Luis; Zabrocki, Mike
A Lift of the Schur and Hall-Littlewood Bases to Non-commutative Symmetric Functions
We introduce a new basis of the algebra of non-commutative symmetric functions whose images under the forgetful map are Schur functions when indexed by a partition. Dually, we build a basis of the quasi-symmetric functions which expand positively in the fundamental quasi-symmetric functions. We then use the basis to construct a non-commutative lift of the Hall-Littlewood symmetric functions with similar properties to their commutative counterparts.

Keywords:Hall-Littlewood polynomial, symmetric function, quasisymmetric function, tableau

4. CJM 2013 (vol 65 pp. 843)

Jonsson, Jakob
3-torsion in the Homology of Complexes of Graphs of Bounded Degree
For $\delta \ge 1$ and $n \ge 1$, consider the simplicial complex of graphs on $n$ vertices in which each vertex has degree at most $\delta$; we identify a given graph with its edge set and admit one loop at each vertex. This complex is of some importance in the theory of semigroup algebras. When $\delta = 1$, we obtain the matching complex, for which it is known that there is $3$-torsion in degree $d$ of the homology whenever $\frac{n-4}{3} \le d \le \frac{n-6}{2}$. This paper establishes similar bounds for $\delta \ge 2$. Specifically, there is $3$-torsion in degree $d$ whenever $\frac{(3\delta-1)n-8}{6} \le d \le \frac{\delta (n-1) - 4}{2}$. The procedure for detecting torsion is to construct an explicit cycle $z$ that is easily seen to have the property that $3z$ is a boundary. Defining a homomorphism that sends $z$ to a non-boundary element in the chain complex of a certain matching complex, we obtain that $z$ itself is a non-boundary. In particular, the homology class of $z$ has order $3$.

Keywords:simplicial complex, simplicial homology, torsion group, vertex degree
Categories:05E45, 55U10, 05C07, 20K10

5. CJM 2013 (vol 66 pp. 205)

Iovanov, Miodrag Cristian
Generalized Frobenius Algebras and Hopf Algebras
"Co-Frobenius" coalgebras were introduced as dualizations of Frobenius algebras. We previously showed that they admit left-right symmetric characterizations analogue to those of Frobenius algebras. We consider the more general quasi-co-Frobenius (QcF) coalgebras; the first main result in this paper is that these also admit symmetric characterizations: a coalgebra is QcF if it is weakly isomorphic to its (left, or right) rational dual $Rat(C^*)$, in the sense that certain coproduct or product powers of these objects are isomorphic. Fundamental results of Hopf algebras, such as the equivalent characterizations of Hopf algebras with nonzero integrals as left (or right) co-Frobenius, QcF, semiperfect or with nonzero rational dual, as well as the uniqueness of integrals and a short proof of the bijectivity of the antipode for such Hopf algebras all follow as a consequence of these results. This gives a purely representation theoretic approach to many of the basic fundamental results in the theory of Hopf algebras. Furthermore, we introduce a general concept of Frobenius algebra, which makes sense for infinite dimensional and for topological algebras, and specializes to the classical notion in the finite case. This will be a topological algebra $A$ that is isomorphic to its complete topological dual $A^\vee$. We show that $A$ is a (quasi)Frobenius algebra if and only if $A$ is the dual $C^*$ of a (quasi)co-Frobenius coalgebra $C$. We give many examples of co-Frobenius coalgebras and Hopf algebras connected to category theory, homological algebra and the newer q-homological algebra, topology or graph theory, showing the importance of the concept.

Keywords:coalgebra, Hopf algebra, integral, Frobenius, QcF, co-Frobenius
Categories:16T15, 18G35, 16T05, 20N99, 18D10, 05E10

6. CJM 2012 (vol 65 pp. 863)

Josuat-Vergès, Matthieu
Cumulants of the $q$-semicircular Law, Tutte Polynomials, and Heaps
The $q$-semicircular distribution is a probability law that interpolates between the Gaussian law and the semicircular law. There is a combinatorial interpretation of its moments in terms of matchings where $q$ follows the number of crossings, whereas for the free cumulants one has to restrict the enumeration to connected matchings. The purpose of this article is to describe combinatorial properties of the classical cumulants. We show that like the free cumulants, they are obtained by an enumeration of connected matchings, the weight being now an evaluation of the Tutte polynomial of a so-called crossing graph. The case $q=0$ of these cumulants was studied by Lassalle using symmetric functions and hypergeometric series. We show that the underlying combinatorics is explained through the theory of heaps, which is Viennot's geometric interpretation of the Cartier-Foata monoid. This method also gives a general formula for the cumulants in terms of free cumulants.

Keywords:moments, cumulants, matchings, Tutte polynomials, heaps
Categories:05A18, 05C31, 46L54

7. CJM 2012 (vol 65 pp. 1020)

Goulden, I. P.; Guay-Paquet, Mathieu; Novak, Jonathan
Monotone Hurwitz Numbers in Genus Zero
Hurwitz numbers count branched covers of the Riemann sphere with specified ramification data, or equivalently, transitive permutation factorizations in the symmetric group with specified cycle types. Monotone Hurwitz numbers count a restricted subset of these branched covers related to the expansion of complete symmetric functions in the Jucys-Murphy elements, and have arisen in recent work on the the asymptotic expansion of the Harish-Chandra-Itzykson-Zuber integral. In this paper we begin a detailed study of monotone Hurwitz numbers. We prove two results that are reminiscent of those for classical Hurwitz numbers. The first is the monotone join-cut equation, a partial differential equation with initial conditions that characterizes the generating function for monotone Hurwitz numbers in arbitrary genus. The second is our main result, in which we give an explicit formula for monotone Hurwitz numbers in genus zero.

Keywords:Hurwitz numbers, matrix models, enumerative geometry
Categories:05A15, 14E20, 15B52

8. CJM 2012 (vol 65 pp. 222)

Sauer, N. W.
Distance Sets of Urysohn Metric Spaces
A metric space $\mathrm{M}=(M;\operatorname{d})$ is {\em homogeneous} if for every isometry $f$ of a finite subspace of $\mathrm{M}$ to a subspace of $\mathrm{M}$ there exists an isometry of $\mathrm{M}$ onto $\mathrm{M}$ extending $f$. The space $\mathrm{M}$ is {\em universal} if it isometrically embeds every finite metric space $\mathrm{F}$ with $\operatorname{dist}(\mathrm{F})\subseteq \operatorname{dist}(\mathrm{M})$. (With $\operatorname{dist}(\mathrm{M})$ being the set of distances between points in $\mathrm{M}$.) A metric space $\boldsymbol{U}$ is an {\em Urysohn} metric space if it is homogeneous, universal, separable and complete. (It is not difficult to deduce that an Urysohn metric space $\boldsymbol{U}$ isometrically embeds every separable metric space $\mathrm{M}$ with $\operatorname{dist}(\mathrm{M})\subseteq \operatorname{dist}(\boldsymbol{U})$.) The main results are: (1) A characterization of the sets $\operatorname{dist}(\boldsymbol{U})$ for Urysohn metric spaces $\boldsymbol{U}$. (2) If $R$ is the distance set of an Urysohn metric space and $\mathrm{M}$ and $\mathrm{N}$ are two metric spaces, of any cardinality with distances in $R$, then they amalgamate disjointly to a metric space with distances in $R$. (3) The completion of every homogeneous, universal, separable metric space $\mathrm{M}$ is homogeneous.

Keywords:partitions of metric spaces, Ramsey theory, metric geometry, Urysohn metric space, oscillation stability
Categories:03E02, 22F05, 05C55, 05D10, 22A05, 51F99

9. CJM 2012 (vol 65 pp. 241)

Aguiar, Marcelo; Lauve, Aaron
Lagrange's Theorem for Hopf Monoids in Species
Following Radford's proof of Lagrange's theorem for pointed Hopf algebras, we prove Lagrange's theorem for Hopf monoids in the category of connected species. As a corollary, we obtain necessary conditions for a given subspecies $\mathbf k$ of a Hopf monoid $\mathbf h$ to be a Hopf submonoid: the quotient of any one of the generating series of $\mathbf h$ by the corresponding generating series of $\mathbf k$ must have nonnegative coefficients. Other corollaries include a necessary condition for a sequence of nonnegative integers to be the dimension sequence of a Hopf monoid in the form of certain polynomial inequalities, and of a set-theoretic Hopf monoid in the form of certain linear inequalities. The latter express that the binomial transform of the sequence must be nonnegative.

Keywords:Hopf monoids, species, graded Hopf algebras, Lagrange's theorem, generating series, Poincaré-Birkhoff-Witt theorem, Hopf kernel, Lie kernel, primitive element, partition, composition, linear order, cyclic order, derangement
Categories:05A15, 05A20, 05E99, 16T05, 16T30, 18D10, 18D35

10. CJM 2011 (vol 64 pp. 1090)

Rosso, Daniele
Classic and Mirabolic Robinson-Schensted-Knuth Correspondence for Partial Flags
In this paper we first generalize to the case of partial flags a result proved both by Spaltenstein and by Steinberg that relates the relative position of two complete flags and the irreducible components of the flag variety in which they lie, using the Robinson-Schensted-Knuth correspondence. Then we use this result to generalize the mirabolic Robinson-Schensted-Knuth correspondence defined by Travkin, to the case of two partial flags and a line.

Keywords:partial flag varieties, RSK correspondence
Categories:14M15, 05A05

11. CJM 2011 (vol 64 pp. 1201)

Aistleitner, Christoph; Elsholtz, Christian
The Central Limit Theorem for Subsequences in Probabilistic Number Theory
Let $(n_k)_{k \geq 1}$ be an increasing sequence of positive integers, and let $f(x)$ be a real function satisfying \begin{equation} \tag{1} f(x+1)=f(x), \qquad \int_0^1 f(x) ~dx=0,\qquad \operatorname{Var_{[0,1]}} f \lt \infty. \end{equation} If $\lim_{k \to \infty} \frac{n_{k+1}}{n_k} = \infty$ the distribution of \begin{equation} \tag{2} \frac{\sum_{k=1}^N f(n_k x)}{\sqrt{N}} \end{equation} converges to a Gaussian distribution. In the case $$ 1 \lt \liminf_{k \to \infty} \frac{n_{k+1}}{n_k}, \qquad \limsup_{k \to \infty} \frac{n_{k+1}}{n_k} \lt \infty $$ there is a complex interplay between the analytic properties of the function $f$, the number-theoretic properties of $(n_k)_{k \geq 1}$, and the limit distribution of (2). In this paper we prove that any sequence $(n_k)_{k \geq 1}$ satisfying $\limsup_{k \to \infty} \frac{n_{k+1}}{n_k} = 1$ contains a nontrivial subsequence $(m_k)_{k \geq 1}$ such that for any function satisfying (1) the distribution of $$ \frac{\sum_{k=1}^N f(m_k x)}{\sqrt{N}} $$ converges to a Gaussian distribution. This result is best possible: for any $\varepsilon\gt 0$ there exists a sequence $(n_k)_{k \geq 1}$ satisfying $\limsup_{k \to \infty} \frac{n_{k+1}}{n_k} \leq 1 + \varepsilon$ such that for every nontrivial subsequence $(m_k)_{k \geq 1}$ of $(n_k)_{k \geq 1}$ the distribution of (2) does not converge to a Gaussian distribution for some $f$. Our result can be viewed as a Ramsey type result: a sufficiently dense increasing integer sequence contains a subsequence having a certain requested number-theoretic property.

Keywords:central limit theorem, lacunary sequences, linear Diophantine equations, Ramsey type theorem
Categories:60F05, 42A55, 11D04, 05C55, 11K06

12. CJM 2011 (vol 64 pp. 1359)

Nozaki, Hiroshi; Sawa, Masanori
Note on Cubature Formulae and Designs Obtained from Group Orbits
In 1960, Sobolev proved that for a finite reflection group $G$, a $G$-invariant cubature formula is of degree $t$ if and only if it is exact for all $G$-invariant polynomials of degree at most $t$. In this paper, we find some observations on invariant cubature formulas and Euclidean designs in connection with the Sobolev theorem. First, we give an alternative proof of theorems by Xu (1998) on necessary and sufficient conditions for the existence of cubature formulas with some strong symmetry. The new proof is shorter and simpler compared to the original one by Xu, and moreover gives a general interpretation of the analytically-written conditions of Xu's theorems. Second, we extend a theorem by Neumaier and Seidel (1988) on Euclidean designs to invariant Euclidean designs, and thereby classify tight Euclidean designs obtained from unions of the orbits of the corner vectors. This result generalizes a theorem of Bajnok (2007) which classifies tight Euclidean designs invariant under the Weyl group of type $B$ to other finite reflection groups.

Keywords:cubature formula, Euclidean design, radially symmetric integral, reflection group, Sobolev theorem
Categories:65D32, 05E99, 51M99

13. CJM 2011 (vol 64 pp. 822)

Haglund, J.; Morse, J.; Zabrocki, M.
A Compositional Shuffle Conjecture Specifying Touch Points of the Dyck Path
We introduce a $q,t$-enumeration of Dyck paths that are forced to touch the main diagonal at specific points and forbidden to touch elsewhere and conjecture that it describes the action of the Macdonald theory $\nabla$ operator applied to a Hall--Littlewood polynomial. Our conjecture refines several earlier conjectures concerning the space of diagonal harmonics including the ``shuffle conjecture" (Duke J. Math. $\mathbf {126}$ ($2005$), 195-232) for $\nabla e_n[X]$. We bring to light that certain generalized Hall--Littlewood polynomials indexed by compositions are the building blocks for the algebraic combinatorial theory of $q,t$-Catalan sequences, and we prove a number of identities involving these functions.

Keywords:Dyck Paths, Parking functions, Hall--Littlewood symmetric functions
Categories:05E05, 33D52

14. CJM 2011 (vol 63 pp. 1254)

D'Azevedo, Antonio Breda; Jones, Gareth A.; Schulte, Egon
Constructions of Chiral Polytopes of Small Rank
An abstract polytope of rank $n$ is said to be chiral if its automorphism group has precisely two orbits on the flags, such that adjacent flags belong to distinct orbits. This paper describes a general method for deriving new finite chiral polytopes from old finite chiral polytopes of the same rank. In particular, the technique is used to construct many new examples in ranks $3$, $4$, and $5$.

Keywords:abstract regular polytope, chiral polytope, chiral maps
Categories:51M20, 52B15, 05C25

15. CJM 2010 (vol 62 pp. 1228)

Ardila, Federico; Fink, Alex; Rincón, Felipe
Valuations for Matroid Polytope Subdivisions
We prove that the ranks of the subsets and the activities of the bases of a matroid define valuations for the subdivisions of a matroid polytope into smaller matroid polytopes.

Categories:05B35, 52B40, 52B45, 52C22

16. CJM 2010 (vol 62 pp. 1058)

Chen, Yichao; Liu, Yanpei
On a Conjecture of S. Stahl
S. Stahl conjectured that the zeros of genus polynomials are real. In this note, we disprove this conjecture.

Keywords:genus polynomial, zeros, real

17. CJM 2009 (vol 62 pp. 355)

Král', Daniel; Máčajová, Edita; Pór, Attila; Sereni, Jean-Sébastien
Characterisation Results for Steiner Triple Systems and Their Application to Edge-Colourings of Cubic Graphs
It is known that a Steiner triple system is projective if and only if it does not contain the four-triple configuration $C_{14}$. We find three configurations such that a Steiner triple system is affine if and only if it does not contain one of these configurations. Similarly, we characterise Hall triple systems using two forbidden configurations. Our characterisations have several interesting corollaries in the area of edge-colourings of graphs. A cubic graph G is S-edge-colourable for a Steiner triple system S if its edges can be coloured with points of S in such a way that the points assigned to three edges sharing a vertex form a triple in S. Among others, we show that all cubic graphs are S-edge-colourable for every non-projective non-affine point-transitive Steiner triple system S.

Categories:05B07, 05C15

18. CJM 2009 (vol 61 pp. 1300)

Hubard, Isabel; Orbani\'c, Alen; Weiss, Asia Ivi\'c
Monodromy Groups and Self-Invariance
For every polytope $\mathcal{P}$ there is the universal regular polytope of the same rank as $\mathcal{P}$ corresponding to the Coxeter group $\mathcal{C} =[\infty, \dots, \infty]$. For a given automorphism $d$ of $\mathcal{C}$, using monodromy groups, we construct a combinatorial structure $\mathcal{P}^d$. When $\mathcal{P}^d$ is a polytope isomorphic to $\mathcal{P}$ we say that $\mathcal{P}$ is self-invariant with respect to $d$, or $d$-invariant. We develop algebraic tools for investigating these operations on polytopes, and in particular give a criterion on the existence of a $d$\nobreakdash-auto\-morphism of a given order. As an application, we analyze properties of self-dual edge-transitive polyhedra and polyhedra with two flag-orbits. We investigate properties of medials of such polyhedra. Furthermore, we give an example of a self-dual equivelar polyhedron which contains no polarity (duality of order 2). We also extend the concept of Petrie dual to higher dimensions, and we show how it can be dealt with using self-invariance.

Keywords:maps, abstract polytopes, self-duality, monodromy groups, medials of polyhedra
Categories:51M20, 05C25, 05C10, 05C30, 52B70

19. CJM 2009 (vol 61 pp. 1092)

Irving, John
Minimal Transitive Factorizations of Permutations into Cycles
We introduce a new approach to an enumerative problem closely linked with the geometry of branched coverings, that is, we study the number $H_{\alpha}(i_2,i_3,\dots)$ of ways a given permutation (with cycles described by the partition $\a$) can be decomposed into a product of exactly $i_2$ 2-cycles, $i_3$ 3-cycles, \emph{etc.}, with certain minimality and transitivity conditions imposed on the factors. The method is to encode such factorizations as planar maps with certain \emph{descent structure} and apply a new combinatorial decomposition to make their enumeration more manageable. We apply our technique to determine $H_{\alpha}(i_2,i_3,\dots)$ when $\a$ has one or two parts, extending earlier work of Goulden and Jackson. We also show how these methods are readily modified to count \emph{inequivalent} factorizations, where equivalence is defined by permitting commutations of adjacent disjoint factors. Our technique permits us to generalize recent work of Goulden, Jackson, and Latour, while allowing for a considerable simplification of their analysis.

Categories:05A15, 05E10

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

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

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

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

24. CJM 2008 (vol 60 pp. 1108)

Lopez-Abad, J.; Manoussakis, A.
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

25. CJM 2008 (vol 60 pp. 960)

   1 2 3    

© Canadian Mathematical Society, 2014 :