


Combinatorics / Combinatoire Org: Petr Lisonek (Simon Fraser) and/et Brett Stevens (Carleton)
 RICHARD ANSTEE, UBC
A conjecture for small forbidden configurations

This represents joint work with Attila Sali and also Balin Fleming. We
say that a matrix is simple if it is a (0,1)matrix with no repeated
columns. Consider an arbitrary k×l (0,1)matrix F and let
forb(m,F) be the maximum possible number of columns that a mrowed
simple matrix can have subject to the property that there is no
submatrix which is a row and column permutation of F. We conjecture
a resonable simple set of constructions from which the asymptotic
behaviour of forb(m,F). In particular we propose the matrices F for
which forb(m,F) is O(m^{k1}) providing a generalization of the
Sauer Bound (a result of Vapnik and Chervonenkis, Perles and Shelah,
and Sauer).
 FRANCOIS BERGERON, Université du Québec à Montréal, Département de
Mathématiques, Montréal, Québec
On a conjecture about LittlewoodRichardson coefficients

We give new results about a fascinating conjecture of Fulton, Fomin, Li
and Poon concerning inequalities for LittlewoodRichardson
coefficients. This involves a strange operation on pairs of integer
partitions, that they call "star". We give many unexpected
combinatorial properties of this star operation, and derive from these
that the conjecture holds for several families of partition pairs.
Moreover we give a natural extension of the conjecture to skew shapes.
This is joint work with R. Biagioli and M. Rosas.
 NANTEL BERGERON, York University
Combinatorial Hopf algebra have character

We will introduce the notion of characters for graded Hopf algebras and
derive some interesting properties of the character group. In
particular we will give a canonical factorization of a character into
an even and an odd character. We will discuss some canonical character
related to combinatorial Hopf algebras.
This induces the definition of the Even/Odd Hopf subalgebra of a
combinatorial Hopf algebra. We will show that the quasisymmetric
functions combinatorial Hopf algebra is the carthesian product of its
even/odd Hopf subalgebra.
 ILIYA BLUSKOV, University of Northern British Columbia, Department of Mathematics,
Prince George, British Columbia V2N 4Z9
LDEO in recent search for designs

Let B=[b_{ij}] be an n×k matrix with entries in Z_{v}. If
the multiset
{b_{ij}b_{is}  j ¹ s,1 £ j £ k, 1 £ s £ k,1 £ i £ n} 

contains every nonzero element of Z_{v} exactly l times, then
the existence of B implies the existence of a 2(v,k,l)
cyclic design (cyclic BIBD). In this case, the cyclic group Z_{v} is a
subgroup of the group of automorphisms of the BIBD. We present an
application of LDEO (Leveldependent experimental optimization) to
finding such matrices. Modifications of this algorithm have been
applied in the search for 2(v,k,l) designs having either
Z_{l}, l < v, or a product of cyclic groups as a subgroup of the
group of automorphisms. The algorithm has also been successful in
recent searches for coverings.
 JONATHAN JEDWAB, Department of Mathematics, Simon Fraser University,
Burnaby, British Columbia V5A 1S6
Constructing binary sequences with merit factor greater
than 6.34

The study of the merit factor of binary sequences occurs as a classical
problem of signal design for digital communication and, in equivalent
guise, in analytic number theory. It has also become a notorious
problem of combinatorial optimization. For thirty years mathematicians,
engineers, physicists and chemists have sought a systematic way to
construct long binary sequences with large merit factor. All previous
work has led to an asymptotic merit factor no larger than six.
In Summer 1999, Jim Davis of the University of Richmond supervised
students Tony Kirilusha and Ganesh Narayanaswamy in an investigation of
this problem. The students discovered a new method of constructing good
sequences that suggested it might be possible reliably to attain a
merit factor greater than six.
After conducting extensive computational experiments, Peter Borwein,
Stephen Choi and I found a way to develop the students' method into a
systematic construction for long binary sequences. We can obtain a
merit factor greater than 6.34 for sequences up to millions of elements
long. We cannot yet prove that the construction will work for
arbitrarily long sequences, but have used numerical evidence to
formulate a precise conjecture which would imply this result.
I shall describe from first principles the merit factor problem and
show how it arises in multiple disciplines. I shall then tell the story
linking the students' work to the recent results, and present evidence
in support of the explanatory conjecture.
 MARK KAYLL, University of Montana, Department of Mathematical Sciences,
