CMSMITACS Joint Conference 2007May 31  June 3, 2007
Delta Hotel, Winnipeg, Manitoba

In a finite affine plane of order n, a system of parallel representatives (SPR) is a set of n+1 lines consisting of exactly one line from each parallel class of the plane. An SPR is tight if no three of its lines are incident on a common point; this is equivalent to a hyperoval in the dual of the associated projective plane of order n. We describe some basic properties of SPR's and characterize tight SPR's as those on which a certain sumofsquares function attains the value zero. We then examine some necessary conditions for an SPR to be minimal with respect to this function, and apply our results to SPR's in a hypothetical affine plane of order 12.
A kuniform hypergraph (V,E) is 3colorcritical if it is not
2colorable, but for every edge e the hypergraph (V,Ee) is
2colorable. Lovász proved in 1976 that

Here we give a new algebraic proof and prove a generalization that leads to a sharpening of Sauer's bound for forb(m,F), where F is a kbyl 0,1matrix.
Joint work with R. Anstee, B. Fleming, and A. Sali.
Let G be a graph with a distinguished vertex d. Suppose that each vertex of G has a preference list of a set of paths joining it to d. A solution to the stable paths problem is a tree T in G rooted at d, with the property that for each vertex x, if x prefers some path P to the path from x to d in T, then some edge of P not incident to x is missing from T. Not every instance of the stable paths problem has a solution, but we show that every instance does have a fractional solution.
The peak sidelobe level of a binary sequence is the largest absolute value of all its nontrivial aperiodic autocorrelations. A classical problem of digital sequence design is to determine how slowly the peak sidelobe level of a length n binary sequence can grow, as n becomes large. Moon and Moser showed in 1968 that the growth rate of the peak sidelobe level of almost all length n binary sequences lies between order Ö{n logn} and Ön, but in the last forty years no theoretical improvement to these bounds has been found.
I shall present numerical evidence showing how closely these bounds can be approached. A significant algorithmic improvement reveals behaviour that was previously well beyond the range of computation.
Joint work with Denis Dmitriev.
An orthogonal design A of order n and type (s_{1},s_{2},...,s_{u}), in the commuting variables ±x_{1},±x_{2},...,±x_{u}, denoted OD(n; s_{1},s_{2},...,s_{u}), is a square matrix of order n with entries ±x_{k} or 0, where each x_{k} occurs s_{k} times in each row and column such that distinct rows are pairwise orthogonal. Two orthogonal designs X and Y are said to be amicable, if XY^{t}=YX^{t}.
Amicable orthogonal designs are instrumental in the construction of orthogonal matrices. Not much is known about the existence or the structure of full (no zeros) amicable orthogonal designs admitting the maximum possible number of variables. An asymptotic existence result for full amicable orthogonal designs with almost maximum number of variables will be presented.
Given a finite projective plane of order n. A quadrangle consists of four points A,B,C,D, no three collinear. If the diagonal points are noncollinear, the quadrangle is called a nonFano quad. A general theorem is proved on the distibution of points and lines in a plane of order n, with respect to a nonFano quad, whenever n ³ 7. The theorem implies that the number of possible distributions of points in a plane of order n is limited for all n ³ 7.
A Steiner quadruple system of order v, SQS(v), is a pair (X,B), where B is a set of 4subsets of X such that each 3subset of X is in a unique member of B. Hanani showed that an SQS(v) exists if and only if v=0,1 or v º 2,4 mod 6. An SQS(v) is commonly described as a S(3,4,v) design, and as a 4uniform hypergraph each SQS(v) has a chromatic number.
For a given k ³ 2, a basic problem is to determine all v for which a kchromatic SQS(v) exists. We survey recent progress on this problem and point out avenues for future research.
We consider a generalization of Turán's theorem for edgecolored graphs. Suppose that R (red) and B (blue) are graphs on the same vertex set of size n. We conjecture that if R and B each have more than (11/k) n^{2}/2 edges, and K is a (k+1)clique whose edges are arbitrarily colored with red and blue, then R ÈB contains a colored copy of K, for all k+1 Ï {4,6,8}. If k+1 Î {4,6,8}, then the same conclusion holds except for one specific edgecoloring of K_{k+1}.
We prove this conjecture for all 2edgecolorings of K_{k+1} that contain a monochromatic K_{k}. This provides a new proof of Turán's theorem. We also prove the conjecture for k+1 Î {3,4,5}.
This is joint work with Ajit Diwan.
Fullerenes are allcarbon molecules whose molecular structures correspond to 3regular planar graphs that have face sizes equal to five or six. Fuigui (Fullerene Interactive Graphical User Interface) is a java program under development whose goal is to aid the exploration of fullerenes and their parameters. This talk will include a selection of interesting open problems about various fullerene parameters. A demonstration of how Fuigui can be used to attack these will be provided.
This is joint work with Bette Bultena, Sean Daugherty, Bradley Debroni Patrick Fowler, Sameer Girn, Marsha Minchenko, and Jennifer Woodcock.
Let V be a finite set and M a collection of subsets of V. Then M is an alignment of V if and only if M is closed under taking intersections and contains both V and the empty set. If M is an alignment of V, then the elements of M are called convex sets and the pair (V,M) is called an aligned space. If S Í V, then the convex hull of S is the smallest convex set that contains S. Suppose X Î M. Then x Î X is an extreme point for X if X \{x} Î M. A convex geometry on a finite set is an aligned space with the additional property that every convex set is the convex hull of its extreme points. Let G be a connected graph. We define several graph convexities using Steiner distances and trees and characterize those classes of graphs for which these graph convexities are convex geometries.
Joint work with M. Nielsen.
It was shown by H. Schröter [Nachr. Ges. Wiss. Göttingen 1889, 193236] that among the ten combinatorially possible (10,3) designs, only one cannot be realized in a projective plane over any field. In view of this, this D10 is known in the literature as an antiPappian design. In 1954, R. Lauffer [Math. Nachrichten, vol. 11] gave a representation of this design over the infinite division ring of quaternions. This proves that the design, viewed as a ternary implicational system, is strictly consistent, meaning that it is impossible to formally derive x=y from the ten defining equations. Here we give a group representation of rank 3 for this configuration and show that 3 is the minimal possible rank for such a representation. Apart from demonstrating the combinatorial consistency of the antiPappian design, this gives a new proof of the fact that this design cannot be realized in any finite Desarguesian plane. This is part of an unpublished set of notes on group representations written in collaboration with Barry Wolk and the late Professor Nathan Mendelsohn.
We show that for any p such that pn goes to infinity, the diameter of G_{n,p} is concentrated on two values.
Rivest proposed the idea of a chaffingandwinnowing scheme, in which confidentiality is achieved through the use of an authentication code. Thus it would still be possible to have confidential communications even if conventional encryption schemes were outlawed. Hanaoka et al. constructed unconditionally secure chaffingandwinnowing schemes which achieve perfect secrecy in the sense of Shannon. Their schemes are constructed from unconditionally secure authentication codes.
In this talk, we construct unconditionally secure chaffingandwinnowing schemes from unconditionally secure authentication codes in which the authentication tags are very short. This could be a desirable feature, because certain types of unconditionally secure authentication codes can provide perfect secrecy if the length of an authentication tag is at least as long as the length of the plain text. The use of such a code might be prohibited if encryption schemes are made illegal, so it is of interest to construct chaffingandwinnowing schemes based on "short" authentication tags.
We use elementary combinatorial techniques for our construction.
In this talk I will prove that for any forest F Ì K_{n}, K_{n}\E(F) is a union of at most roughly nlogn cliques. This result generalizes a number of preceding theorems on clique partitions of complements of paths. In addition, it will be shown that the minimum number of cliques required to partition K_{n}\E(G) when G Ì K_{n} has maximum degree O(n^{1e}), where e > 0 is a constant independent of n, is at most n^{2e/2} (logn)^{2} and at least e^{2}n^{22e}, for n large enough relative to e.
We leave the following two basic open problems. First, to show that if a graph G Ì K_{n} has maximum degree o(n), then K_{n}\E(G) can be partitioned into o(n^{2}) cliques, and second, to exhibit a forest F such that K_{n} \E(F) cannot be partitioned into any linear number of cliques.
This is joint work with Mike Cavers.
Active researches on selfdual codes over Z_{4} = Z/4Z have been devoted in recent years. A Type II Z_{4}code is a selfdual code which has the property that all Euclidean weights are divisible by 8 and contains the allone vector.
A selfdual Z_{4}code which is not a Type II code is called a Type I Z_{4}code. A Type IV Z_{4}code is a selfdual code with all codewords of even Hamming weight. A type IV code which is also Type I or Type II is called a Type IVI, or a Type IVII code respectively. Two infinite families of Type IV codes are known, Klemm's codes and C_{m,r} codes.
The distinct rows of an Hadamard matrix are orthogonal. If we recognize the components 1 and 1 of an Hadamard matrix H_{4m} of order 4m as the elements of Z_{4}, then the Z_{4}code generated by H_{4m} is selforthogonal. In 1999, Charnes proved that if an Hadamard matrix H_{4m} has order 4m and m is odd, then the Z_{4}code generated by H_{4m} is selfdual and equivalent to Klemm's code. Charnes and Seberry considered the Z_{4}code generated by a weighing marix W(n,4) and proved that if it has type 4^{(n4)/2}2^{4}, then it is a selfdual code. In this talk, we give families of selfdual Z_{4}codes of Type IVI and Type IVII generated by Hadamard matrices and conference matrices.