OCW/DMD 2003, Invited and Contributed Talks: Abstracts (36 talks)

INVITED TALKS IN ORDER OF APPEARANCE (8 talks)

Nick Wormald (University of Waterloo)
Title: Two choices are better than one, but by how much?
Abstract:
Many structures have been studied which are built by the successive
random insertions of elements. Examples include balls-in-bins situations
and random graphs. If a structure is built by the arrival of items which
have a choice of two random places to be inserted, rather than just one,
then by choosing judiciously, one can alter the properties of a typical
structure.  This phenomenon has been investigated for some
time in applications to hashing, routing, and load balancing of
processors. I will discuss some recent problems which this idea has 
opened up for random graphs, and some of the methods which can be 
used to tackle them.

Brian Alspach (University of Regina) 
Title: Poker and Mathematics
Abstract:
This is a talk aimed at a general audience discussing the interaction
between poker and mathematics.  Poker anecdotes will be mixed with an
examination of the role of mathematics in poker, and some of the
mathematical problems arising from poker.

Sylvia Boyd (University of Ottawa) 
Title: Methods for hard combinatorial optimization problems -- a guided tour
Abstract:           
Many combinatorial optimization problems of practical importance are
known to be NP-hard, and thus no efficient techniques are currently known
for solving them.  A prime example is the Travelling Salesman Problem
(TSP), which has applications in areas such as printed circuit board
production, vehicle routing and genetic engineering.  In this talk we will
use the TSP as the example to give a "guided tour" of some of the techniques
and approaches used to find provably good solutions for hard combinatorial
optimization problems.