Missoula, Montana, USA
On weak Sidon sequences: a new proof with an improved bound

A sequence (a_{i}) of integers is weakly Sidon if the sums
a_{i}+a_{j}, for i < j, are all different. For a fixed positive integer
r, let W_{r}(N) denote the maximum integer n for which
there exists a weak Sidon sequence 0 £ a_{1} < ¼ < a_{n} £ N with
a_{i} º a_{j}( mod r) for all i, j. We shall outline a proof,
based on an idea of Lindström (1969), of the following theorem of
Ruzsa (1993): (N/r)^{1/2}(N/r)^{21/80} < W_{r}(N) < (N/r)^{1/2}+O((N/r)^{1/4} ). Our new proof not only is more
transparent but also improves the implicit constant in the upper
bound.
 MARNI MISHNA, LaCIM, Université du Québec à Montréal
Automatic combinatorial identities arising from symmetric
functions

We address two different types of combinatorial problems, both of which
have at their heart the same computation, namely the scalar product for
symmetric functions. The first incarnation of the scalar product is as
a key part of an automatic asymptotic enumeration scheme, which is
quite general in nature. The process, amenable to nonspecialists,
determines asymptotic formulas for families of combinatorial structures
with certain kind of regularity. The second application of the scalar
product illustrates how to use symbolic calculation to determine the
Kronecker product of two generating series of symmetric functions.
 LUCIA MOURA, University of Ottawa, Ottawa, Ontario K1N 6N5
Primitive pentanomials and orthogonal arrays

Munemasa (1998) investigated maximumlength binary shiftregister
sequences defined by primitive trinomials over GF(2), which give
rise to orthogonal arrays of strength 2, close to having strength
3. I will discuss ongoing research on the generalization of these
results for primitive pentanomials and their relationship with
orthogonal arrays of strength 3. This is joint work with Michael
Dewar, Daniel Panario and Brett Stevens.
 FRANK RUSKEY, University of Victoria, Victoria, British Columbia
Some recent results about Venn diagrams

We survey some recent results about Venn diagrams. Killian, Griggs,
and Savage proved that symmetric Venn diagrams exist if and only if the
number of curves, n, is prime. However, the resulting diagrams are
highly nonsimple, where a simple diagram is one with at most two
curves passing through any point. In fact, they are minimal with
respect to number of intersection points within the class of diagrams
drawable with convex curves, since they have \binomnn/2 points of
intersection. We show how to modify their construction so that the
resulting diagrams are "halfsimple" in the sense of having
asymptotically 2^{n1} points of intersection, whereas a simple
diagram has 2^{n}2 points of intersection. Time permitting, we also
present some recent constructions of pseudosymmetric and
areaproportional Venn diagrams.
 NABIL SHALABY, Memorial University of Newfoundland, St. John's,
Newfoundland AIC 5S7
Skolem and Rosatype sequences

A Skolem sequence of order n is a sequence of 2n integers from the
set {1,2,...,n} such that each integer occurs exactly twice and
the difference of the positions of two integers i is again i. For
example, 1,1,4,2,3,2,4,3, is a Skolem sequence of order 4. A Rosa
sequence is similar to a Skolem sequence except that it has a space (or
hook) in the middle position. For example 2,4,2,3,,4,3,1,1, is a
Rosa sequence of order 4. Skolem and Rosa sequences were introduced
to construct cyclic Steiner triple systems of orders 6n+1 and 6n+3
respectively. In this talk we show some mathematical relations between
these sequences and other mathematical objects, and we also introduce
some new results.
 JOHN VAN REES, Department of Computer Science, University of Manitoba,
