---

Discrete Mathematics / Mathématiques discrètes
(Org: Vaclav Linek)

---

JASON BROWN, Dalhousie University
Well-covered 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 well-covered 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 well-covered 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 well-covered weightings for structural theorems on a class of well-covered 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}ⁿ 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, Butson-Hadamard matrices, unit Hadamard and (*unit weighing) matrices, Inverse orthogonal (and *I0-weighing 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/non-existence of sequences avoiding patterns. Classical examples include non-repetitive 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/non-existence of sequences avoiding patterns. Classical examples include non-repetitive words, words avoiding abelian powers, and Dejean's conjecture concerning words avoiding fractional powers. In conjunction with the existence questions are extremal problems:

1. What is the least alphabet size for avoiding (abelian) x^k
   
   
2. What is the least k such that x^k is S-avoidable?
   
   
3. What is the least L such that x^k is S-avoidable 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
Digraph-based 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 k-extended Langford sequences of large defect, hooked and un-hooked

A classical Skolem sequence is an integer sequence d₁,¼,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+m-1]. A k-extended Langford sequence of defect d and length m is an integer sequence s₁,¼,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 i-1 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 k-extended 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² (the affine plane over an arbitrary field K) to be adjacent if (x¢-x)²+(y¢-y)²=1. Determination of the chromatic number c(K²) 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 number-theoretical 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 l-tableaux 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 l-tableau as a linear combination of bideterminants associated to semistandard l-tableaux. There are also symplectic l-tableaux 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 l-tableaux, 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+2-gon in other types

There is a well-studied surjective map from S_n to triangulations of an n+2-gon, 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+2-gon, 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 triangulations-which makes them a self-dual lattice-has 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 non-crossing partitions and generalized associahedra.

TERRY VISENTIN, University of Winnipeg
Recent progress on the Q-conjecture

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 Q-conjecture. 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.