Ram Murty (Queen's University)
Title: Ramanujan Graphs
Abstract:  The theory of Ramanujan graphs has become
significant in communication theory in that it solves
an important extremal problem.  However, their
explicit construction is still shrouded in mystery.
At present, all explicit constructions rely heavily
on number theory, algebraic geometry and representation
theory.  In this talk, we will give a leisurely survey
of this exciting area.  The talk should be accessible
to undergraduates.

Bill Cunningham  (University of Waterloo)
Title: Even Factors in Digraphs
Abstract: 
An even factor in a digraph is a set of even cycles
including each vertex exactly once. If the digraph
is symmetric, then it has an even factor if and only
if the underlying undirected graph has a perfect
matching. I will describe results on even factors
that extend basic results on matching, and will also
indicate some limitations, some useful techniques,
and some further generalizations. This is based on
joint work with Jim Geelen.

Endre Szemerédi (Rutgers University) 
Title: Long Arithmetic Progressions in Sum-set sums.
Abstract: Given a set A, define
        S_A = { \sum_{a \in B} a: B \subseteq A }.
We are going to prove that if A is a subset of the first n integers
with at least c n^{0.5} elements, then S_A contains an arithmetic
progression of length n.
As a corollary, we are going to present a proof for an old conjecture
of Erdos and Folkman.
This is join work with Van Vu.

Clement Lam (Concordia University)
Title: Block design existence -- when it rains, it pours
Abstract:
In some recent papers (JCTA, Vol. 92, p. 186-196 and JCD, Vol. 9, p.
363-376),
a huge number of block designs with the classical parameters were
constructed, starting from just a single design. The basic idea is that
the single design can be partitioned into two parts, and that the parts
can be combined together in an exponential number of ways.
In this talk, we shall see examples of how this idea works, and
speculate how
it can be used in a computer enumeration.

Brian Alspach (University of Regina) 
Title: Searching and Sweeping Graphs
Abstract:
A problem of practical importance is the following:  Given an intruder
in a graph, what must be done to find the intruder?  For example, a person
lost or hiding in a cave system fits into this model, or a piece of nasty
software roaming through a computer network fits into the model.  
This talk will survey some of the work done on this problem as well as look 
at some new research.


CONTRIBUTED TALKS IN ORDER OF APPEARANCE (28 talks)

Julie Anne Cain (Dept. Mathematics and Statistics, University of Melbourne)
Title:  Load balancing as a random graph process
Abstract: 
A simple example of a load balancing problem consists of a set of N discs
in parallel and a set of M requests for data stored on the discs. It was shown
by Azar, Broder, Karlin and Upfal that if we have 2 instead of 1 randomly
distributed copies of each piece of data, and we sequentially allocate each
request to the least loaded of the 2 discs containing a copy of the required
data, then the maximum load is exponentially reduced from (when M = N)
(1 + o(1)) ln N= ln ln N to ln ln N= ln 2 +O(1).
In the case of 2 copies, an oine allocation algorithm can be represented as
a random graph process. From a result of Pittel, Spencer and Wormald on the
emergence of k-cores in random graphs we know that when the ratio c = M=N
is less than the threshold for the existence of a k-core (for some integer k) then
there is an allocation method which results in maximum load being at most
k 1 a.a.s. as N ! 1. Further, if we make a little more eort with our
assignment algorithm we can achieve the same maximum load for even larger c.
This algorithm is analysed using a dierential equation method.

Sebastian Cioaba (Department of Mathematics and Statistics, Queen's University)
Title: Bounds on the Turan density of PG(3,2)
Abstract:
Bounds on the Turan density of PG(3,2) are presented. A lower bound of
 27/32=0.84375 is obtained by a construction. Using a method of de Caen
 and Furedi for determining the Turan density of PG(2,2), an upper bound
 of 27/28=0.96428... is determined.

Graeme Kemkes (Dept. of Combinatorics and Optimization, University of Waterloo)
Title: Finding Hamilton Cycles in Random Graphs
Abstract:
No one knows of an efficient method for finding Hamilton Cycles in graphs.
So, people are designing algorithms which can find Hamilton Cycles
efficiently in "most graphs". We will talk about some of these algorithms
and see how random graphs can be used to analyze their behaviour.

Atefeh Mashatan (Dept. of Combinatorics and Optimization, University of Waterloo)
Title:  Asymptotics of Combinatorial Structures with Large Smallest Component
Abstract: 
We study the probability of connectedness for structures of size $n$ when
all components must have size at least $m$. In the border between almost
certain connectedness and almost certain disconnectedness, we encounter a
generalized Buchstab function of $n/m$.

Marni Mishna (LaCIM, Université de Québec à Montréal) 
Title:  New algorithms for symmetric functions useful in combinatorial enumeration
Abstract:
The vector space of symmetric functions possesses a well-known scalar
product which has a variety of combinatorial applications. This scalar
product has been used to express generating functions of combinatorial
objects, and I. Gessel has determined some conditions to determine when
these series are D-finite.  That is, when do such series satisfy a
differential equation with polynomial coefficients?  We extend Gessel's
work by providing algorithms that compute the differential equations these
generating functions satisfy.
More precisely, we will outline algorithms to compute the differential
equation satisfied by the scalar product of two series of symmetric
functions, under certain finiteness and D-finiteness conditions. These
algorithms use Groebner bases in the algebra of differential operators.
Applications of this algorithm include:
  x   Enumeration of regular graphs, generalized involutions, latin
      squares...;
  x   An effective inner product of symmetric functions,
      (also known as the tensor or Kronecker product)
      under similar initial conditions.
More generally, we will discuss the potential uses of the theory of
holonomy and D-finite functions in the realm of enumerative combinatorics.

John P. Steinberger (Dept. of Combinatorics and Optimization, University of Waterloo)
Title: Tilings of R and roots of unity
Abstract:
We shall give a brief introduction to tilings of the real line by
translates of stacked clusters, and detail the connection between these
tilings and vanishing sums of roots of unity. (A "stacked cluster" is a
fancy word for a non-negative integer-valued function over the integers.)
As time permits, we shall show some new constructions for stacked clusters
with exotic tiling properties, and show a new visualization device for
vanishing sums of roots of unity.

Julian West (Malaspina University-College, University of Victoria)
Title: Perfect matchings for the Gale-Robinson sequence
Abstract:
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)

Natasa Przulj (Dept. of Computer Science, University of Toronto)
Title: $2$-tree probe interval graphs have a large obstruction set
Abstract: 
Probe interval graphs are used as a generalization of interval graphs in 
physical mapping of DNA.  $G=(V,E)$ is a  \emph{probe interval graph (PIG)}
 with respect to a partition $(P,N)$ of $V$ if vertices of $G$ correspond to 
intervals on a real line and two vertices are adjacent if and only if their 
corresponding intervals intersect and at least one of them is in $P$; vertices 
belonging to $P$ are called \emph{probes} and vertices belonging to $N$ are 
called \emph{non-probes}.  This definition gives rise to two PIG recognition 
problems, namely when the $(P,N)$ partition of $V$ is given, and when it is not.  
The first problem has been solved efficiently; however, the second remains open 
and is the subject of this paper. One common approach to studying the structure 
of a new family of graphs is to determine if there is a concise family of 
forbidden induced subgraphs.  It has been shown that there are $2$ forbidden 
induced subgraphs that characterize tree PIGs. In this paper we show that 
having a concise forbidden induced subgraph characterization does not extend 
to $2$-tree PIGs; in particular we show that there are at least $62$ minimal 
forbidden induced subgraphs for $2$-tree PIGs.

Anna Bretscher (Dept. of Computer Science, University of Toronto)
Title: A Simple Linear Time LexBFS Cograph Recognition Algorithm
Abstract: 
We introduce a new simple linear time algorithm to recognize cographs (graphs 
without an induced). Unlike other cograph recognition algorithms, the new algorithm 
is based on Lexicographic Breadth First Search (LexBFS), and uses a new variant 
of LexBFS, called LexBFS , operating on the complement of the given graph G   
and breaking ties with respect to an initial LexBFS. The algorithm uses an initial
LexBFS and two LexBFS-sweeps to produce the cotree of G or identify an induced.

Marina Sokolova (S.I.T.E., University of Ottawa)
Title: The Decision List Machine with Half-Spaces
Abstract:
We examine the decision list machine (DLM) when it uses data-dependent
alf-spaces for its set of features. The algorithm allows a trade-off between
raining accuracy and complexity (classifier size).
We introduce a compression scheme which enables us to bound the
DLM's generalization error in terms of the number of training errors and
he number of half-spaces it achieves on the training data. Furthermore, we
how that our bound on the generalization error provides an effective guide
or model selection.
We also show that on some natural data sets the DLM provides a favor-
ble alternative to such learning algorithms as the support vector machine
nd the set covering machine with half-spaces. Compared to the support
ector machine, the DLM with data-dependent half-spaces produces sub-
tantially sparser classifiers with comparable (and sometimes better) gener-
lization.

Reza Naseras (Department of Mathematics, Simon Fraser University)
Title: $K_5$-free Bound for the calss of Planar Graphs
Abstract: 
We define $k$-{\rm diverse} coloring of a graph to be a 
proper vertex coloring in which every vertex $x$, sees $min \{ k, 
d(x)\}$ different colors in its neighbours. We show that for given 
$k$ there is an $f(k)$ for which every planar graph admits a 
$k$-diverse coloring using at most $f(k)$ colors. Then using this 
coloring we obtain a $K_5$-free graph $H$ for which every planar 
graph admits a homomorphism to it, thus another proof for the 
result of J. Ne\v set\v ril, P. O. De Mendez. 

Gabriel Verret (University of Ottawa)
Title: Mobility of Graphs
Abstract:
Let $G$ be a graph and $g \in {\rm Aut}(G)$. The {\em mobility} of
$g$, denoted by ${\rm Mob}(g)$, is defined as $\min_{v \in {\rm
V}(G)}{\rm d}_G(v,g(v))$. The {\em (absolute) mobility} of the graph
$G$, denoted by $ {\rm Mob}(G)$, is defined as $\min_{g \in {\rm
Aut}(G)}{\rm Mob}(g)$. The {\em relative mobility} of the graph $G$ is
${\rm mob}(G) = \frac{{\rm Mob}(G)}{{\rm diam}(G)}$, where ${\rm
diam}(G)$ denotes the diameter of $G$. A direct application of
``Burnside's Lemma" yields that vertex-transitive graphs have non-zero
mobility. I will show that this bound is sharp; that is, for any
$\varepsilon 0$, there exists a vertex-transitive graph with relative
> mobility less than $\varepsilon$, and show how to construct a
vertex-transitive graph of mobility $m$ and diameter $d$ for all
integers $0<m\leq d$. This is joint work with Mateja \v{S}ajna.

Karen Meagher (Dept. of Mathematics and Statistics, University of Ottawa) 
Title: Covering arrays on Graphs
Abstract: 
Two vectors $v,w$ on $\mathbb{Z}_g$ are {\em vector independent} if
for all pairs $(a, b) \in \mathbb{Z}_g \times \mathbb{Z}_g$ there is a
position $i$ in the vectors where $(a,b) = (v_i,w_i)$. A covering
array on a graph $G$, denoted $CA(G,g)$, is an array on $\mathbb{Z}_g$
with $|V(G)|$ rows and the property that any two rows which correspond
to adjacent vertices in $G$ are vector independent. We define a family
of graphs $G(n,g)$ whose vertices are length $n$ vectors on
$\mathbb{Z}_g$ and edges join two vertices if they are vector
independent. A graph $G$ has a covering array with $n$ columns if and
only if there is a homomorphism from $G$ to $G(n,g)$. Hence, finding a
covering array on a graph is similar to finding the chromatic number,
the $r$ chromatic number or the star chromatic number of a graph.

mike newman (Department of Combinatorics and Optimization, University of Waterloo)
Title: A partition graph.
Abstract: 
Let $X$ be the graph whose vertices are the partitions of
$\{1,\ldots,n^2\}$ into $n$ partitions of size $n$ each, where for our
purposes, $n=3$. Vertices are adjacent if the corresponding partitions are
skew, that is, no part from one partition intersects a part from the other
in more than one element. The question was asked as to whether this graph
is a core. We answer this in the affirmative, and time permitting, discuss
some other properties of this graph as well.

Marcelo Henriques de Carvalho (Dept. of Combinatorics & Optimization - University of Waterloo)
Title: How to build a brick
Abstract:
One of the basic facts concerning 3-connected graphs is that "every
3-connected graph can be obtained from $K_4$ by means of edge
additions and vertex expansions", where vertex expansion consists of
splitting a vertex $x$ of degree at least four into two
vertices $x_1$ and $x_2$ and then joining $x_1$ and $x_2$ by an edge.
A graph $G$ is bicritical if $G-\{u,v\}$ has a perfect matching for
any two vertices $u$ and $v$ of $G$.  A brick is a $3$-connected
bicritical graph. Bricks play an important role in matching theory.
In this talk, we present an analogue of the above result for
bricks. More precisely, we prove that every brick distinct from $K_4$,
the complement of the cycle on six vertices and the Petersen graph can
be obtained from one of them by a sequence of application of four
operations of expansion. We also present an application of this
result.

Frank Jagla (Flint Software Inc.)
Title: Two theorems on planar graphs
Abstract: 
This talk focuses on the four color problem and presents skeleton 
proofs of two theorems: 1. Graph planarity, and 2. Four color problem. 
The introduced concepts of cycles, cycles basis, edge cyclic numbers, 
tiers and layers are crucial to the proofs.
The first theorem articulates the conditions in order for a graph
to be non-planar and its proof is based on Kuratowski's theorem
and edge cyclic numbers.
The proof of the four color theorem uses the prime and dual (vertex
and region) problem formulations. The prime problem is applied to a
graph with a vertex of degree four and its proof follows Kempe's
and Heawood's method. The dual problem uses the introduced concepts
for a graph with vertices of at least degree five.
Final remarks are on problems that the concepts are applicable to.

Genevieve Labonte (S.I.T.E., University of Ottawa)
Title:  A new separation algorithm for the subtour elimination constraints
Abstract: 
The Symmetric Traveling Salesman Problem is to find a minimum cost
Hamiltonian cycle in the weighted complete graph on n nodes.  This
problem is well known to be NP-hard even in the metric case, and thus
it is considered highly unlikely that an efficient algorithm will ever
be found for solving it.
One direction which seems promising for obtaining improved STSP
solutions is the study of a linear relaxation of the STSP called the
Subtour Elimination Problem (SEP).  The SEP can be written as a linear
program which, unfortunately, has an exponential number of
constraints.  Nevertheless, it is still possible to solve the SEP
efficiently by using a cutting plane approach.  The core of the
cutting plane algorithm is identifying a violated constraint for the
current optimal solution.  This problem is called the separation
problem.  Currently, the best separation algorithm to find such a
violated constraint has an O(n^4) complexity.
In this talk, I will present a new algorithm for separating over the
subtour elimination constraints (a set of valid constraints for the
SEP).  The algorithm described in the talk is based on a decomposition
methodology which was first introduced to us by Dr. Pulleyblank at the
Ottawa-Carleton Discrete Math Day 2002.  The approach presented is
particularly suited to parallel computers and could easily be adapted
to many other separation problems in combinatorial optimization.

Francisco J. Zaragoza (Department of Combinatorics and Optimization, University of Waterloo)
Title: A Restricted Postman Problem on Mixed Graphs
Abstract: 
Given a strongly connected mixed graph $M$, with nonnegative costs on its
edges and arcs, the mixed postman problem is to find a minimum cost tour
of $M$ traversing all its edges and arcs at least once. A generalization
of this problem is to require that the tour traverses a given subset $R$
of {\em restricted} edges and arcs exactly once. In this talk we present
some results obtained for special choices of $R$.

Kevin Cheung (University of Waterloo)
Title: On a class of 4-regular planar graphs of inscribable type
Abstract: 
A classical result due to Steinitz that connects
graph theory to geometry states that a graph can
be realized by a 3-dimensional polytope if and
only if it is 3-connected and planar.  If a
3-connected planar graph can be realized by a
3-dimensional polytope inscribed in a sphere, it
is said to be of inscribable type.  The problem of
determing which 3-connected planar graphs are of
inscribable type dates back to at least 1832 when
Jakob Steiner mentioned it in a book.  The problem
was open for over a century until Igor Rivin in
the early 1990s gave a necessary and sufficient
condition that can be checked in polynomial time
using linear programming methods.  Since then,
certain graph-theoretical necessary conditions as
well as sufficient ones for graphs of inscribable
type have emerged.  However, a complete
graph-theoretical characterization is not yet
known.
Dillencourt and Smith (1995) gave a
graph-theoretical characterization for cubic
planar graphs that are of inscribable type.
However, a graph-theoretical characterization for
4-regular planar graphs of inscribable type is
still open.  In this talk, I will settle a
question raised by David Eppstein and describe an
infinite class of 4-regular graphs of inscribable
type.

Megan Dewer (School of Mathematics and Statistics, Carleton University)
Title:  An Interval Colouring Approach to the Computer Test Scheduling Problem
Abstract:  
When a new computer chip comes off the assembly line it must undergo a
series of tests to determine if it is functioning correctly.  Computer
chip test scheduling is a problem that has become more important as
the size of chips and number of chips connected on a board has
increased.  The determination of tests and the order in which they are
carried out is a well-researched area of electrical engineering and
computer science.  However, the algorithms used to determine a
schedule for these tests are based on clique covers or greedy
colouring.  I present a method that uses interval colouring to
determine a near-optimal test schedule.

Bohdan Kaluzny (McGill University)
Title: Solving Inequalities and Proving Farkas's Lemma Made Easy
Abstract: 
We present a simple algorithm that finds a nonnegative solution
to a system of linear inequalities. This algorithm can be taught to
secondary or college level students who have learned how to solve a
system of linear equations. The algorithm is a dual version of Bland's
rule for linear programming. We present a simple proof of finiteness
which leads to a simple proof of Farkas's Lemma.

Paul Elliott (Wilfrid Laurier University)
Title: Multicommodity Flows and Signed Graphs
Abstract:
Multicommodity flows are a generalization of
network flows where we allow multiple source-sink
pairs (which we call commodities).  The cut condition
states that the total demands of commodities separated
by a cut cannot exceed the total capacity of the cut.
We are interested in discovering for which
multicommodity flow problems is the cut condition both
necessary and sufficient for the existence of an
integer solution.  There are several historical
results in this area, the most famous being the
Max-flow/Min-cut Theorem proved by Ford and Fulkerson.
 We will discuss a theorem by P.D. Seymour which
unifies many of these historical results.
Furthermore, we will see how the use of signed graphs
can lead to a characterization of multicommodity flow
problems for which the cut condition is both necessary
and sufficient for the existence of an integer
solution.


Ariane Masuda (School of mathematics and statistics, Carleton University)
Title: A characterization of permutation polynomials based on their coefficients.
Abstract: 
We give a characterization of permutation polynomials over a finite 
field $\mathbb F_{q}$ based on their coefficients. As a result,
explicit conditions for a polynomial to be a permutation polynomial 
are given when $q=2$, $3$, $5$. Moreover, permutation binomials over 
$\mathbb F_{q}$ are completely described. New classes of permutation 
binomials and polynomials can be constructed accordingly.
This is joint work with D. Panario (Carleton University) and
S. Q. Wang (University of Lethbridge).

Alastair Farrugia (Dept. of Combinatorics and Opimization, University of Waterloo)
Title: Primal sets and dually vertex-oblique graphs 
Abstract: 
Some sets have a primal urge to generate other sets efficiently. For
example a basis $B$ generates a vector space $V$ using linear
combination. The set $P$ of prime numbers (from which Dewdney obtained
the term `primal') generates the positive integers using multiplication.
Moreover, $B$ (and $P$) is minimal: for any $b \in B$, $B-b$ does not
generate $V$. A {\em primal set} is just a minimal generating set.
Are there primal sets in other contexts? Are they unique? And what if we
want a stronger form of minimality? We examine these questions when
generating the set of (positive) integers, rationals or reals, using
some variant of addition or multiplication.
We are particularly interested in ``addition of distinct numbers''. With
this operation, the powers of $2$ are a well-known (though by no means
unique) primal set for the positive integers, but we have shown that
there is no primal set for the positive reals. We also know what a
primal set for the positive rationals must look like, but we conjecture
that there is no such set.
This work, financed by a Canadian Commonwealth Scholarship and NSERC,
was done jointly with Bruce Richter, as well as Therese Biedl, Erik
Demaine and Rudolf Fleischer.

YoungBin Choe (Dept.of Combinatorics & Optimization, University of Waterloo)
Title: Polynomials with the Half-Plane Property and Rayleigh Monotonicity
Abstract:
A polynomail $P(x)$ in $n$ complex variables is said to have the
half-plane property if $P(x)\neq 0$ whenever all the variables
have positive real parts. The generating polynomial for the set of
all spanning trees of a graph $G$ is one particular example of the
polynomials with the half-plane property. Providing that the edge
sets of the spanning trees of $G$ constitute the set of bases, we
might wonder if the same would hold for any such polynomials. I
proved that the support of any homogeneous multiaffine polynomial
with the half-plane property constitutes the set of all the bases
of a matroid. By relaxing the multilinearity condition we can show
that the support is a jump system. When the polynomial has a
definite parity with the half-plane property, the support is a
jump system. Another nice property of the spanning tree generating
polynomial is the Rayleigh monotonicity property. In this paper I
prove that the property holds for all the spanning tree generating
polynomials using the All-Minors Matrix-Tree Theorem and Jacobi
identity. I will show that the same property holds for the
generating polynomial for any regular matroid and 6th-root of
unity matroid. Open problems and a few directions for further
research will also be discussed.

Michael Dewar (School of Mathematics and Statistics, Carleton University)
Title: Linear Transformation Shift Registers
Abstract: 
Sequences in Finite Fields are used in a variety of applications in coding
theory and cryptography. Linear Feedback Shift Registers (LFSRs) play an
important role in the generation of sequences with long periods. In order to
exploit word-oriented operations for LFSRs, Tsaban and Vishne introduce
the notion of linear Transformation Shift Registers (TSRs) in \Efficient Lin-
ear Feedback Shift Registers with Maximal Period", Finite Fields and their
Applications, vol. 8, pp. 256-267, 2002. They combine primitive linear trans-
formations of order m and LFSRs of order n to create these TSRs. The TSR
has a characteristic polynomial 
\[
f_{(T,S)}(\lambda) = f_{S}(\lambda)^mf_{T}\left(\frac{\lambda^{n}}{f_{S}(\lambda)}\right),
\]
 where $f_{S}(\lambda)$ and $f_{T}(\lambda)$
are the characteristic polynomials of the LFSR S and the trans-
formation T . If $f_{(T,S)}(\lambda)$ is primitive, then the TSR will have period 2 mn 1.
Although Tsaban and Vishne give procedures to check the primitivity of
the TSR, the search for desirable TSRs can be computationally intensive for
large m and n. Tsaban and Vishne argue that Finding irreducible TSRs is
the most diÆcult part of the process as most of these will be primitive.
We conducted an exhaustive search for primitive TSRs involving LFSRs
and linear transformations each of order less than 10. It was noticed that LF-
SRs with characteristic polynomials having an odd number of terms formed
pairs in which the TSRs involving one of them are irreducible for exactly
the same linear transformations as the other LFSR of the pair. We formally
prove that this is the case. Furthermore, there is a correspondence between
the pairings of LFSRs of different orders.
We propose a method to eectively double the eÆciency of the search for
primitive TSRs. For any given n, half of the LFSRs are paired in such a way
that their TSRs are irreducible for exactly the same linear transformations.
Once a single pair has been identiFied, we can quickly generate paired LFSRs
for arbitrarily large orders. Indeed, the pairings of LFSRs can be completely
determined from the pairings of smaller orders. Although it is still necessary
to nd suitable primitive transformations for these paired LFSRs, by concen-
trating our eorts on the pairable LFSRs, we can get two irreducible TSRs
for the computational price of one.
This is joint work with Daniel Panario.

Cedric Chauve (LaCIM, UQAM)
Title: Factorizations of signed permutations
Abstract:
  We consider a problem related to the factorizations of
  elements of  the wreath product of the symmetric group $\sn$ by $\Z
  / k\Z$. More precisely, for a given integer $k$, we give a
  combinatorial construction relating factorizations of elements in
  the wreath product of $\sn$ by $\Z / k\Z$ and factorizations in $\sn$.
  Our proof relies on the encoding of such factorizations as maps with
  signed edges and can be generalized to the factorization of
  permutations of any cycle type.
Resume :
  Nous consid\'erons un probl\`eme concernant les
  factorisations d'\'el\'ements du produit en couronne du groupe
  sym\'etrique $\sn$ par $\Z / k\Z$. Plus pr\'ecis\'ement, pour un
  entier $k$ donn\'e, nous  pr\'esentons une construction combinatoire
  reliant factorisations dans le produit en couronne de $\sn$ par $\Z
  / k\Z$ et factorisations dans $\sn$. Notre preuve repose sur le
  codage de factorisations par des cartes aux ar\^etes sign\'ees
  et peut \^etre g\'en\'eralis\'ee aux factorisations de permutations
  de type cyclique quelconque.
This is joint work with Alain Goupil and Dominique Poulalhon

Benjamin Steinberg (School of Mathematics and Statistics, Carleton University)
Title: On embedding graphs in Cayley graphs
Abstract: 
Given a finite graph labelled over a finite alphabet (i.e. a
finite state automaton), it is natural to asked whether it embeds in the
(so-called labelled or colored) Cayley graph of a group (or maybe of a
finite group, or an Abelian group, or your favorite sort of group).  
There are some obvious necessary conditions:  the relation on vertices
corresponding to each letter of the alphabet must be a partial bijection;
any word that labels a loop at one vertex must label a loop at every
vertex from which it can be read.  However, there is a missing condition
which is algebraic (semigroup-theoretic) and which turns out to be 
undecidable.
In fact, if H is a class of groups satisfying some mild closure properties
(i.e. closed subgroups, finite products, quotients), the the problem of
determining whether a finite labelled graph embeds in a Cayley graph of a
group from H is equivalent to the uniform word problem for H and to an
algebraic problem about ideal quotients of inverse semigroups.
Incidentally, the techniques involved show easily that there are
finite labelled graphs which embed in the Cayley graph of an infinite
group, but not the Cayley graph of a finite group.