


Discrete Mathematics / Mathématiques discrètes (Org: Vaclav Linek)
 JASON BROWN, Dalhousie University
Wellcovered vector spaces of graphs

A weighting of a graph G is a function f:V(G)® F that assigns a value from the field
F to each vertex of G. A wellcovered weighting f
of a graph G has the additional property that there is some value K
such that å_{x Î M}f(x)=K for every maximal independent set M
of G. The wellcovered weightings form a vector space, and in this
talk we shall explore some recent results on both the dimension of the
vector spaces, as well as uses of wellcovered weightings for
structural theorems on a class of wellcovered graphs.
 CHONG SUH CHUN, Athabasca University
The maximum sum of the values on the edges of a given graph

Let G be a graph with n vertices. We weigh each vertex v_{i} a
weight z_{i} ³ 0 with å_{i = 1}^{n} z_{i} = 1. We define S = åz_{i} z_{i} , where the sum is taken over all edges of {v_{i} ,v_{j} }.
In this paper we investigate the type of sub graph and the S = åz_{i} z_{i} could achieve maximum. We also try to find sub graph where
the maximum value of the S = åz_{i} z_{i} occurs using nonlinear
programing.
 NANCY CLARKE, Department of Mathematics and Statistics, Acadia University,
Wolfville, Nova Scotia B4P 2R6
Cops and robber played with partial information

A game that is a mixture of Searching and Cops and Robber is
introduced. The cops play with partial information provided first via
selected edges of a graph and then via selected vertices. The robber
plays with perfect information. When the partial information includes
just the robber's position, bounds are given for the amount of
information required by a single cop to guarantee the capture of the
robber on a tree. When the partial information includes the robber's
direction in addition to his position, bounds are given for the amount
of information required by a cop to win on a tree, and with less tight
bounds, on a copwin graph.
 ROB CRAIGEN, University of Manitoba, Winnipeg Manitoba
Classes of orthogonal matrices

This is a largely expository talk about various types of orthogonal
matrices, their relationship to important configurations and each
other; several new objects (indicated by asterisks) will be discussed
and placed in the framework.
We will discuss (ordinary) Hadamard matrices, weighing matrices,
orthogonal designs, ButsonHadamard matrices, unit Hadamard and (*unit
weighing) matrices, Inverse orthogonal (and *I0weighing matrices),
(group) generalized Hadamard (and weighing) matrices, Difference
matrices, *permutation Hadamard (and *permutation weighing) matrices,
*power Hadamard matrices (and *power weighing matrices). A common
framework for discussing such objects, and a proposal for a unified
theory, will be discussed. Some open questions will be mentioned.
 JAMES CURRIE, University of Winnipeg, Winnipeg, Manitoba R3B 2E9
The probabilistic method and problems in semigroups

A large class of problems in combinatorics on words involves deciding
the existence/nonexistence of sequences avoiding patterns. Classical
examples include nonrepetitive words, words avoiding abelian powers,
and Dejean's conjecture concerning words avoiding fractional powers. In
conjunction with the existence questions are extremal problems: A
large class of problems in combinatorics on words involves deciding the
existence/nonexistence of sequences avoiding patterns. Classical
examples include nonrepetitive words, words avoiding abelian powers,
and Dejean's conjecture concerning words avoiding fractional powers. In
conjunction with the existence questions are extremal problems:
 What is the least alphabet size for avoiding (abelian) x^{k}
 What is the least k such that x^{k} is Savoidable?
 What is the least L such that x^{k} is Savoidable for
x ³ L?
I show how these existence questions and extremal problems can be
attacked and sometimes resolved using the probabilistic method.
 TERRY GANNON, University of Alberta, Edmonton
Graph theory in string theory

In my talk I will describe how a problem in the spectra of graphs plays
a fundamental role in string theory and conformal field theory. I will
also describe some recent work on it by Vaclav Linek and myself.
 IAN GOULDEN, University of Waterloo, Waterloo, Ontario N2L3G1
Ramified covers, symmetrization and Lagrange's Theorem

Hurwitz numbers count connected ramified covers, of given degree, of
the sphere by a Riemann surface of given genus. There is much known
about Single Hurwitz numbers, in which ramification is arbitrary at a
single branch point, and simple (i.e., two sheets of the Riemann
surface are exchanged) at all other branch points. In this talk we also
consider Double Hurwitz numbers, with arbitrary ramification at two
specified branch points.
Hurwitz numbers can be treated combinatorially because, from Hurwitz,
they enumerate factorizations in the symmetric group. The condition
that the cover is connected translates to the condition that the
factors, together, act transitively on the points.
We describe various results for Hurwitz numbers that feature
symmetrization and transformations of variables in the generating
series. The transformations of variables that simplify the series can
be inverted by Lagrange's Implicit Function Theorem, and correspond to
functional equations with an apparently combinatorial form. However, we
do not know a combinatorial explanation for these transformations.
 STEVE KIRKLAND, University of Regina, Regina, Saskatchewan S4S 0A2
