Seminar

Zoom Link

Given a tree T and an abelian group G, a labelling of the vertices of T with distinct elements of G is called harmonious if the sum of the labels along each edge is also distinct. Harmonious labellings were introduced in 1980 by Graham and Sloane in connection with the study of additive bases. The main conjecture in the area, the Graham-Sloane conjecture, asserts that every tree with n vertices admit a harmonious labelling via the group Z/nZ. On the other hand, for general abelian groups, the situation is more complicated, as a well-known example of Maamoun and Meyniel from 1984 shows that a path on 2^k vertices does not admit a harmonious labelling via the group (F_2)^k. In this talk, we discuss recent work with A. Pokrovskiy that gives a full characterisation of when a bounded degree tree admits a harmonious labelling via a given abelian group. In particular, this confirms the Graham-Sloane conjecture for all bounded degree trees. The proof relies on a recent result of the author and A. Pokrovskiy on random subsquares of multiplication tables (the so-called random Hall-Paige conjecture) as well as an interesting connection with sorting networks, a classical object of study from computer science. In this talk, we will give a gentle introduction to this area. No prior background will be assumed. 

On the Graham-Sloane harmonious tree conjecture