There will be a CIRCA seminar on November 30th, at 1pm on Theatre D of Maths. Peter Cameron and Richard Connor will speak.

Peter’s title is “When is the commuting graph split or threshold?”.

Abstract: The commuting graph of a group (or semigroup) G has vertex set G, two vertices joined if they commute. It was introduced by Brauer and Fowler in 1955, in their seminal work on involution centralisers in simple groups.
Split graphs and threshold graphs are two subgraph-closed graph families arising in operations research. A graph is split if the vertex set is the union of a complete graph and a null graph (with maybe some edges between); it is threshold if there are vertex weights and two vertices are joined if the sum of their weights exceeds a threshold.
I hope to present the complete proof of the classification of groups whose commuting graph is split or threshold: they are either abelian, or generalised dihedral of twice odd order.

Richard’s title is “Similarity search by graph navigation: some high-dimensional problems”

Abstract: Similarity search is a simple concept: to (efficiently) find, from within a (very) large collection, those objects which are most similar to a query object presented from the same domain. We (kind of) know that even approximate search becomes linear-time when the data is “high dimensional”, and linear time is no use to us! Unfortunately, “high” means something like over 20 Euclidean dimensions, and our main current interest is in searching embeddings, which are high-dimensional vectors arising from convolutional neural networks (such as GPT.) Language model embeddings have thousands of dimensions.

Some interesting recent systems have emerged which use novel graph navigation techniques. Simply, each element of the collection is represented as a graph node, and nodes are connected according to some relation. Search strategy is something like: start at a random node and navigate the graph, at each step moving closer to the query, which should thus be reached in a logarithmic number of steps. The current “state-of-the-art” is hnswlib (Hierarchical Navigable Small-World), which claims to work independently of dimensionality.

That, of course, isn’t true! In this talk, we examine the essential concepts presented by the authors, and some unfortunate properties of high-dimensional spaces which spoil the low-dimensional intuitions of graph navigation.

All welcome!