Réunion d'été 2009 de la SMC et de la SCHPM
Université Memorial de Terre-Neuve, St. John's (Terre Neuve), 6 - 8 juin, 2009

Combinatoire algébrique
Org: Steve Kirkland et Karen Meagher (Regina)

ROBERT BAILEY, Carleton University, Ottawa
Metric dimension of distance-regular graphs

The metric dimension of a graph is the least size of a subset of vertices {v1,v2,...,vk} such that for any vertex w, the list of distances ( d(w,v1),d(w,v2),...,d(w,vk) ) uniquely identifies w. Introduced in the 1970s, this parameter has seen a flurry of recent interest from a variety of authors.

In this talk, we consider distance-regular graphs (and in particular, the special cases of distance-transitive and strongly regular graphs). By digging into the literature, we find some interesting results from other contexts from the early 1980s and rephrase them in terms of metric dimension. We also present some new results for Johnson graphs.

If time permits, we will also consider links between metric dimension of graphs and the base size of permutation groups.

AMY GLEN, The Mathematics Institute, Reykjavík University, Kringlan 1, IS-103, Iceland
Abelian repetitions and crucial words

In 1961, Erdös asked whether or not there exist words of arbitrary length over a fixed finite alphabet that avoid patterns of the form XX¢ where X¢ is a permutation of X (called abelian squares). This problem has since been solved in the affirmative in a series of papers from 1968 to 1992. Much less is known in the case of abelian k-th powers, i.e., words of the form X1 X2 ¼Xk where Xi is a permutation of X1 for 2 £ i £ k.

In this talk, I will discuss crucial words for abelian k-th powers, i.e., finite words that avoid abelian k-th powers, but which cannot be extended to the right by any letter of their own alphabets without creating an abelian k-th power. More specifically, I will consider the problem of determining the minimal length of a crucial word avoiding abelian k-th powers. This problem has already been solved for abelian squares by Evdokimov and Kitaev (2004). I will present a solution for abelian cubes (the case k = 3) and state a conjectured solution for the case of k ³ 4.

This is joint work with Bjarni V. Halldórsson and Sergey Kitaev (Reykjavík University).

CHRIS GODSIL, University of Waterloo, Waterloo, ON, N2L 3G1
Periodic Graphs

In some parts of quantum physics, a graph X with adjacency matrix A is periodic if there is a non-zero real number t such that exp( i A t) is diagonal. Clearly a graph is periodic if all eigenvalues of A are integers, but this condition is only sufficient. I will present some recent work on this problem, and on the related subject of perfect state transfer.

JOHN IRVING, Saint Mary's University, Halifax, NS
Another Look at Factorizations of Full Cycles

We will look at a generalization of an interesting symmetric function identity observed recently by Vassilieva and Morales. The identity serves as an implicit formula for certain connection coefficients of the symmetric group, and we use it to give a short algebraic derivation of an enumerative formula (originally due to Goulden and Jackson) for "top" factorizations of a full cycle into an ordered product of permutations of known cycle types.

MAHDAD KHATIRINEJAD, Helsinki University of Technology, Espoo, Finland
Optimal configuration of points in quaternionic projective spaces

A set of points in a quaternionic projective space is an "optimal configuration" if it minimizes a certain potential function depending on the pairwise distances between points. Equiangular lines and mutually unbiased bases (MUBs) are important examples of such optimal configurations. We formulate a common generalization of several results in real and complex spaces that also hold in the quaternionic space. We also provide intriguing examples of such optimal configurations.

HUILAN LI, Drexel University, Philadelphia, PA, USA
Combinatorial Hopf algebras and Towers of Algebras-dimension, quantization, and functoriality

With N. Bergeron, I have introduced a set of axioms which guarantee that the Grothendieck groups of a tower of algebras Ån ³ 0 An can be endowed with the structure of graded dual Hopf algebras. Hivert and Nzeutzhap, and independently Lam and Shimozono, constructed dual graded graphs from primitive elements in Hopf algebras. With N. Bergeron and T. Lam, I apply the composition of these constructions to towers of algebras. We show that if a tower Ån ³ 0 An gives rise to graded dual Hopf algebras then we must have dimAn = rn n! where r = dimA1. This shows that combinatorial Hopf algebras obtained by this procedure fall into a very rigid framework and can potentially be classified. In the case r=1 we give a conjectural classification. We then investigate a quantum version of the main theorem. We conclude with some open problems and a categorification of the construction.

BILL MARTIN, Worcester Polytechnic Institute, 100 Institute Road, Worcester, MA 01609, USA
The ideal of a cometric association scheme

