Sublinear expanders and their applications
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910602268508160 |
|---|---|
| author | Letzter, Shoham |
| author_facet | Letzter, Shoham |
| contents | 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 $α|U|$, where $α$ is a function of $n$ and $|U|$. This is in contrast with linear expanders, where $α$ is typically a constant. :We will briefly describe proof ideas of some of the results mentioned here, as well as related open problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_10865 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sublinear expanders and their applications Letzter, Shoham Combinatorics 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 $α|U|$, where $α$ is a function of $n$ and $|U|$. This is in contrast with linear expanders, where $α$ is typically a constant. :We will briefly describe proof ideas of some of the results mentioned here, as well as related open problems. |
| title | Sublinear expanders and their applications |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2401.10865 |