Expand all Collapse all | Results 1 - 25 of 60 |
1. CJM Online first
A density CorrÃ¡di-Hajnal Theorem We find, for all sufficiently large $n$ and each $k$, the maximum number of edges in an $n$-vertex graph which does not contain $k+1$ vertex-disjoint triangles.
This extends a result of Moon [Canad. J. Math. 20 (1968), 96-102] which is in turn an extension of Mantel's Theorem. Our result can also be viewed as a density version of the CorrÃ¡di-Hajnal Theorem.
Keywords:graph theory, Turan's Theorem, Mantel's Theorem, CorrÃ¡di-Hajnal Theorem, triangle Category:05C35 |
2. CJM 2014 (vol 66 pp. 1327)
Obstructions of Connectivity Two 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 |
3. CJM 2013 (vol 65 pp. 1287)
$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 |
4. CJM 2013 (vol 66 pp. 525)
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 Category:05E05 |
5. CJM 2013 (vol 65 pp. 843)
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 |
6. CJM 2013 (vol 66 pp. 205)
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 |
7. CJM 2012 (vol 65 pp. 863)
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 |
8. CJM 2012 (vol 65 pp. 1020)
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 |
9. CJM 2012 (vol 65 pp. 222)
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 |
10. CJM 2012 (vol 65 pp. 241)
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 |
11. CJM 2011 (vol 64 pp. 1090)
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 |
12. CJM 2011 (vol 64 pp. 1201)
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 |
13. CJM 2011 (vol 64 pp. 1359)
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 |
14. CJM 2011 (vol 64 pp. 822)
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 |
15. CJM 2011 (vol 63 pp. 1254)
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 |
16. CJM 2010 (vol 62 pp. 1228)
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 |
17. CJM 2010 (vol 62 pp. 1058)
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 Category:05C10 |
18. CJM 2009 (vol 62 pp. 355)
Characterisation Results for Steiner Triple Systems and Their Application to Edge-Colourings of Cubic Graphs |
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 |
19. CJM 2009 (vol 61 pp. 1300)
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 |
20. CJM 2009 (vol 61 pp. 1092)
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 |
21. CJM 2009 (vol 61 pp. 888)
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 |
22. CJM 2009 (vol 61 pp. 904)
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 |
23. CJM 2009 (vol 61 pp. 583)
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 |
24. CJM 2009 (vol 61 pp. 465)
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 |
25. 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 |