


Combinatorics
Org: Peter Dukes and Frank Ruskey (Victoria) [PDF]
 KAROLY BEZDEK, University of Calgary, 2500 University Drive N.W., Calgary,
AB T2N 1N4
The illumination problem and the cube
[PDF] 
Let K be an arbitrary convex body in ddimensional Euclidean space
and let 1 < k < d be some fixed nonnegative integer. Then let I(k,K)
denote the smallest number of kdimensional affine subspaces that
illuminate K. According to a conjecture of K. Bezdek (1994), if C
denotes the ddimensional unit cube, then I(k,K) is always at most
as large as I(k,C). In the talk we survey the status of this
conjecture including the more recent results on the rather
combinatorial quantity I(k,C).
 ILIYA BLUSKOV, University of Northern BC
Pair Covering Designs with Block Size 6
[PDF] 
A t(v,k,l) covering design, denoted
(V,B), where v=V, is a finite
family B of ksubsets of V, called
blocks, such that each tsubset of V occurs in at
least l blocks. The covering number C_{l}(v,k,t)
is minB, where the minimum is taken over all
t(v,k,l) covering designs. My talk is based on a recent
joint work (with Abel, Greig and de Heer) on the covering number
C_{1}(v,6,2). This number meets the Schönheim bound:
C_{1}(v,k,2) ³ 
é ê


v
k


é ê


v1
k1


ù ú


ù ú

. 

We show that C_{1}(v,6,2) attains the Schönheim bound for all v º 2 mod 5. I will discuss direct combinatorial constructions
and computer assisted searches related to this result.
 AIDEN BRUEN, U. of Calgary, Dept. of Mathematics and Statistics
Combinatorial characterizations of perfect secrecy
[PDF] 
We discuss entropy in classical information theory and Shannon's
concept of perfect secrecy in cryptography. Examples include the
Vernam cipher, also known as the onetime pad. Under suitable
conditions we prove the equivalence of perfect secrecy with a
wellknown class of combinatorial structures. We then proceed to
discuss analagous questions in quantum information theory. This in
turn leads to a muchstudied and fundamental classical question in
combinatorics dating back to Euler. We conclude, time permitting,
with some "philosophical musings".
 JONATHAN JEDWAB, Simon Fraser University, 8888 University Drive, Burnaby, BC
V5A 1S6
Proof of the Barker array conjecture
[PDF] 
Using only elementary methods, we prove Alquaddoomi and Scholtz's
conjecture of 1989, that no s ×t Barker array having s, t > 1 exists except when s = t = 2.
Joint work with J. A. Davis and K. W. Smith.
 VESELIN JUNGIC, Simon Fraser University, Burnaby, BC
Ramsey Rainbow Theory
[PDF] 
The van der Waerden theorem in Ramsey theory states that, for every
k and t and sufficiently large N, every kcoloring of [N]
contains a monochromatic arithmetic progression of length t.
Motivated by this result, Radoici\'c conjectured in 2001 that
every equinumerous 3coloring of [3n] contains a 3term rainbow
arithmetic progression, i.e., an arithmetic progression whose
terms are colored with distinct colors. This conjecture initiated a
serious results having rainbow structures as the common theme. One
such result is that every 3coloring of the set of natural numbers
for which each color class has density more than 1/6, contains a
3term rainbow arithmetic progression. A similar results for
colorings of Z_{n} is true.
In this presentation an overview of the current state in research
directions in the rainbow Ramsey theory will be given. I will list
results, problems, and conjectures related to existence of rainbow
arithmetic progressions in [n] and N. A general
perspective on other rainbow Ramseytype problems will be given.
 MARK KAYLL, University of Montana, Missoula, MT, USA
