Canadian Mathematical Society www.cms.math.ca
 location:  Publications → journals
Search results

Search: MSC category 05 ( Combinatorics )

 Expand all        Collapse all Results 26 - 50 of 63

26. CMB 2011 (vol 56 pp. 407)

Rad, Nader Jafari; Jafari, Sayyed Heidar; Mojdeh, Doost Ali
 On Domination in Zero-Divisor Graphs We first determine the domination number for the zero-divisor graph of the product of two commutative rings with $1$. We then calculate the domination number for the zero-divisor graph of any commutative artinian ring. Finally, we extend some of the results to non-commutative rings in which an element is a left zero-divisor if and only if it is a right zero-divisor. Keywords:zero-divisor graph, dominationCategories:13AXX, 05C69

27. CMB 2011 (vol 55 pp. 462)

Campbell, Peter S.; Stokke, Anna
 Hook-content Formulae for Symplectic and Orthogonal Tableaux By considering the specialisation $s_{\lambda}(1,q,q^2,\dots,q^{n-1})$ of the Schur function, Stanley was able to describe a formula for the number of semistandard Young tableaux of shape $\lambda$ in terms of the contents and hook lengths of the boxes in the Young diagram. Using specialisations of symplectic and orthogonal Schur functions, we derive corresponding formulae, first given by El Samra and King, for the number of semistandard symplectic and orthogonal $\lambda$-tableaux. Keywords:symplectic tableaux, orthogonal tableaux, Schur functionCategories:05E05, 05E10

28. CMB 2011 (vol 55 pp. 410)

Service, Robert
 A Ramsey Theorem with an Application to Sequences in Banach Spaces The notion of a maximally conditional sequence is introduced for sequences in a Banach space. It is then proved using Ramsey theory that every basic sequence in a Banach space has a subsequence which is either an unconditional basic sequence or a maximally conditional sequence. An apparently novel, purely combinatorial lemma in the spirit of Galvin's theorem is used in the proof. An alternative proof of the dichotomy result for sequences in Banach spaces is also sketched, using the Galvin-Prikry theorem. Keywords:Banach spaces, Ramsey theoryCategories:46B15, 05D10

29. CMB 2011 (vol 54 pp. 217)

Chen, William Y. C.; Wang, Larry X. W.; Yang, Arthur L. B.
 Recurrence Relations for Strongly $q$-Log-Convex Polynomials We consider a class of strongly $q$-log-convex polynomials based on a triangular recurrence relation with linear coefficients, and we show that the Bell polynomials, the Bessel polynomials, the Ramanujan polynomials and the Dowling polynomials are strongly $q$-log-convex. We also prove that the Bessel transformation preserves log-convexity. Keywords:log-concavity, $q$-log-convexity, strong $q$-log-convexity, Bell polynomials, Bessel polynomials, Ramanujan polynomials, Dowling polynomialsCategories:05A20, 05E99

30. CMB 2011 (vol 54 pp. 255)

Dehaye, Paul-Olivier
 On an Identity due to Bump and Diaconis, and Tracy and Widom A classical question for a Toeplitz matrix with given symbol is how to compute asymptotics for the determinants of its reductions to finite rank. One can also consider how those asymptotics are affected when shifting an initial set of rows and columns (or, equivalently, asymptotics of their minors). Bump and Diaconis obtained a formula for such shifts involving Laguerre polynomials and sums over symmetric groups. They also showed how the Heine identity extends for such minors, which makes this question relevant to Random Matrix Theory. Independently, Tracy and Widom used the Wiener-Hopf factorization to express those shifts in terms of products of infinite matrices. We show directly why those two expressions are equal and uncover some structure in both formulas that was unknown to their authors. We introduce a mysterious differential operator on symmetric functions that is very similar to vertex operators. We show that the Bump-Diaconis-Tracy-Widom identity is a differentiated version of the classical Jacobi-Trudi identity. Keywords:Toeplitz matrices, Jacobi-Trudi identity, SzegÅ limit theorem, Heine identity, Wiener-Hopf factorizationCategories:47B35, 05E05, 20G05

31. CMB 2010 (vol 53 pp. 757)

Woo, Alexander
 Interval Pattern Avoidance for Arbitrary Root Systems We extend the idea of interval pattern avoidance defined by Yong and the author for $S_n$ to arbitrary Weyl groups using the definition of pattern avoidance due to Billey and Braden, and Billey and Postnikov. We show that, as previously shown by Yong and the author for $\operatorname{GL}_n$, interval pattern avoidance is a universal tool for characterizing which Schubert varieties have certain local properties, and where these local properties hold. Categories:14M15, 05E15

32. CMB 2010 (vol 53 pp. 425)

