Book contents
- Frontmatter
- Preface
- Contents
- 1 Clique-width for hereditary graph classes
- 2 Analytic representations of large graphs
- 3 Topological connectedness and independent sets in graphs
- 4 Expanders – how to find them, and what to find in them
- 5 Supersingular isogeny graphs in cryptography
- 6 Delta-matroids for graph theorists
- 7 Extremal theory of vertex or edge ordered graphs
- 8 Some combinatorial and geometric constructions of spherical buildings
4 - Expanders – how to find them, and what to find in them
Published online by Cambridge University Press: 17 June 2019
- Frontmatter
- Preface
- Contents
- 1 Clique-width for hereditary graph classes
- 2 Analytic representations of large graphs
- 3 Topological connectedness and independent sets in graphs
- 4 Expanders – how to find them, and what to find in them
- 5 Supersingular isogeny graphs in cryptography
- 6 Delta-matroids for graph theorists
- 7 Extremal theory of vertex or edge ordered graphs
- 8 Some combinatorial and geometric constructions of spherical buildings
Summary
A graph $G=(V,E)$ is called an expander if every vertex subset U of size up to $|V|/2$ has an external neighborhood whose size is comparable to $|U|$. Expanders have been a subject of intensive research for more than three decades and have become one of the central notions of modern graph theory. We first discuss the above definition of an expander and its alternatives. Then we present examples of families of expanding graphs and state basic properties of expanders. Next, we introduce a way to argue that a given graph contains a large expanding subgraph. Finally weresearch properties of expanding graphs, such as existence of small separators, of cycles (including cycle lengths),and embedding of large minors.
- Type
- Chapter
- Information
- Surveys in Combinatorics 2019 , pp. 115 - 142Publisher: Cambridge University PressPrint publication year: 2019
- 12
- Cited by