CMS/SMC
Canadian Mathematical Society
www.cms.math.ca
Canadian Mathematical Society
  location:  Publicationsjournals
Publications        
Search results

Search: MSC category 05 ( Combinatorics )

  Expand all        Collapse all Results 51 - 68 of 68

51. 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 set
Categories:20F55, 05E15

52. 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 function
Categories:15A48, 15A45, 15A57, 05E05

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

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

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

56. CMB 2004 (vol 47 pp. 161)

Alspach, Brian; Du, Shaofei
Suborbit Structure of Permutation $p$-Groups and an Application to Cayley Digraph Isomorphism
Let $P$ be a transitive permutation group of order $p^m$, $p$ an odd prime, containing a regular cyclic subgroup. The main result of this paper is a determination of the suborbits of $P$. The main result is used to give a simple proof of a recent result by J.~Morris on Cayley digraph isomorphisms.

Categories:20B25, 05C60

57. CMB 2002 (vol 45 pp. 537)

Chapoton, Frédéric; Fomin, Sergey; Zelevinsky, Andrei
Polytopal Realizations of Generalized Associahedra
No abstract.

Categories:05E15, 20F55, 52C07

58. CMB 2002 (vol 45 pp. 321)

Brenken, Berndt
$C^{\ast}$-Algebras of Infinite Graphs and Cuntz-Krieger Algebras
The Cuntz-Krieger algebra $\mathcal{O}_B$ is defined for an arbitrary, possibly infinite and infinite valued, matrix $B$. A graph $C^{\ast}$-algebra $G^{\ast} (E)$ is introduced for an arbitrary directed graph $E$, and is shown to coincide with a previously defined graph algebra $C^{\ast} (E)$ if each source of $E$ emits only finitely many edges. Each graph algebra $G^{\ast} (E)$ is isomorphic to the Cuntz-Krieger algebra $\mathcal{O}_B$ where $B$ is the vertex matrix of~$E$.

Categories:46LXX, 05C50

59. CMB 2001 (vol 44 pp. 370)

Weston, Anthony
On Locating Isometric $\ell_{1}^{(n)}$
Motivated by a question of Per Enflo, we develop a hypercube criterion for locating linear isometric copies of $\lone$ in an arbitrary real normed space $X$. The said criterion involves finding $2^{n}$ points in $X$ that satisfy one metric equality. This contrasts nicely to the standard classical criterion wherein one seeks $n$ points that satisfy $2^{n-1}$ metric equalities.

Keywords:normed spaces, hypercubes
Categories:46B04, 05C10, 05B99

60. CMB 2000 (vol 43 pp. 397)

Bonato, Anthony; Cameron, Peter; Delić, Dejan
Tournaments and Orders with the Pigeonhole Property
A binary structure $S$ has the pigeonhole property ($\mathcal{P}$) if every finite partition of $S$ induces a block isomorphic to $S$. We classify all countable tournaments with ($\mathcal{P}$); the class of orders with ($\mathcal{P}$) is completely classified.

Keywords:pigeonhole property, tournament, order
Categories:05C20, 03C15

61. CMB 2000 (vol 43 pp. 385)

Bluskov, I.; Greig, M.; Heinrich, K.
Infinite Classes of Covering Numbers
Let $D$ be a family of $k$-subsets (called blocks) of a $v$-set $X(v)$. Then $D$ is a $(v,k,t)$ covering design or covering if every $t$-subset of $X(v)$ is contained in at least one block of $D$. The number of blocks is the size of the covering, and the minimum size of the covering is called the covering number. In this paper we consider the case $t=2$, and find several infinite classes of covering numbers. We also give upper bounds on other classes of covering numbers.

Categories:05B40, 05D05

62. CMB 2000 (vol 43 pp. 108)

Sanders, Daniel P.; Zhao, Yue
On the Entire Coloring Conjecture
The Four Color Theorem says that the faces (or vertices) of a plane graph may be colored with four colors. Vizing's Theorem says that the edges of a graph with maximum degree $\Delta$ may be colored with $\Delta+1$ colors. In 1972, Kronk and Mitchem conjectured that the vertices, edges, and faces of a plane graph may be simultaneously colored with $\Delta+4$ colors. In this article, we give a simple proof that the conjecture is true if $\Delta \geq 6$.

Categories:05C15, 05C10

63. CMB 2000 (vol 43 pp. 3)

Adin, Ron; Blanc, David
Resolutions of Associative and Lie Algebras
Certain canonical resolutions are described for free associative and free Lie algebras in the category of non-associative algebras. These resolutions derive in both cases from geometric objects, which in turn reflect the combinatorics of suitable collections of leaf-labeled trees.

