Canadian Mathematical Society
Canadian Mathematical Society
  location:  Publicationsjournals
Search results

Search: MSC category 05 ( Combinatorics )

  Expand all        Collapse all Results 76 - 79 of 79

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


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

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

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

   1 2 3 4    

© Canadian Mathematical Society, 2017 :