Chapoton, Frédéric
 Free Pre-Lie Algebras are Free as Lie Algebras We prove that the $\mathfrak{S}$-module $\operatorname{PreLie}$ is a free Lie algebra in the category of $\mathfrak{S}$-modules and can therefore be written as the composition of the $\mathfrak{S}$-module $\operatorname{Lie}$ with a new $\mathfrak{S}$-module $X$. This implies that free pre-Lie algebras in the category of vector spaces, when considered as Lie algebras, are free on generators that can be described using $X$. Furthermore, we define a natural filtration on the $\mathfrak{S}$-module $X$. We also obtain a relationship between $X$ and the $\mathfrak{S}$-module coming from the anticyclic structure of the $\operatorname{PreLie}$ operad. Categories:18D50, 17B01, 18G40, 05C05

33. CMB 2010 (vol 53 pp. 453)

Desgroseilliers, Marc; Larose, Benoit; Malvenuto, Claudia; Vincent, Christelle
 Some Results on Two Conjectures of Schützenberger We present some partial results concerning two conjectures of SchÃ¼tzenberger on evacuations of Young tableaux. Keywords:Evacuation of Standard Young tableauxCategories:05E10, 05A99

34. CMB 2009 (vol 53 pp. 378)

Zhou, Sizhong
 A New Sufficient Condition for a Graph To Be $(g,f,n)$-Critical Let $G$ be a graph of order $p$, let $a$, $b$, and $n$ be nonnegative integers with $1\leq a\lt b$, and let $g$ and $f$ be two integer-valued functions defined on $V(G)$ such that $a\leq g(x)\lt f(x)\leq b$ for all $x\in V(G)$. A $(g,f)$-factor of graph $G$ is a spanning subgraph $F$ of $G$ such that $g(x)\leq d_F(x)\leq f(x)$ for each $x\in V(F)$. Then a graph $G$ is called $(g,f,n)$-critical if after deleting any $n$ vertices of $G$ the remaining graph of $G$ has a $(g,f)$-factor. The binding number $\operatorname{bind}(G)$ of $G$ is the minimum value of ${|N_G(X)|}/{|X|}$ taken over all non-empty subsets $X$ of $V(G)$ such that $N_G(X)\neq V(G)$. In this paper, it is proved that $G$ is a $(g,f,n)$-critical graph if $\operatorname{bind}(G)\gt \frac{(a+b-1)(p-1)}{(a+1)p-(a+b)-bn+2} \quad\text{and}\quad p\geq \frac{(a+b-1)(a+b-2)}{a+1}+\frac{bn}{a}.$ Furthermore, it is shown that this result is best possible in some sense. Keywords:graph, $(g,f)$-factor, $(g,f,n)$-critical graph, binding numberCategory:05C70

35. CMB 2009 (vol 53 pp. 171)

Thomas, Hugh; Yong, Alexander
 Multiplicity-Free Schubert Calculus Multiplicity-free algebraic geometry is the study of subvarieties $Y\subseteq X$ with the smallest invariants'' as witnessed by a multiplicity-free Chow ring decomposition of $[Y]\in A^{\star}(X)$ into a predetermined linear basis. This paper concerns the case of Richardson subvarieties of the Grassmannian in terms of the Schubert basis. We give a nonrecursive combinatorial classification of multiplicity-free Richardson varieties, i.e., we classify multiplicity-free products of Schubert classes. This answers a question of W. Fulton. Categories:14M15, 14M05, 05E99

36. CMB 2009 (vol 53 pp. 3)

Athanasiadis, Christos A.
 A Combinatorial Reciprocity Theorem for Hyperplane Arrangements Given a nonnegative integer $m$ and a finite collection $\mathcal A$ of linear forms on $\mathcal Q^d$, the arrangement of affine hyperplanes in $\mathcal Q^d$ defined by the equations $\alpha(x) = k$ for $\alpha \in \mathcal A$ and integers $k \in [-m, m]$ is denoted by $\mathcal A^m$. It is proved that the coefficients of the characteristic polynomial of $\mathcal A^m$ are quasi-polynomials in $m$ and that they satisfy a simple combinatorial reciprocity law. Categories:52C35, 05E99

37. CMB 2009 (vol 52 pp. 416)

Malik, Shabnam; Qureshi, Ahmad Mahmood; Zamfirescu, Tudor
 Hamiltonian Properties of Generalized Halin Graphs A Halin graph is a graph $H=T\cup C$, where $T$ is a tree with no vertex of degree two, and $C$ is a cycle connecting the end-vertices of $T$ in the cyclic order determined by a plane embedding of $T$. In this paper, we define classes of generalized Halin graphs, called $k$-Halin graphs, and investigate their Hamiltonian properties. Keywords:$k$-Halin graph, Hamiltonian, Hamiltonian connected, traceableCategories:05C45, 05C38

