Expand all Collapse all | Results 51 - 59 of 59 |
51. CMB 2000 (vol 43 pp. 397)
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 |
52. CMB 2000 (vol 43 pp. 385)
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 |
53. CMB 2000 (vol 43 pp. 108)
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 |
54. CMB 2000 (vol 43 pp. 3)
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 |
55. CMB 1999 (vol 42 pp. 359)
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 |
56. CMB 1999 (vol 42 pp. 386)
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 |
57. CMB 1999 (vol 42 pp. 25)
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 |
58. CMB 1998 (vol 41 pp. 33)
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 |
59. CMB 1997 (vol 40 pp. 149)
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 |