Testing for a Large Induced Expander: Sublinear Algorithms and Query Lower BoundsResearch Paper
A graph can contain a large well-connected subsystem even when the rest of the graph has no useful global structure. For a graph algorithm that only inspects a small portion of its input, recognizing the existence of such a subsystem differs from recognizing expansion of the whole graph. The subsystem might occupy forty percent of the vertices while the…