Computer Science and Discrete Mathematics (CSDM)

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...

Graph Vertex Expansion

Theo McKenzie

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...

We prove the existence of subspace designs with any given parameters, provided that the dimension of the underlying space is sufficiently large in terms of the other parameters of the design and satisfies the obvious necessary divisibility...