CanaDAM 2013 Memorial University of Newfoundland, June 10 - 13, 2013 www.cms.math.ca//2013
 français conference home canadam home

Eric Mendelsohn: Colleagues and Descendants III
Chair: Peter Danziger (Ryerson University)
Org: Peter Danziger (Ryerson University) and Brett Stevens (Carleton University)
[PDF]

AIDEN BRUEN, Carleton University
Unimbeddable nets of small deficiency  [PDF]

The famous Bruck-Bose embedding theorem for nets [or families of mols] and partial geometries asserts that, in particular, a net of order $n$ with small deficiency is embeddable in an affine plane of order $n$. As a counterpoint we present here a simple construction for a family of nets of order $n$ degree $k$ which are unimbeddable and have the smallest known deficiency, i.e. the largest known value of $k$. The construction uses a classical geometrical result which is ascribed to Gallucci but which, strictly speaking, goes back to Pappus of Alexandria.

FRANTISEK FRANEK, McMaster University
On the singularities of extremal periodic strings  [PDF] [SLIDES]

Fraenkel and Simpson conjectured in 1998 that the number of distinct squares in a string is at most its length. Kolpakov and Kucherov conjectured the same in 1999 for the number of runs. We consider the role of the size of the string's alphabet in both problems and investigate the functions $\sigma_d(n)$ and $\rho_d(n)$, i.e. the maximum number of distinct primitively rooted squares, respectively runs, over all strings of length $n$ containing exactly $d$ distinct symbols. We discuss singularities of the two functions, i.e. pairs $(d,n)$ such that $\sigma_d(n)-\sigma_{d-1}(n-2)\geq 2$, or $\rho_d(n)-\rho_{d-1}(n-2)\geq 2$ respectively. Joint work with A. Deza.

SEBASTIAN RAAPHORST, University of Ottawa
The Lovasz Local Lemma and Variable Strength Covering Arrays  [PDF]

The Lovasz Local Lemma is a nonconstructive probabilistic technique that can be used to determine upper bounds on properties of combinatorial objects. We apply the Local Lemma to determine upper bounds on the size of variable strength covering arrays for different families of hypergraphs and show how the bounds compare to those derived from a greedy-density based algorithm and best known bounds. We also examine issues in applying the symmetric form of the Local Lemma, and challenges that arise in using the more general forms.

The "1-2-3 conjecture" states that any connected graph on at least 3 vertices may be properly vertex coloured by assigning each edge a label from $\{1,2,3\}$ and colouring a vertex with the sum of the weights from its incident edges. One may generalize this by weighting edges from independently assigned lists. I will present the first known upper bound (which is graph dependent) for the size of lists required to properly colour vertices in this way; the result is obtained via Alon's Combinatorial Nullstellensatz. This work was completed as part of my PhD thesis under the supervision of Brett Stevens.
In 2000, Rees and Shalaby constructed simple, indecomposable two-fold cyclic triple systems for all $v\equiv 0,1,3,4,7$ and $9~ (\textup{mod}~12)$, where $v=4$ or $v\geq 12$, using Skolem-type sequences.