Directed analogues of expander graphs and random compact subsets of $\mathbb{R}^n$

Abstract: I will talk about two separate projects. The first one is a joint work with Endre Csoka (published in "Combinatorics, Probability and Computing"), where we construct "extender" graphs - sparse directed graphs with the property that it is impossible to remove a small amount of edges and obtain a graph which does not have long directed paths (long is $|V|^\delta$, where $\delta>0$ is an absolute constant). Extenders are a directed analogue of expander graphs, since the latter ones are characterised by the property that it is impossible to remove a small amount of edges and obtain graphs which have small connected components. I'll discuss some conjectures in circuit complexity which motivated us to introduce extenders.

The second project is a joint work with Tomasz Ciesla (preprint available on arxiv). We construct compacts subsets of $\mathbb{R}^2$ which are not "domains of expansion", which answers a question about spectral properties of group actions, raised by Adrian Ioana.

Apart from the general theme of "expansion", both projects are related by the method which is used to construct suitable examples - in both cases the construction is probablistic, and the required properties follow from entropy estimates.

combinatorics

Audience: researchers in the topic

Warwick Combinatorics Seminar

Series comments: This is the online combinatorics seminar at Warwick.