The metric dimension of a graph is the least size of a subset of vertices {v₁,v₂,...,v_k} such that for any vertex w, the list of distances ( d(w,v₁),d(w,v₂),...,d(w,v_k) ) 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.

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 X₁ X₂ ¼X_k where X_i is a permutation of X₁ 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).

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.

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.

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.

With N. Bergeron, I have introduced a set of axioms which guarantee that the Grothendieck groups of a tower of algebras Å_{n ³ 0} A_n 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} A_n gives rise to graded dual Hopf algebras then we must have dimA_n = rⁿ n! where r = dimA₁. 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.

Consider a d-class cometric (or Q-polynomial) association scheme with vertex set X and primitive idempotents E₀,E₁,...,E_d forming a Q-polynomial ordering. For each vertex a, we introduce an indeterminate Z_a and map the polynomial ring C [Z₁,...,Z_v] (v=|X|) to the standard module C^X by first mapping Z_a to the column of E₁ 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.

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 E₆ and E₇ 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.

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.

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

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.

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.

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.