Réunion d'été 2009 de la SMC et de la SCHPM
Université Memorial de Terre-Neuve, St. John's (Terre Neuve), 6 - 8 juin, 2009

Designs combinatoires et sujets connexes
Org: Václav Linek (Winnipeg) et Nabil Shalaby (Memorial)

CATHY BAKER, Mount Allison University, Sackville, NB, E4L 1E6
Extended near Skolem sequences: where are we now?

Skolem-type sequences can be useful in constructing various types of designs, for example in constructing Steiner triple systems and cyclic partial triple systems.

A k-extended q-near Skolem sequence of order n is an integer sequence (s1, ...,s2n-1) with sk=0 such that for each j Î {1,2, ..., n} \{q}, there exists a unique i with si=si+j=j. It is straightforward to show that such a sequence exists only if

    (1) n º 0, 1 mod 4 and q and k have the same parity, or
    (2) n º 2, 3 mod 4 and q and k have opposite parity.
However, it is more difficult to show that these conditions are sufficient. We examine various families of constructions and assess what is left to do.

ELIZABETH J. BILLINGTON, University of Queensland, Brisbane, Australia
Gregarious cycles: an antipodean update

A complete multipartite graph K(a1,a2,...,an) has its vertices partitioned into n parts or "partite sets" of size ai, 1\leqslant i\leqslant n, and any pair of vertices is joined by an edge if and only if the vertices lie in different partite sets.

A k-cycle decomposition of G = K(a1,a2,...,an) is a partition of all the edges of G into k-cycles. The decomposition is said to be `gregarious' if every possible k-cycle in the decomposition has all its k vertices lying in different partite sets (so necessarily the cycle length k does not exceed the number of parts n).

An update on the present state of play regarding existence of gregarious k-cycle systems will be given.

Joint with Benjamin R. Smith.

ILIYA BLUSKOV, University of Northern British Columbia, Department of Mathematics, Prince George, BC, V2N 4Z9
On Packing Designs

A 2-(v,k,l) packing design, (V,B), is a set V (with elements called points) and a collection B of k-subsets of V (called blocks) with the property that every unordered pair of points occurs in at most l blocks. We denote the maximum possible size of B by Dl(v,k,2) and call it the packing number for these parameters. We are interested in finding either the exact value of Dl(v,k,2) or a good lower bound on it.

I will give an update on the exact values of Dl(v,5,2).

I will also talk about some new results on improving the known bounds on the size of constant weight codes (packings with l = 1) by using optimization.

ANDREA BURGESS, University of Ottawa
Cycle decompositions of 3Km

We consider the problem of determining necessary and sufficient conditions for the existence of a decomposition of the complete multigraph lKm into cycles of length k (also called a (lKm, Ck)-design or a k-cycle system of lKm). This problem remains open in general. Notably, necessary and sufficient conditions are known for l = 1 or 2 (Alspach, Gavlas, Sajna, Verrall), but have not been determined for greater values of l. In this talk, we discuss progress towards the case l = 3.

PETER DANZIGER, Ryerson Unversity
On bipartite 2-factorisations of Kn-I and the Oberwolfach problem

It is shown that if F1, F2, ..., Ft are bipartite 2-regular graphs of order n and a1, a2, ..., at are non-negative integers such that a1 + a2 + ¼+ at = [(n-2)/2], a1 ³ 3 is odd, and ai is even for i = 2, 3, ..., t, then there exists a 2-factorisation of Kn-I in which there are exactly ai 2-factors isomorphic to Fi for i = 1, 2, ..., t. Taking t=1 this result completes the solution of the Oberwolfach problem for any collection of even sized cycles.

This is joint work with Darryn Bryant, The University of Queensland.

WILLIAM MARTIN, Worcester Polytechnic Institute, 100 Institute Road, Worcester, MA 01609, USA
Roughly independent binary random variables

In cryptography (as well as other areas, I'm sure), the effective (ab)use of random bits is of great importance. In this talk, we consider an expansion function f : {0,1}m ® {0,1}n (n > m) with the property that, given the uniform distribution Um on input strings, the projection of the output f(Um) onto any t coordinates has min-entropy at least l. For example, for l = t, this is just a binary orthogonal array of strength t with n factors and 2m runs. Our goal is to significantly beat the Rao bound by allowing l to drop below t.

In this talk, which is joint work with Matt Houde of EMC Corporation, I will give some preliminary bounds and constructions. Hopefully, I can motivate some experts to look into this question.

JIM MCQUILLAN, Western Illinois University, Department of Computer Science, 447 Stipes Hall, Macomb, IL 61455, USA
Desargues' theorem and related configurations

Consider a projective plane over a field F. One interesting question is: given two triangles in perspective from a point V, under what circumstances does V lie on the Desargues axis? We consider Desargues' theorem and some related configurations.

This is joint work with Prof. Aiden Bruen, Department of Electrical and Computer Engineering, the University of Calgary.

DANIELA SILVSAN, Memorial University, St John's, Newfoundland
The intersection spectrum of Skolem sequences and its applications to l-fold cyclic triple systems

A Skolem sequence of order n is a sequence Sn = (s1,s2,...,s2n) of 2n integers containing each of the symbols 1,2,...,n exactly twice, such that two occurrences of the integer j Î {1,2,...,n} are separated by exactly j-1 symbols. We prove, with few possible exceptions, that there exists two Skolem sequences of order n with 0,1,2,...,n-3 or n pairs in common. Using this result, we determine, with few possible exceptions the fine structure of a cyclic three-fold triple systems, for v º 1,7 mod 24. We also determine, with few exceptions, the fine structure of a cyclic four-fold triple systems, for v º 1,7 mod 24. Then, we extend these results to the fine structure of a l-fold directed triple system and a l-fold Mendelsohn triple system. We also determine, the number of possible repeated base blocks in a cyclic two-fold triple system, a directed triple system and a Mendelsohn triple system, for v º 1,3 mod 6.

BRETT STEVENS, Carleton University, 1125 Colonel By Dr., Ottawa, ON, K1S 5B6
Octahedral Designs

An octahedral design of order v, or ocv, is a decomposition of all oriented triples on v points into oriented octahedra. Hanani settled the existence of these designs in the unoriented case. We show that an ocv exists if and only if v º 1,2,6 mod 8 (the admissible numbers), and moreover the constructed ocv are indecomposble, i.e., the octahedra cannot be paired into mirror images. We show that an ocv with a subdesign ocu exists if and only if v and u are admissible and v ³ u+4.

This is joint work with Prof. V. Linek.

STEVEN WANG, Carleton University
Costas arrays and permutations with distinct difference property

Costas arrays arise in sonar and radar applications and they also closely related to a few other combinatorial designs. Originally an m ×m Costas array is defined as an m ×m permutation matrix (that is, a square matrix with precisely one 1 in each row and column and all other entries 0) for which all the vectors joining the pairs of 1's are distinct. It can also be defined in terms of a permutation such that each row in the difference triangle contains distinct entries. In this talk, I will discuss basic constructions of Costas arrays and a weaker notion of Costas arrays: permutations with distinct difference property (DDP permutations). In particular, I will address some issues related to a construction proposed by Batten and Sane in 2003 on DDP permutations.


l'Université Memorial de Terre-Neuve    AARMS: Atlantic Association for Research in the Mathematical Sciences    Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Réseau canadien de recherche sur le langage et l'alphabétisation

© Société mathématique du Canada :