Tag - Expanders

Harald Helfgott: Expansion, Divisibility and Parity

5th April, 2024

We will discuss a graph that encodes the divisibility properties of integers by primes. We will prove that this graph has a strong local expander property almost everywhere. We then obtain several consequences in number theory, beyond the traditional parity barrier, by combining the main result with Matomaki-Radziwill. (This is joint work with M. Radziwill.) For instance: for λ the Liouville function (that is, the completely multiplicative function with λ(p) = −1 for every prime),

(1/log x) ∑n ≤ x λ(n) λ(n+1)/n=O(1/√(log log x)),

which is stronger than well-known results by Tao and Tao-Teravainen. We also manage to prove, for example, that λ(n+1) averages to 0 at almost all scales when n restricted to have a specific number of prime divisors Ω(n)=k, for any "popular" value of k (that is, k = log log N+O(√(log log N)) for n ≤ N).

Tselil Schramm: Higher-dimensional Expansion of Random Geometric Complexes

25th July, 2023

A graph is said to be a (1-dimensional) expander if the second eigenvalue of its adjacency matrix is bounded away from 1, or almost-equivalently, if it has no sparse vertex cuts. There are several natural ways to generalize the notion of expansion to hypergraphs/simplicial complexes, but one such way is 2-dimensional spectral expansion, in which the local expansion of vertex links/neighborhoods (remarkably) witnesses global expansion. While 1-dimensional expansion is known to be achieved by, e.g., random regular graphs, very few examples of sparse 2-dimensional expanders are known, and at present all are algebraic. It is an open question whether sparse 2-dimensional expanders are natural and "abundant" or "rare." In this talk, we'll give some evidence towards abundance: we show that the set of triangles in a random geometric graph on a high-dimensional sphere yields an expanding simplicial complex of arbitrarily small polynomial degree.

Thatchaphol Saranurak: Using Expanders for Fast Graph Algorithms

9th May, 2023

In the last few years, expanders have been used in fast graph algorithms in different models, including static, dynamic, and distributed algorithms. I will survey these applications of expanders, explain the expander-related tools behind this development, then give a tutorial on how to construct some of these tools, such as expander decomposition.

Theo McKenzie: Graph Vertex Expansion

8th May, 2023

In a vertex expanding graph, every small subset of vertices neighbors many different vertices. Random graphs are near-optimal vertex expanders; however, it has proven difficult to create families of deterministic near-optimal vertex expanders, as the connection between vertex and spectral expansion is limited. We discuss successful attempts to create unique neighbour expanders (a weak version of vertex expansion), as well as limitations in using common combinatorial methods to create stronger expanders.

Jeroen Schillewaert: Constructing highly regular expanders from hyperbolic Coxeter groups

17th November, 2022

Given a string Coxeter system (W,S), we construct highly regular quotients of the 1-skeleton of its universal polytope P, which form an infinite family of expander graphs when (W,S) is indefinite and P has finite vertex links. The regularity of the graphs in this family depends on the Coxeter diagram of (W,S). The expansion stems from superapproximation applied to (W,S). This construction is also extended to cover Wythoffian polytopes. As a direct application, we obtain several notable families of expander graphs with high levels of regularity, answering in particular a question posed by Chapman, Linial and Peled positively.

This talk is based on joint work with Marston Conder, Alexander Lubotzky and Francois Thilmany.

This video was produced by the Sydney Mathematical Research Institute, as part of their SMRI seminar series.

Harald Helfgott: Expansion, divisibility and parity

5th March, 2021

We will discuss a graph that encodes the divisibility properties of integers by primes. We show that this graph is shown to have a strong local expander property almost everywhere. We then obtain several consequences in number theory, beyond the traditional parity barrier. For instance: for λ the Liouville function (that is, the completely multiplicative function with λ(p) = -1 for every prime), (1/log x) ∑n ≤ x λ(n) λ(n+1)/n = O(1/√(log log x)), which is stronger than a well-known result by Tao. We also manage to prove, for example, that λ(n+1) averages to 0 at almost all scales when n restricted to have a specific number of prime divisors Ω(n)=k, for any "popular" value of k (that is, k = log log N + O(√(log log N)) for n ≤ N. We will give a quick overview of the combinatorial ideas behind the proof.

Federico Vigolo: Asymptotic expander graphs

17th July, 2020

A sequence of expanders is a family of finite graphs that are sparse yet highly connected. Such families of graphs are fundamental object that found a wealth of applications throughout mathematics and computer science. This talk is centred around an 'asymptotic' weakening of the notion of expansion. The original motivation for this asymptotic notion comes from the study of operator algebras associated with metric spaces. Further motivation comes from some recent works which established a connection between asymptotic expansion and strongly ergodic actions. I will give a non-technical introduction to this topic, highlighting the relations with usual expanders and group actions.

Nati Linial: What are High-Dimensional Expanders?

2nd February, 2017

Quite a few people are trying to answer the question in the title. Various interesting approaches are being proposed based on algebraic, geometric and topological notions. In this talk I will advocate a combinatorial approach that is based on sparsity and regularity and focuses on notions of low discrepancy. This approach makes it particularly desirable to investigate random high-dimensional combinatorial objects.