Consider a d-class cometric (or Q-polynomial) association scheme with vertex set X and primitive idempotents E0,E1,...,Ed forming a Q-polynomial ordering. For each vertex a, we introduce an indeterminate Za and map the polynomial ring C [Z1,...,Zv] (v=|X|) to the standard module CX by first mapping Za to the column of E1 indexed by a. We extend this by ordinary addition and entrywise multiplication of vectors. We consider the kernel of this map and conjecture that it is always generated by low degree polynomials.


KEVIN PURBHOO, University of Waterloo, Waterloo, ON, N2L 3G1
Visualizing type-E root systems

Root systems are highly symmetrical finite collections of vectors in Euclidean space that encode the structure of a complex semisimple Lie algebra. Two important relations on a root system are the partial ordering and the orthogonality relation, and it can be very useful to be able to calculate easily and quickly with these. For exceptional root systems, a computer can easily calculate these relations, but it is not so obvious how a human can get a useful intuitive grasp of both simultaneously. However, in the case of the E6 and E7 root systems, a remarkable numerical accident occurs, which allows us to map the root system to a vector space over a finite field and maintain the important structure. This leads to a useful way to visualize type-E root systems.

ROBERT RAUSSENDORF, University of British Columbia, Department of Physics and Astronomy, 6224 Agricultural Road, Vancouver, BC, V6T 1Z4
Graph Theory and the hardness of classical simulation of quantum computation

Using the laws of quantum mechanics for computation leads to exponential savings in computational cost and run-time. The best known example is Shor's algorithm for factoring numbers, which breaks the RSA crypto system. But which quantum mechanical property causes this speed-up? We approach this question by investigating circumstances under which the speedup vanishes, namely when a quantum computation becomes efficiently simulatable on a classical computer.

To date, three techniques for the efficient simulation of special classes of quantum computations are known:

    (1) the Stabilizer formalism,
    (2) the fermionic/matchgate method, and the tensor contraction method.
It turns out that, through the framework of measurement-based quantum computation (MQC), all of them have a connection with graph theory. I briefly review these methods and then show that measurement-based quantum computation on a graph state |G > can be simulated by the matchgate method if and only if G is a circle graph.

Joint work with Jim Geelen (UW), Chris Godsil (UM) and Maarten van den Nest (MPI for Quantum Optics, Garching, Germany).

AIDAN ROY, University of Calgary, 2500 University Drive NW, Calgary, AB, T2N 1N4
Minimal Euclidean representations of graphs

A simple graph G is representable in a real vector space V if there is an embedding of the vertex set in V such that the Euclidean distance between two vertices u and v depends only on whether or not u and v are adjacent. The Euclidean representation number of G is the smallest dimension in which G is representable. Representations of graphs were introduced by Pouzet in 1977 as a means of showing that certain graph invariants of Tutte are reconstructible.

In this talk, we use Euclidean distance matrices to give an exact formula for the Euclidean representation number of any graph in terms of its spectrum and main eigenvalues.

ALYSSA SANKEY, University of New Brunswick, Fredericton NB
Weighted strongly regular graphs associated with S4(q)

We construct a family of weighted strongly regular graphs using the rank 3 action of the projective symplectic group on the totally isotropic lines of the symplectic geometry. From the weighted srg's we obtain line systems with two intersection angles, some of which realise known bounds on the number of such lines. There are also "type-II" matrices associated with these weighted srg's, thus they illustrate nicely the connections between weighted srg's, line systems with two angles, and type-II matrices.

SIMONE SEVERINI, University of Waterloo, Waterloo, Canada
Combinatorics of unitary matrices

The combinatorial structure of orthogonal matrices is a topic of study that remained dormant for many years after the first independent stubs by Fiedler, Brualdi, et al., from the mathematics community; by Lande and Louck, from the physics community. This was the area that I chose for my Ph.D. research. I will survey what we have done so far, why we should be interested in the topic and what we should do next.

MARTHA YIP, University of Wisconsin-Madison
Alcove walks and Macdonald polynomials

Macdonald polynomials are polynomials with two parameters q and t, associated to root systems. The type A symmetric Macdonald polynomials specialize to the Hall-Littlewood polynomials at q=0, and specialize to the Schur polynomials at q=t.

We give a Littlewood-Richardson rule for symmetric Macdonald polynomials. The coefficients are described combinatorially, using paths with folds.


l'Université Memorial de Terre-Neuve    AARMS: Atlantic Association for Research in the Mathematical Sciences    Centre de recherches mathématiques Fields Institute MITACS Pacific Institute for the Mathematical Sciences Réseau canadien de recherche sur le langage et l'alphabétisation

© Société mathématique du Canada :