Ekspander – graf o niewielkiej liczbie krawędzi, w którym każdy podzbiór wierzchołków ma dużo sąsiadów. Istnieje kilka nierównoważnych formalizacji tej własności, definiujących różne klasy ekspanderów. Ekspandery pozwoliły na uzyskanie kilku istotnych wyników z różnych dziedzin informatyki: dowodów w teorii złożoności, projektowaniu sieci sortujących, kodów korekcji błędów, ekstraktorów losowości i odpornych na błędy schematów komunikacji w sieciach komputerowych.
Definicje W zależności od kontekstu, używa się różnych sposobów mierzenia ekspansji grafu.
Ekspansja wierzchołkowa – ekspansja wierzchołkowa grafu to współczynnik
gdzie oznacza zbiór wszystkich sąsiadów zbioru (wierzchołków połączonych z tym zbiorem krawędzią). W niektórych zastosowaniach używa się pojęcia ekspansji jednokrawędziowej, gdzie bierze się pod uwagę tylko sąsiadów połączonych dokładnie jedną krawędzią z
Ekspansja krawędziowa Współczynnik ekspansji krawędziowej grafu definiuje się jako:
gdzie oznacza zbiór krawędzi które łączą wierzchołek z z wierzchołkiem spoza