Keywords:resolutions, homology, Lie algebras, associative algebras, non-associative algebras, Jacobi identity, leaf-labeled trees, associahedron
Categories:18G10, 05C05, 16S10, 17B01, 17A50, 18G50

64. CMB 1999 (vol 42 pp. 359)

Martin, W. J.; Stinson, D. R.
A Generalized Rao Bound for Ordered Orthogonal Arrays and $(t,m,s)$-Nets
In this paper, we provide a generalization of the classical Rao bound for orthogonal arrays, which can be applied to ordered orthogonal arrays and $(t,m,s)$-nets. Application of our new bound leads to improvements in many parameter situations to the strongest bounds (\ie, necessary conditions) for existence of these objects.

Categories:05B15, 65C99

65. CMB 1999 (vol 42 pp. 386)

Polat, Norbert
Minimal Separators
A separator of a connected graph $G$ is a set of vertices whose removal disconnects $G$. In this paper we give various conditions for a separator to contain a minimal one. In particular we prove that every separator of a connected graph that has no thick end, or which is of bounded degree, contains a minimal separator.

Category:05C40

66. CMB 1999 (vol 42 pp. 25)

Brown, Tom C.; Graham, Ronald L.; Landman, Bruce M.
On the Set of Common Differences in van der Waerden's Theorem on Arithmetic Progressions
Analogues of van der Waerden's theorem on arithmetic progressions are considered where the family of all arithmetic progressions, $\AP$, is replaced by some subfamily of $\AP$. Specifically, we want to know for which sets $A$, of positive integers, the following statement holds: for all positive integers $r$ and $k$, there exists a positive integer $n= w'(k,r)$ such that for every $r$-coloring of $[1,n]$ there exists a monochromatic $k$-term arithmetic progression whose common difference belongs to $A$. We will call any subset of the positive integers that has the above property {\em large}. A set having this property for a specific fixed $r$ will be called {\em $r$-large}. We give some necessary conditions for a set to be large, including the fact that every large set must contain an infinite number of multiples of each positive integer. Also, no large set $\{a_{n}: n=1,2,\dots\}$ can have $\liminf\limits_{n \rightarrow \infty} \frac{a_{n+1}}{a_{n}} > 1$. Sufficient conditions for a set to be large are also given. We show that any set containing $n$-cubes for arbitrarily large $n$, is a large set. Results involving the connection between the notions of ``large'' and ``2-large'' are given. Several open questions and a conjecture are presented.

Categories:11B25, 05D10

67. CMB 1998 (vol 41 pp. 33)

Gallant, Robert; Colbourn, Charles J.
Asymptotic existence of tight orthogonal main effect plans
Our main result is showing the asymptotic existence of tight $\OMEP$s. More precisely, for each fixed number $k$ of rows, and with the exception of $\OMEP$s of the form $2 \times 2 \times \cdots 2 \times 2s\specdiv 4s$ with $s$ odd and with more than three rows, there are only a finite number of tight $\OMEP$ parameters for which the tight $\OMEP$ does not exist.

Categories:62K99, 05B15

68. CMB 1997 (vol 40 pp. 149)

Brown, Tom C.; Landman, Bruce M.; Mishna, Marni
Monochromatic homothetic copies\\ of $\{1,1+s,1+s+t\}$
For positive integers $s$ and $t$, let $f(s, t)$ denote the smallest positive integer $N$ such that every $2$-colouring of $[1,N]=\{1,2, \ldots , N\}$ has a monochromatic homothetic copy of $\{1, 1+s, 1+s+t\}$. We show that $f(s, t) = 4(s+t) + 1$ whenever $s/g$ and $t/g$ are not congruent to $0$ (modulo $4$), where $g=\gcd(s,t)$. This can be viewed as a generalization of part of van~der~Waerden's theorem on arithmetic progressions, since the $3$-term arithmetic progressions are the homothetic copies of $\{1, 1+1, 1+1+1\}$. We also show that $f(s, t) = 4(s+t) + 1$ in many other cases (for example, whenever $s > 2t > 2$ and $t$ does not divide $s$), and that $f(s, t) \le 4(s+t) + 1$ for all $s$, $t$. Thus the set of homothetic copies of $\{1, 1+s, 1+s+t\}$ is a set of triples with a particularly simple Ramsey function (at least for the case of two colours), and one wonders what other ``natural'' sets of triples, quadruples, {\it etc.}, have simple (or easily estimated) Ramsey functions.

Category:05D10
Page
   1 2 3    

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