Tag - Cayley graphs

Carla Groenland: Cyclically covering subspaces in š”½2n

26th October, 2020

A subspace of š”½2n is called cyclically covering if every vector in š”½2n has a cyclic shift which is inside the subspace. Let h2(n) denote the largest possible codimension of a cyclically covering subspace of š”½2n. We show that h2(p) = 2 for every prime p such that 2 is a primitive root modulo p, which, assuming Artinā€™s conjecture, answers a question of Peter Cameron from 1991. In this talk, I will try to explain how we reduce the problem to a problem on finding odd subgraphs in which each vertex has odd outdegree in directed Cayley graphs, how additive combinatorics comes to the rescue and which open problems I would like to see solved. This is joint work with James Aaronson and Tom Johnston.

Peter Keevash: Isoperimetric Stability

14th September, 2020

Understanding approximate minimisers for isoperimetric problems is of fundamental importance in Combinatorics, Analysis and Geometry. We will survey some recent progress on these problems in three settings: the Extremal Combinatorics setting of the discrete cube (joint with Eoin Long), the Additive Combinatorics setting of Cayley digraphs on lattices (joint with Ben Barber, Joshua Erde and Alexander Roberts) and the Discrete Analysis setting of Boolean functions with small influence, with applications to sharp thresholds and Extremal Combinatorics via the Junta Method (joint with Noam Lifshitz, Eoin Long and Dor Minzer).

Ana Khukhro: A new characterization of virtually free groups

4th September, 2020

A finite graph that can be obtained from a given graph by contracting edges and removing vertices and edges is said to be a minor of this graph. Minors have played an important role in graph theory, ever since the well-known result of Kuratowski that characterized planar graphs as those that do not admit the complete graph on five vertices nor the complete bipartite graph on (3,3) vertices as minors. In this talk, we will explore how this concept interacts with some notions from geometric group theory, and describe a new characterisation of virtually free groups in terms of minors of their Cayley graphs.

Tatiana Smirnova-Nagnibeda: Spectra of Laplacians on Cayley and Schreier graphs

16th April, 2020

We are interested in Laplacians on graphs associated with finitely generated groups: Cayley graphs and, more generally, Schreier graphs corresponding to some natural group actions. The spectrum of such an operator is a compact subset of the closed interval [-1,1], but not much more can be said about it in general. We will discuss various techniques that allow to construct examples with different types of spectra - connected, union of two intervals, totally disconnected - and with various types of spectral measure. The problem of spectral rigidity will also be addressed.

Harald Helfgott: The Diameter of the Symmetric Group: Ideas and Tools

3rd February, 2017

Given a finite group G and a set A of generators, the diameter diam(Ī“(G,A)) of the Cayley graph Ī“(G,A) is the smallest š“ such that every element of G can be expressed as a word of length at most š“ in A ā‹ƒ A-1. We are concerned with bounding diam(G):= maxA diam(Ī“(G,A)). It has long been conjectured that the diameter of the symmetric group of degree n is polynomially bounded in n. In 2011, Helfgott andĀ Seress gave a quasipolynomial bound exp((log n)4+ε). We will discuss a recent, much simplified version of the proof.

Doron Puder: Word-Measures on Unitary Groups

2nd February, 2017

One approach to studying properties of random walks on groupsĀ with random generators is to study word-measures on these groups. ThisĀ approach was proven useful for the study of symmetric groups and randomĀ regular graphs. In the current work we focus on the unitary groups U(n).Ā For example, if w is a word in F2 = <x,y>, sample at random two elementsĀ from U(n), A for x and B for y, and evaluate w(A,B). The measure of thisĀ random element is called the w measure on U(n). We study the expected traceĀ (and other invariants) of a random unitary matrix sampled from U(n)Ā according to the w-measure, and find surprising algebraic properties of wĀ that determine these quantities.

Alireza Salehi Golsefidy: Super-approximation

31st January, 2017

I will report on the latest results on super-approximation. Roughly super-approximation gives us the right condition in order to get a family of expanders out of the Cayley graphs of the congruence quotients of a group generated by finitely many rational matrices. I will mention a sum-product phenomenon in number fields which is used in the proof of super-approximation. Some of the applications of super-approximation will be mentioned at the end.