Sublinear expanders and their applications
| Autor: | Letzter, Shoham |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | In this survey we aim to give a comprehensive overview of results using sublinear expanders. The term sublinear expanders refers to a variety of definitions of expanders, which typically are defined to be graphs $G$ such that every not-too-small and not-too-large set of vertices $U$ has neighbourhood of size at least $\alpha |U|$, where $\alpha$ is a function of $n$ and $|U|$. This is in contrast with linear expanders, where $\alpha$ is typically a constant. :We will briefly describe proof ideas of some of the results mentioned here, as well as related open problems. Comment: 39 pages, 15 figures. This survey will appear in `Surveys in Combinatorics 2024' (the proceedings of the 30th British Combinatorial Conference) |
| Databáze: | arXiv |
| Externí odkaz: |
|