Digraphbased conditioning for Markov chains

For an irreducible stochastic matrix T, we consider a certain
condition number c(T), which measures the stability of the
corresponding stationary distribution when T is perturbed. We
characterize the strongly connected directed graphs D such that
c(T) is bounded as T ranges over S_{D}, the set of
stochastic matrices whose directed graph is contained in D. For those
digraphs D for which c(T) is bounded, we find the maximum value of
c(T) as T ranges over S_{D}.
 PIERRE MATHIEU, Laval

 SHAI MOORE, University of Winnipeg
Recursive and parameterized constructions for all
kextended Langford sequences of large defect, hooked and
unhooked

A classical Skolem sequence is an integer sequence d_{1},¼,d_{2n}
where d_{i} Î [1,n] and d_{i} occurs exactly twice, with the two
occurences exactly d_{i} positions apart. A natural generalization is
a Langford sequence of defect d and length m, which is a partition
of the (integer) set S = [1,2m] into all differences from the set
D=[d,d+m1]. A kextended Langford sequence of defect d and length
m is an integer sequence s_{1},¼,s_{2m+1} where s_{k} = 0, and each
s_{i} ¹ s_{k} comes from D. Once again each difference of D occurs
exactly twice in the sequence and the two occurences of i Î D are
separated by exactly i1 symbols. (e.g. 36734506475 is an
extended Langford sequence of defect 3 and length 5.) A hooked
seqeuence is a variant where the second position also has a zero.
The problem of constructing all possible kextended Langford
sequences given d, m was solved by C. Baker for d=1 and Linek and
Jiang for d=2,3. For d > 3 the general problem is still open but we
give a partial solution which holds for all possible defects where the
length of the Langford sequence, m, is a function of the defect,
d. Our result allows us to easily extend the preceding results, and
more importantly it reduces the general problem to consideration of a
finite number of lengths, m, for each fixed defect, d.
 ERIC MOORHOUSE, Department of Mathematics, University of Wyoming
On the chromatic number of the plane

Define two points (x,y), (x¢,y¢) of K^{2} (the affine plane over an
arbitrary field K) to be adjacent if (x¢x)^{2}+(y¢y)^{2}=1.
Determination of the chromatic number c(K^{2}) of the plane is a
very difficult (and in most cases open) problem; for example for the
Euclidean plane the best that is known is that this number is 4, 5, 6
or 7. We discuss some interesting numbertheoretical questions (with
only partial answers) arising in the study of this problem.
 ANNA STOKKE, Brandon University, Brandon, Manitoba R7A 6A9
A symplectic Desarmenien matrix

For each postive integer n, and for each partition l of a
positive integer r, there is a Désarménien matrix which has rows
and columns indexed by the semistandard ltableaux with entries
from the set {1,¼,n}. This matrix plays a significant role in
the representation theory of the general linear group, GL(n,K).
Among other things, it provides a straightening algorithm for writing a
bideterminant associated to a given ltableau as a linear
combination of bideterminants associated to semistandard
ltableaux. There are also symplectic ltableaux which
prove useful in studying the representation theory of the symplectic
group. I will discuss a symplectic version of the Désarménien
matrix, which has rows and columns indexed by semistandard symplectic
ltableaux, and its role in the representation theory of the
symplectic group.
 HUGH THOMAS, Fields Institute, Toronto, Ontario M5J 3T1
Analogues of the map from S_{n} to triangulations of an
n+2gon in other types

There is a wellstudied surjective map from S_{n} to triangulations of
an n+2gon, through which the map taking a permutation to its descent
set factors. One can endow the permutations, triangulations, and
descent sets with partial order structures which make these all poset
maps. There is a Type B version of this (Type A) story, where one
replaces permutations by signed permutations of [n] and
triangulations by centrally symmetric triangulations of a 2n+2gon,
and one interprets descents in a natural way. Aspects of this story
have been worked out by Simion and Reiner, but the story has not been
put together completely; in particular, the correct order on the
centrally symmetric triangulationswhich makes them a selfdual
latticehas been missing until recently. I will discuss the stories
in Type A, Type B, and beyond. Time permitting, I may also touch on
connections to generalized noncrossing partitions and generalized
associahedra.
 TERRY VISENTIN, University of Winnipeg
Recent progress on the Qconjecture

In 1988, using purely algebraic methods, Jackson and I found an
interesting relationship between rooted quadrangulations in orientable
surfaces of genus g and all rooted maps in orientable surfaces. The
relationship is an important one because these two families of maps lie
at the heart of two distinct models for 2D quantum gravity. One feels
that there should be a natural combinatorial description of this
relationship; this is the essence of the Qconjecture. Although we
have not yet found a combinatorial construction which encompasses all
of the properties of the algebraic relationship, much progress has been
made. In this talk, we'll give a short history of the problem and a
discussion of the most recent developments.

