Expanders are an interesting class of graphs characterized by the “linear isoperimetric inequality”. The graphs themselves are sparse (each vertex has only a constant number of neighbors, so the total number of edges is linear in the number of vertices), yet they are very strongly connected – each set has a large boundary (the number of edges going out from that set), so it’s very difficult to disconnect a graph by removing edges. Alternatively, there is an algebraic characterization of expanders using the so-called “spectral gap”, related to the eigenvalues of the graph’s adjacency matrix.
It’s a common theme in metric geometry to embed graphs into “nicer” metric spaces, for example the Euclidean space R^n or other normed spaces (Hilbert spaces, Banach spaces). For a given graph G, one usually asks how distorted its metric becomes after embedding into e.g. a Hilbert space. Expanders are, in some sense, graphs whose geometry is “as non-Euclidean as possible” and thus are the most difficult graphs to embed into Euclidean spaces – every such embedding must incur distortion of order at least log n (we know that log n is worst possible from Bourgain’s embedding theorem).
The focus on embedding into Banach spaces seems to be our cultural bias – since we live in a Euclidean 3-dimensional space, we view spaces of such geometry as “natural” and other possible metrics are considered “distorted” after embedding. We can easily imagine that if our world was an expander, the Euclidean space would seem “distorted”, “unnatural” or simpy “weird” and we would be embedding things into expanders, not vice versa. In fact, there are still native tribes today that live inside expanders. A new BBC documentary “Mind Expansion” makes a closer investigation into the lives and mindsets of such peoples.
“Anthropologically speaking”, explains Michael Gormoff, a field anthropologist who has studied “expander tribes” for over 25 years, “we cannot view our Euclidean-centric worldview as the primary one. The natives living inside expanders simply have a conceptual framework incommensurate with our own. To me, trying to insist that our metric culture is <<better>> reeks of imperialism – the same attitude that the Spanish had when they conquered the New World in 16th century, and we know what the results were”.
Gormoff gives an example where “expander-centric culture” is less violent than ours. Inside expanders, every set has a large ratio of its boundary to its size, which is unlike the Euclidean plane, where a square of size n has area n^2 but perimeter only 4n. Inside expanders, it’s very difficult to build a secure military camp or a fortress – since it has large perimeter, it will be exposed to attack from all sides. Expander tribes have eschewed defensive warfare in favor of a very aggresive and offensive approach. If one remembers the horror of trench-based positional warfare during World War I, this seems a much less cruel alternative.
“I can’t even imagine how life in a Euclidean space can look like, it must be a living hell”, says Grigere Margelels, the leader of one of expander tribes. “Random walks in your metric are sluggish, they mix extremely slowly. I could never understood how you can <<get lost in the mountains>>. If something like that happened here, you would just walk around randomly and would be guaranteed to find a way out very quickly. Euclidean world is a nightmare to us, I would never consider emigrating.”
Sadly, the world becomes more and more Euclidianized, and expander tribes are slowly forced to assimilate. Just in last 5 years, over a dozen of big expanders (includes Margulis expander, Philips-Lubotzky-Sarnak expander, zig-zag product expander) have been coarsely embedded into a Hilbert space. This threatens not only the culture of expander tribes, but also day-to-day needs of Western science, in particular theoretical computer science which makes extensive use of expanders. “The spectral gap is vanishing”, warns Gormoff. “We must stop this process and preserve the cultural heritage of our planet. Otherwise, we might one day wake up, only to find that expansion has disappeared – and we have lost a valuable metric perspective.”