Associative spectra of graph algebras

The associative spectrum was introduced by Csákány and Waldhauser in 2000 and has appeared in the literature under different names. It is a way of quantifying the non-associativity of binary operations or the corresponding groupoids. The associative spectrum of a groupoid $G$ is an integer sequence, the $n$-th member of which equals the number of distinct term operations induced on $G$ by the bracketings of $n$ variables.

In this talk, we report our work on associative spectra of graph algebras. Graph algebras were introduced by Shallon in 1979 and provide a useful representation of directed graphs as algebras with a binary operation. We classify undirected graphs according to the associative spectra of their graph algebras; there are only three distinct possibilities: constant 1, powers of 2, and Catalan numbers. For arbitrary digraphs, the situation is considerably more complicated. We provide a necessary and sufficient condition for a graph algebra to satisfy a given bracketing identity, expressed in terms of several numerical structural parameters associated, on the one hand, with the graph and, on the other hand, with a pair of bracketings. Based on this, we establish bounds on the possible associative spectra of graph algebras; such a spectrum is either a constant sequence bounded above by 2 or it grows exponentially. This stands in stark contrast with associative spectra of arbitrary groupoids, for which other constant and subexponential spectra are also possible.

This is joint work with Tamás Waldhauser (University of Szeged).

Date and Venue

Start Date
Online Zoom meeting
End Date


Erkko Lehtonen

Speaker's Institution

Khalifa University, UAE



Semigroups, Automata and Languages