Finite Combinatorics
Org: Robert Craigen and David Gunderson (Manitoba) [PDF]
 WAYNE BROUGHTON, University of British Columbia Okanagan
Systems of Parallel Representatives
[PDF] 
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.
 ZOLTAN FUREDI, University of Illinois at UrbanaChampaign
Color critical hypergraphs and forbidden configurations
[PDF] 
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
for a 3colorcritical kuniform hypergraph with n vertices.
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.
 PENNY HAXELL, University of Waterloo
On stable paths
[PDF] 
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.
 JONATHAN JEDWAB, Simon Fraser University, 8888 University Drive, Burnaby, BC,
V5A 1S6
Bounds on the growth rate of the peak sidelobe level of
binary sequences
[PDF] 
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.
 HADI KHARAGHANI, University of Lethbridge
The asymptotic existence of amicable orthogonal designs
[PDF] 
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.
 WILLIAM KOCAY, University of Manitoba
NonFano Quads in Finite Projective Planes
[PDF] 
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.
 VACLAV LINEK, University of Winnipeg, 515 Portage Ave., Winnipeg, MB,
R3B 2E9
Chromatic numbers of Steiner quadruple systems
[PDF] 
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.
 DHRUV MUBAYI, University of Illinois at Chicago
Turan's theorem with colors
[PDF] 
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.
 WENDY MYRVOLD, University of Victoria, Victoria, BC
Investigating Conjectures about Fullerenes
[PDF] 
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.
 ORTRUD OELLERMANN, University of Winnipeg
Steiner Trees and Convex Geometries
[PDF] 
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.
 RANGANATHAN PADMANABHAN, University of Manitoba
A group representation for the antiPappian design
[PDF] 
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.
 BRUCE REED, McGill University, CNRS, and INRIA
The diameter of sparse random graphs
[PDF] 
We show that for any p such that pn goes to infinity, the diameter
of G_{n,p} is concentrated on two values.
 DOUGLAS STINSON, University of Waterloo
Unconditionally secure chaffing and winnowing with short
authentication tags
[PDF] 
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.
 JACQUES VERSTRAETE, McGill University, 805 Sherbrooke Street West, Montreal,
Quebec, Canada, H3A 2K6
Clique partitions of dense graphs
[PDF] 
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.
 MIEKO YAMADA, Kanazawa University, Kakumamachi, Kanazawa 9201192, Japan
Selfdual Z_{4} codes generated by Hadamard
matrices and conference matices
[PDF] 
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.