38. CMB 2009 (vol 52 pp. 451)

Pach, János; Tardos, Gábor; Tóth, Géza
 Indecomposable Coverings We prove that for every $k>1$, there exist $k$-fold coverings of the plane (i) with strips, (ii) with axis-parallel rectangles, and (iii) with homothets of any fixed concave quadrilateral, that cannot be decomposed into two coverings. We also construct for every $k>1$ a set of points $P$ and a family of disks $\cal D$ in the plane, each containing at least $k$ elements of $P$, such that, no matter how we color the points of $P$ with two colors, there exists a disk $D\in{\cal D}$ all of whose points are of the same color. Categories:52C15, 05C15

39. CMB 2008 (vol 51 pp. 584)

Purbhoo, Kevin; Willigenburg, Stephanie van
 On Tensor Products of Polynomial Representations We determine the necessary and sufficient combinatorial conditions for which the tensor product of two irreducible polynomial representations of $\GL(n,\mathbb{C})$ is isomorphic to another. As a consequence we discover families of Littlewood--Richardson coefficients that are non-zero, and a condition on Schur non-negativity. Keywords:polynomial representation, symmetric function, Littlewood--Richardson coefficient, Schur non-negativeCategories:05E05, 05E10, 20C30

40. CMB 2008 (vol 51 pp. 535)

Csorba, Péter
 On the Simple $\Z_2$-homotopy Types of Graph Complexes and Their Simple $\Z_2$-universality We prove that the neighborhood complex $\N(G)$, the box complex $\B(G)$, the homomorphism complex $\Hom(K_2,G)$and the Lov\'{a}sz complex $\L(G)$ have the same simple $\Z_2$-homotopy type in the sense of Whitehead. We show that these graph complexes are simple $\Z_2$-universal. Keywords:graph complexes, simple $\Z_2$-homotopy, universalityCategories:57Q10, 05C10, 55P10

41. CMB 2008 (vol 51 pp. 413)

Thé, L. Nguyen Van
 Big Ramsey Degrees and Divisibility in Classes of Ultrametric Spaces Given a countable set $S$ of positive reals, we study finite-dimensional Ramsey-theoretic properties of the countable ultrametric Urysohn space $\textbf{Q} _S$ with distances in $S$. Keywords:Ramsey theory, Urysohn metric spaces, ultrametric spacesCategories:05C50, 54E35

42. CMB 2008 (vol 51 pp. 424)

Novelli, Jean-Christophe; Thibon, Jean-Yves
 Noncommutative Symmetric Bessel Functions The consideration of tensor products of $0$-Hecke algebra modules leads to natural analogs of the Bessel $J$-functions in the algebra of noncommutative symmetric functions. This provides a simple explanation of various combinatorial properties of Bessel functions. Categories:05E05, 16W30, 05A15

43. CMB 2008 (vol 51 pp. 47)

Croot, Ernie
 The Minimal Number of Three-Term Arithmetic Progressions Modulo a Prime Converges to a Limit How few three-term arithmetic progressions can a subset $S \subseteq \Z_N := \Z/N\Z$ have if $|S| \geq \upsilon N$ (that is, $S$ has density at least $\upsilon$)? Varnavides %\cite{varnavides} showed that this number of arithmetic progressions is at least $c(\upsilon)N^2$ for sufficiently large integers $N$. It is well known that determining good lower bounds for $c(\upsilon)> 0$ is at the same level of depth as Erd\" os's famous conjecture about whether a subset $T$ of the naturals where $\sum_{n \in T} 1/n$ diverges, has a $k$-term arithmetic progression for $k=3$ (that is, a three-term arithmetic progression). We answer a question posed by B. Green %\cite{AIM} about how this minimial number of progressions oscillates for a fixed density $\upsilon$ as $N$ runs through the primes, and as $N$ runs through the odd positive integers. Category:05D99

44. CMB 2007 (vol 50 pp. 504)

Dukes, Peter; Ling, Alan C. H.
 Asymptotic Existence of Resolvable Graph Designs Let $v \ge k \ge 1$ and $\lam \ge 0$ be integers. A \emph{block design} $\BD(v,k,\lambda)$ is a collection $\cA$ of $k$-subsets of a $v$-set $X$ in which every unordered pair of elements from $X$ is contained in exactly $\lambda$ elements of $\cA$. More generally, for a fixed simple graph $G$, a \emph{graph design} $\GD(v,G,\lambda)$ is a collection $\cA$ of graphs isomorphic to $G$ with vertices in $X$ such that every unordered pair of elements from $X$ is an edge of exactly $\lambda$ elements of $\cA$. A famous result of Wilson says that for a fixed $G$ and $\lambda$, there exists a $\GD(v,G,\lambda)$ for all sufficiently large $v$ satisfying certain necessary conditions. A block (graph) design as above is \emph{resolvable} if $\cA$ can be partitioned into partitions of (graphs whose vertex sets partition) $X$. Lu has shown asymptotic existence in $v$ of resolvable $\BD(v,k,\lambda)$, yet for over twenty years the analogous problem for resolvable $\GD(v,G,\lambda)$ has remained open. In this paper, we settle asymptotic existence of resolvable graph designs. Keywords:graph decomposition, resolvable designsCategories:05B05, 05C70, 05B10

