Music, graphs, and hamiltonian cycles…

Today, I will comment a recent article which has been published in the Journal of Mathematics and Music:

• Chordal and timbral morphologies using Hamiltonian cycles“, Akhmedov, A., Winter, M., Journal of Mathematics and Music, 8(1), 2014, pp. 1-24 (link).

I find this article quite amazing, as it gives very general results to very concrete problems in music. I’m actually going to cover only a part of this article, and I encourage you to to read the rest if you can access it.

The authors consider three main problems, among which the following one: suppose we are given $n$ different instruments (i.e. $n$ different voices) and $k$ different notes. How to play these notes as chords ?
Well, it could be that one instrument would play all $k$ notes, while the others remain silent. Or, you could spread all the $k$ notes among the $n$ instruments. We can easily encode the information of which instrument is playing which note, by considering a $k$-tuple $(x_1, x_2, \ldots, x_k)$ where each $x_i \in \{1,\ldots,n\}$ specifies which instrument plays the pitch $i$.

Now, consider two successive $k$-tuples. Fix an integer $l$ such that $l \leq k$. This integer represents the number of pitches which are assigned the same instruments in both voicings.
For example, let’s take a set of three instruments ( $n=3$), with two different pitches C and F ( $k=2$), and let’s consider that only one pitch is assigned the same instrument between adjacent pairs of chords ( $l=1$). We could thus have the following progression: which would be represented by the succesive 2-tuples $(1,2)$, $(2,2)$, $(2,3)$, and $(1,3)$.

The question is now: given $n$, $k$, and $l$, is it possible to explore all possible $k$-tuples with the above mentionned constraints ? To solve this problem, Akhmedow and Winter resort to graph theory and the notions of Hamiltonian paths and Hamiltonian cycles.

Recall that, given a graph $G$, a hamiltonian path is a path in $G$ which visits every vertex of $G$ exactly once. In addition, a hamiltonian cycle is a hamiltonian path which returns to the original vertex. You may recall that we have seen examples of hamiltonian cycles when we were speaking about the Tonnetz in this post. However, the Tonnetz is constructed using group theory (more precisely, based on the group actions of the dihedral group $D_{24}$ on the set of major and minor triads). Here, we don’t need group theory, just graph theory. This is why I like this article: quite simple, with very nice results.

So, Akhmedov and Winter first builds the timbral graph (after all, it’s all about exploring the same chord with timbral variations due to the change of instrumentation) $T_{n,k,l}$: its vertices are the $k$-tuples as defined above, and two tuples are connected by an edge iff $x_i=x'_i$ for exactly $l$ values of $i \in \{1,\ldots,k\}$.

For example, in my example above, with $n=3$, $k=2$, and $l=1$, here’s what the graph $T_{3,2,1}$ looks like: And now for the big theorem of Akhmedov and Winter :

Theorem: the graph $T_{n,k,l}$ is hamiltonian (i.e. it has at least one hamiltonian cycle) for all $n \geq 3$, and $k \geq l+1$.

This means that, in most cases, you can actually explore all the combinations of chords ! For example, here’s in an hamiltonian cycle in $T_{3,2,1}$: Akhmedov and Winter consider plenty of other graphs as well. For example

• the graph of “chords of size k from n possible pitches where l pitches are assigned the same instrument in both chords of any adjacent pair“,
• the graphs of “chords with 3 pitches from a set of n possible pitches where one pitch stays the same and the others move by a semitone in contrary motion between adjacent chords“,

for which they give theorems about the hamiltonicity of such graphs.

This article is truly a very nice example of a paper about mathematics and music. The results could very well be used to compose (although actually finding a hamiltonian cycle in a given graph is known to be a very difficult problem, more exactly a NP-complete problem). If you’re familiar with the work of Tom Johnson, I suspect this is the kind of music you could get. Or maybe something different…