---

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 m-rowed 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^k-1) 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 Littlewood-Richardson coefficients

We give new results about a fascinating conjecture of Fulton, Fomin, Li and Poon concerning inequalities for Littlewood-Richardson 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 quasi-symmetric 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

{bij-bis | 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 (Level-dependent 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₁ < ¼ < 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 non-specialists, 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 maximum-length binary shift-register 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 non-simple, 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 "half-simple" in the sense of having asymptotically 2^n-1 points of intersection, whereas a simple diagram has 2ⁿ-2 points of intersection. Time permitting, we also present some recent constructions of pseudo-symmetric and area-proportional Venn diagrams.

NABIL SHALABY, Memorial University of Newfoundland, St. John's, Newfoundland  AIC 5S7
Skolem and Rosa-type 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) worst-case 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 non-recursive 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 Bitner-Ehrlich-Reingold 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 co-linear. 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^n-1+1 points. A maximal cap with less than 2^n-1+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ⁿ⁺¹+2ⁱ for 0 £ i £ n-3 or i=n-1.

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₂(n,2). Davydov has conjectured that for all n ³ 8 there exist small complete caps of all sizes k with n₂(n,2) £ k £ 2^n-1-1. I will discuss the state of this conjecture as well as the best known estimates for n₂(n,2).

The classical doubling or Plotkin construction provides an easy construction of caps. Indeed all caps whose size exceeds 2^n-1 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 University-College
Perfect matchings for the Gale-Robinson sequence

A domino is a rectangle of dimensions 1 by 2. An "Aztec diamond" of order n is a diamond-shape 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 "Gale-Robinson" recurrences, which have the form a(n)a(n-m) = a(n-i)a(n-j) +a(n-k)a(n-l), 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 Gale-Robinson sequence. Joint work with Mireille Bousquet-Melou (Bordeaux), Jim Propp (Brandeis).