45. CMB 2007 (vol 50 pp. 632)

Zelenyuk, Yevhen; Zelenyuk, Yuliya
 Transformations and Colorings of Groups Let $G$ be a compact topological group and let $f\colon G\to G$ be a continuous transformation of $G$. Define $f^*\colon G\to G$ by $f^*(x)=f(x^{-1})x$ and let $\mu=\mu_G$ be Haar measure on $G$. Assume that $H=\Imag f^*$ is a subgroup of $G$ and for every measurable $C\subseteq H$, $\mu_G((f^*)^{-1}(C))=\mu_H(C)$. Then for every measurable $C\subseteq G$, there exist $S\subseteq C$ and $g\in G$ such that $f(Sg^{-1})\subseteq Cg^{-1}$ and $\mu(S)\ge(\mu(C))^2$. Keywords:compact topological group, continuous transformation, endomorphism, Ramsey theoryinversion, Categories:05D10, 20D60, 22A10

46. CMB 2007 (vol 50 pp. 535)

Hohlweg, Christophe
 Generalized Descent Algebras If $A$ is a subset of the set of reflections of a finite Coxeter group $W$, we define a sub-$\ZM$-module $\DC_A(W)$ of the group algebra $\ZM W$. We discuss cases where this submodule is a subalgebra. This family of subalgebras includes strictly the Solomon descent algebra, the group algebra and, if $W$ is of type $B$, the Mantaci--Reutenauer algebra. Keywords:Coxeter group, Solomon descent algebra, descent setCategories:20F55, 05E15

47. CMB 2006 (vol 49 pp. 281)

Ragnarsson, Carl Johan; Suen, Wesley Wai; Wagner, David G.
 Correction to a Theorem on Total Positivity A well-known theorem states that if $f(z)$ generates a PF$_r$ sequence then $1/f(-z)$ generates a PF$_r$ sequence. We give two counterexamples which show that this is not true, and give a correct version of the theorem. In the infinite limit the result is sound: if $f(z)$ generates a PF sequence then $1/f(-z)$ generates a PF sequence. Keywords:total positivity, Toeplitz matrix, PÃ³lya frequency sequence, skew Schur functionCategories:15A48, 15A45, 15A57, 05E05

48. CMB 2005 (vol 48 pp. 445)

Patras, Frédéric; Reutenauer, Christophe; Schocker, Manfred
 On the Garsia Lie Idempotent The orthogonal projection of the free associative algebra onto the free Lie algebra is afforded by an idempotent in the rational group algebra of the symmetric group $S_n$, in each homogenous degree $n$. We give various characterizations of this Lie idempotent and show that it is uniquely determined by a certain unit in the group algebra of $S_{n-1}$. The inverse of this unit, or, equivalently, the Gram matrix of the orthogonal projection, is described explicitly. We also show that the Garsia Lie idempotent is not constant on descent classes (in fact, not even on coplactic classes) in $S_n$. Categories:17B01, 05A99, 16S30, 17B60

49. CMB 2005 (vol 48 pp. 460)

Sommers, Eric N.
 $B$-Stable Ideals in the Nilradical of a Borel Subalgebra We count the number of strictly positive $B$-stable ideals in the nilradical of a Borel subalgebra and prove that the minimal roots of any $B$-stable ideal are conjugate by an element of the Weyl group to a subset of the simple roots. We also count the number of ideals whose minimal roots are conjugate to a fixed subset of simple roots. Categories:20F55, 17B20, 05E99

50. CMB 2005 (vol 48 pp. 244)

McLeod, Alice; Moser, William
 Counting Multiple Cyclic Choices Without Adjacencies We give a particularly elementary solution to the following well-known problem. What is the number of $k$-subsets $X \subseteq I_n=\{1,2,3,\dots,n\}$ satisfying no two elements of $X$ are adjacent in the circular display of $I_n$''? Then we investigate a new generalization (multiple cyclic choices without adjacencies) and apply it to enumerating a class of 3-line latin rectangles. Categories:05A19, 05A05
 Page Previous 1 2 3 Next
 top of page | contact us | privacy | site map |

© Canadian Mathematical Society, 2015 : https://cms.math.ca/