51. 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 designs Categories:05B05, 05C70, 05B10 

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

53. 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 MantaciReutenauer algebra.
Keywords:Coxeter group, Solomon descent algebra, descent set Categories:20F55, 05E15 

54. CMB 2006 (vol 49 pp. 281)
 Ragnarsson, Carl Johan; Suen, Wesley Wai; Wagner, David G.

Correction to a Theorem on Total Positivity
A wellknown 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 

55. 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_{n1}$. 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 

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

57. 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
wellknown 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 3line latin rectangles.
Categories:05A19, 05A05 

58. CMB 2004 (vol 47 pp. 161)
59. CMB 2002 (vol 45 pp. 537)
60. CMB 2002 (vol 45 pp. 321)
 Brenken, Berndt

$C^{\ast}$Algebras of Infinite Graphs and CuntzKrieger Algebras
The CuntzKrieger 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
CuntzKrieger algebra $\mathcal{O}_B$ where $B$ is the vertex matrix
of~$E$.
Categories:46LXX, 05C50 

61. 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^{n1}$ metric
equalities.
Keywords:normed spaces, hypercubes Categories:46B04, 05C10, 05B99 

62. CMB 2000 (vol 43 pp. 397)
63. 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 

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

65. 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 nonassociative algebras. These
resolutions derive in both cases from geometric objects, which in turn
reflect the combinatorics of suitable collections of leaflabeled
trees.
Keywords:resolutions, homology, Lie algebras, associative algebras, nonassociative algebras, Jacobi identity, leaflabeled trees, associahedron Categories:18G10, 05C05, 16S10, 17B01, 17A50, 18G50 

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

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

68. 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 ``2large'' are given. Several open
questions and a conjecture are presented.
Categories:11B25, 05D10 

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

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