A variation of chip firing
[PDF] 
A chipfiring game on a graph G=(V,E) begins by placing a
configuration C: V®N of chips on its vertices. Then
single chips are added sequentially to vertices selected uniformly at
random. If, after any step, a vertex v contains more chips than its
threshold, i.e., if C(v) > deg(v), then v fires,
sending one chip to each neighbor and losing one chip to the `ether'.
A firing event may trigger subsequent firings; these play out as long
as possibleuntil the chip configuration is `relaxed'at which
point a new vertex is seeded, and the process repeats. This talk
surveys some results on this version of chip firing, a variant on one
studied by Bjorner, Lovász, Shor and others in the early 1990s. A
sample (perhaps surprising) result: if the relaxed configurations are
viewed as states in a Markov chain, then its stationary distribution
is uniform over all `legal' configurations.
This joint work with David Perkins (Houghton College, NY) forms the
basis for his recent PhD thesis.
 HADI KHARAGHANI, University of Lethbridge
On productive Hadamard matrices
[PDF] 
A regular Hadamard matrix with row sum 2h is called
productive if there is a set H of matrices with row
sum 2h and a cyclic group G = \precs\succ where s: H ® H is a bijection, such that
 H Î H,
 For any H_{1},H_{2} Î H, (sH_{1})(sH_{2})^{t} = H_{1} H_{2}^{t},
 G=4h,
 å_{q Î G} qH = 2[(h)/(h)] J.
We show that for each integer n for which there is a Hadamard matrix
of order 4n and 8n^{2}1 is a prime number, there is a productive
regular Hadamard matrix of order 16n^{2}(8n^{2}1)^{2}. Applications
include a new class of symmetric designs.
This is a joint work with Majid Behbahani.
 ESTHER LAMKEN, c/o Dept. of Math, UC Berkeley, Berkeley, CA
A few more Kirkman squares with block size 3
[PDF] 
In a series of papers, I established the existence of Kirkman squares
with block size 3 for (m,l) = (1,2), (2,4) and the existence
of doubly near resolvable (v,3,2)BIBDs with a small number of
exceptions. Recently, Julian Abel, Jinhua Wang, and I have
constructed designs for all of the open cases. In addition, we
constructed several more Kirkman squares with block size 3 and
m = l = 1. In this talk, I will describe some of our new
constructions.
 PIERRE LEROUX, Université du Québec à Montréal, LaCIM et
Département de mathématiques
Characterization and enumeration of projectiveplanar and
toroidal K_{3,3}subdivisionfree graphs
[PDF] 
In his 2003 Ph.D thesis at University of Manitoba, Andrei Gagarin has
studied graph embeddability on the projective plane and the torus,
from an algorithmic point of view, particularly when avoiding
K_{3,3}subdivision. Building on his results, we have been able to
determine completely the structure of projective planar and toroidal
K_{3,3}subdivisionfree graphs and to enumerate them.
Their characterization is expressed in terms of substitution of
2pole planar networks for the edges of canonically defined
nonplanar graphs called projectiveplanar cores and
toroidal cores respectively.
Their enumeration (both labelled and unlabelled) is achieved by using
methods developed by T. Walsh in 1982 for edge substitutions in the
context of 3connected and homeomorphically irreducible 2connected
graphs.
This is joint work with Andrei Gagarin and Gilbert Labelle.
 PETR LISONEK, Department of Mathematics, Simon Fraser University, Burnaby,
BC V5A 1S6
Combinatorial families enumerated by quasipolynomials
[PDF] 
We say that the sequence (a_{n}) is quasipolynomial in n if there
exist polynomials P_{0},...,P_{s1} such that a_{n}=P_{i}(n) where
i º n mod s. We present several families of combinatorial
structures with the following properties: Each family of structures
depends on two or more parameters, and the number of isomorphism types
of structures is quasipolynomial in one of the parameters whenever
the values of the remaining parameters are fixed to arbitrary
constants. For each family we are able to translate the problem of
counting isomorphism types of structures to the problem of counting
integer points in a union of parameterized rational polytopes. The
quasipolynomiality of the counting sequence then follows from
Ehrhart's result about the number of integer points in the sequence of
integral dilates of a given rational polytope. The families of
structures to which this approach is applicable include combinatorial
designs, linear and unrestricted codes, and dissections of regular
polygons.
 ERIC MENDELSOHN, University of Toronto
When Systems Collide
[PDF] 
We present a conjecture which is a common generalization of the
DoyenWilson Theorem and Lindner and Rosa's intersection theorem for
Steiner triple systems. Given u,v, º 1,3 mod 6, u < v < 2u+1
we ask for the minimum r such that there exists a Steiner triple
system (U,B), U=u such that some partial system (U,B
\\pmb\mathfrak d) can be completed to a STS(v), (V,B¢), where
\pmb\mathfrak d = r. In other words, in order to "quasiembed" an STS(u)
into an STS(v), we must remove r blocks from the small system, and
this r is the least such with this property. One can also view the
quantity u(u1)/6r as the maximum intersection of an STS(u) and
an STS(v) with u < v. We conjecture that the necessary minimum r = (vu)(2u+1v)/6 can be achieved, except when u=6t+1 and v=6t+3,
in which case it is r = 3t for t ¹ 2, or r=7 when t=2.
Using small examples and recursion, we solve the cases vu=2 and
4, asymptotically solve the cases vu=6,8,10, and further show for
given vu > 2 that an asymptotic solution exists if solutions exist
for a run of consecutive values of u (whose required length is no
more than vu). Some results are obtained for v close to 2u+1
as well. The cases where v » 3u/2 seem to be the hardest. For
intersections sizes between 0 and this maximum we generalize Lindner
and Rosa's intersection problem"determine the possible
numbers of blocks common to two Steiner triple systems STS(u),
(U,B), U=V" to the cases STS(v), (V,B¢), with U Í V and solve it completely for vu=2,4 and for v ³ 2u3.
Joint work with P. Dukes.
 MARNI MISHNA, Simon Fraser University, 8888 University Drive, Burnaby, BC
Walks in the quarter plane
[PDF] 
We consider twodimensional lattice walks, with a fixed set of step
directions, restricted to the first quadrant. These walks are well
studied, both in a general context of probabilistic models, and
specifically as particular case studies for particular cases of
direction sets. The goal here is to examine two series associated to
these walks: a simple length generating function, and a complete
generating function which encodes endpoints of walks, and to determine
combinatorial criteria which decide when these series are algebraic,
Dfinite, or none of the above. We shall present an (almost)
complete classification of all nearest neighbour walks where the set
of directions is of cardinality three, and discuss how this leads to a
natural, well supported, conjecture for the classification of nearest
walks with any direction set.
Work in progress with M. BousquetMelou.
 DANIEL PANARIO, School of Mathematics and Statistics, Carleton University,
1125 Colonel By Drive, Ottawa, ON K1S 5B6
Asymptotics of largest and smallest components in
combinatorial structures
[PDF] 
We study the extremal size of components in decomposable combinatorial
structures. We have in mind combinatorial objects such as
permutations that decompose into cycles, graphs into connected
components, polynomials over finite fields into irreducible factors
and so on. The probability that the size of the smallest components
of combinatorial objects of size n be at least m is explained by
the Buchstab function, as shown by Panario and Richmond (2001) using
the FlajoletOdlyzko singularity analysis method. In this talk, we
adapt Buchstab's recursive arguments for integers to combinatorial
objects. We study the probability of connectedness for structures of
size n when all components have size at least m. In the border
between almost certain connectedness and almost certain
disconnectedness, we encounter a generalized Buchstab function.
For largest components, using singularity analysis, Gourdon (1996) has
studied the probability that structures of size n have all
components of size at most m. We also give a recursive argument for
the probability of connectedness for structures of size n when all
components have size at most m. In this case, our results are given
in terms of a generalized Dickman function. The Dickman function
appears when studying the largest prime factor of a random integer
between 1 and n.
We apply these results to several combinatorial structures such as
permutations, polynomials over finite fields, labelled 2regular
graphs, functional digraphs, trees (unrooted and rooted case),
labelled and unlabelled graphs, Achiral trees, and kpoint labelled
stars.
Based on joint works with: Ed Bender, Atefeh Mashatan and Bruce
Richmond (JCTA 2004) and Mohamed Omar, Bruce Richmond and Jacki
Whitely (to appear in Algorithmica).
 ANDREW RECHNITZER, University of Melbourne
Disproving things is easier when you know they are
falseexperimenting with two conjectures on patternavoiding
permutations
[PDF] 
Perhaps the most important mathematical idea that I have learnt was
that "It is always easier to prove something when you know it is
true."
I have used this idea a great deal in my work; computeraided number
crunching has been a crucial part of many of my results.
Recently I was introduced the problem of counting patternavoiding
permutations, which arises in different contexts in computer science
and algebra. In the last decade or so it has been subject to a great
deal of work and a number of conjectures have been made. Some of
these have recently been proved, but much work remains to be done.
In this talk I will give a quick discussion of patternavoiding
permutations before focussing on some of the experimental work I have
done which led me to realise (but not prove) that two open conjectures
were false. Thankfully it is easier to disprove something when
you know it is false, and I will show you how we disproved one
conjecture and (given time) some of our work towards disproving the
other.
 FRANK RUSKEY, University of Victoria, Victoria, BC
Counting strings over the integers mod a power of two with
given elementary symmetric function evaluations
[PDF] 
Let a be a string over Z_{q}, where q = 2^{d}. The jth
elementary symmetric function evaluated at a is denoted
e_{j}(a). We study the cardinalities S_{q} (m;t_{1},t_{2},...,t_{t}) of the set of length m strings for which
e_{i}(a) = t_{i}. The profile k(a) = ák_{1},k_{2},...,k_{q1} ñ of a string a is the
sequence of frequencies with which each letter occurs. The profile of
a determines e_{j}(a), and hence S_{q}. Let h_{n}: Z_{2n+d1}^{(q1)} ® Z_{2d}[z] mod z^{2n} be the
map that takes k(a) mod 2^{n+d1} to the polynomial
1 + e_{1}(a) z + e_{2}(a) z^{2} + ¼+e_{2n1}(a) z^{2n1}. We show that h_{n} is a group
homomorphism and establish necessary conditions for membership in the
kernel for fixed d. The kernel is determined for d = 2,3. The
range of h_{n} is described for d = 2. These results are used to
"efficiently" compute S_{4} (m;t_{1},t_{2},...,t_{t}).
This is joint research with Bob Miers at UVic.
 CARLA SAVAGE, North Carolina State University
Partitions and compositions defined by digraphs
[PDF] 
We consider the enumeration of nonnegative integer sequences
a_{1},a_{2},...,a_{n} satisfying a system C inequalities of the form
a_{i} ³ a_{j} + b_{i,j}. In this case, C can be modeled by a
directed graph with vertices 1,...,n and with an edge from i to
j of weight b_{i,j} for each constraint a_{i} ³ a_{j} + b_{i,j}
in C. Many familiar systems can be modeled in this way, including
ordinary partitions and compositions, plane partitions, monotone
triangles, plane partition diamonds, and solid partitions.
We develop special tools tailored to computing the generating function
of sequences defined by a digraph and show how to apply these tools
strategically to solve some nontrivial enumeration problems in the
theory of partitions and compositions. The focus is on deriving
a recurrence for the generating function when the digraph has a
recursive structure. Part of this process can be (and has been)
automated.
This is joint work with Will Davis, Sunyoung Lee, and Erwin D'Souza.
 BRETT STEVENS, Carleton University, 1125 Colonel By Dr., Ottawa, ON K1S 5B6
Maximally Pair Separated Round Robin Tournaments: Ordering
the Blocks of a Design
[PDF] 
In a Round Robin Tournament with multiple edges, we can ask that we
schedule the successive games between any given pair as far apart in
time as possible. We show that for a cyclic n day, l = 2,
tournament schedule on n players it is impossible to ask that
successive game for the same pair be at least ën/2 û
days apart. However we also show that if we allow a small number to
be separated by ë(n2)/2 û days apart, then such a
schedule is possible. These orderings fit into an interesting unifying
framework that brings together quite a few previously known results.
 STEPHANIE VAN WILLIGENBURG, University of British Columbia
Multiplicity free expansions of Schur Pfunctions
[PDF] 
Schur P functions arise, for example, as the generating function of
shifted tableaux, and can be expressed as a linear combination of the
better known Schur functions using the shifted LittlewoodRichardson
rule.
In this talk we will give specific criteria for when the
aforementioned expression is multiplicity free. From here we will
apply this result to determine when the multiplicity of an irreducible
spin character of the twisted symmetric group in the product of a
basic spin character with an irreducible character of the symmetric
group is multiplicity free.
This is joint work with Kristin Shaw.