Winnipeg, Manitoba R3T 2N2
(m,t)splitting systems and set intersection systems

Let m and t be positive integers with t ³ 2. An
(m,t)splitting system is a pair (X, B) where X = m and B is a collection of subsets of X called
blocks, such that, for every Y Í X with Y = t, there
exists a block B Î B such that B ÇY = ë[(t)/2]û. An (m,t)splitting system is uniform if
every block has size ë[(m)/2]û. In this paper, we
give several constructions and bounds for splitting systems,
concentrating mainly on the case t=3. We consider uniform splitting
systems as well as other splitting systems with special properties,
including disjunct and regular splitting systems. Some of these systems
have interesting connections with other types of set intersection
systems.
 TIMOTHY WALSH, Université du Québec à Montréal, Montreal, Quebec H3C
3P8
Generating gray codes in O(1) worstcase time per word

A Gray code is a family of word lists such that the word lengths are
unbounded but the number of positions in which two consecutive words in
any list differ is bounded independently of the word length. We show
that a nonrecursive generation algorithm can be obtained for any word
list in which all the words with the same prefix (or, equivalently,
suffix) are consecutive and that the BitnerEhrlichReingold method of
generating each word in a time bounded by a constant works under the
additional condition that in the interval of words with the same prefix
or suffix the next letter assumes at least two distinct values.
Finally we generalize this method so that it works under a weaker
condition satisfied by almost all the Gray codes in the literature: if
the next letter assumes only one value, then the interval contains only
one word.
 DAVID WEHLAU, Royal Military College of Canada, Kingston, Ontario K7K 7B4
Complete caps in PG(n,2)

A cap in PG(n,2) is a set of points in PG(n,2) no three of which
are colinear. A cap is called complete if it is maximal with
respect to inclusion in PG(n,2) and called large if it
contains at least 2^{n1}+1 points. A maximal cap with less than
2^{n1}+1 points is called small. In 1990 Davydov and Tombak
showed that the only possible cardinalities of a large complete cap
S, are S = 2^{n+1}+2^{i} for 0 £ i £ n3 or i=n1.
Much less is known about the possible sizes and structures of small
complete caps. The size of the smallest complete cap in PG(n,2) is
denoted n_{2}(n,2). Davydov has conjectured that for all n ³ 8
there exist small complete caps of all sizes k with n_{2}(n,2) £ k £ 2^{n1}1. I will discuss the state of this conjecture as well
as the best known estimates for n_{2}(n,2).
The classical doubling or Plotkin construction provides an easy
construction of caps. Indeed all caps whose size exceeds 2^{n1} may
be realized by this construction. I will describe a powerful new
technique, generalizing the doubling construction, for constructing a
great many complete caps, both large and small.
 JULIAN WEST, Malaspina UniversityCollege
Perfect matchings for the GaleRobinson sequence

A domino is a rectangle of dimensions 1 by 2. An "Aztec diamond"
of order n is a diamondshape array of squares with height and width
2n. The number of different ways of covering an Aztec diamond of
order n with dominos is 2^{n(n+1)/2}. (Alternatively this can be
viewed as the number of perfect matchings in the dual graph.) There
are a number of attractive proofs of this formula, notably the
"condensation" proof used by Eric Kuo to verify the recursion
formula. We will generalize this proof to the "GaleRobinson"
recurrences, which have the form a(n)a(nm) = a(ni)a(nj) +a(nk)a(nl), where i+j=k+l=m. (The Aztec diamond recurrence
corresponds to the case of i=j=k=l=1.) In the process, we construct
graphs analogous to the Aztec diamonds and in which the number of
perfect matchings are given by the appropriate term in the
GaleRobinson sequence. Joint work with Mireille BousquetMelou
(Bordeaux), Jim Propp (Brandeis).

