Testing for a Large Induced Expander: Sublinear Algorithms and Query Lower Bounds

Testing expansion asks to distinguish graphs of large conductance from graphs that are far from having large conductance. We study a relaxation in which only part of the graph is required to expand: does an n-vertex graph of bounded degree contain an induced expander on a constant fraction of its vertices, when the rest of the graph, including the edges leaving the expander, is arbitrary? Let Pα,ϕ denote the property of containing an induced subgraph on at least $αn$ vertices with inner conductance at least $ϕ$. For every constant κ∈(0,1), we give a tester that accepts graphs in Pα,ϕ and rejects graphs outside Pκα,μϕ², where μ=Θα,κ(1/log n), using Oα,κ(√ n\,ϕ⁻²log n) queries. For fixed α∈(0,1], κ∈(0,1), and 0<ϕ≤9/20, we further show that distinguishing these two classes requires Ωα,κ,ϕ(n^1/2+cκ,ϕμ) queries for every sufficiently large n and every 0<μ≤1, where cκ,ϕ>0. The bound holds for adaptive algorithms, uniformly in $μ$. Hence, for testers with √ n\,polylog(n) queries, the logarithmic loss in conductance is necessary up to a loglog n factor. The same tester also permits distance-based rejection at a weaker conductance while retaining the original core size. Our tester compares the endpoint distributions of random walks from different vertices with each other, rather than with the uniform distribution. Its analysis uses the trace chain, which observes the walk only at its visits to the unknown expanding core. Our lower bound builds on the noisy-parity construction of [CKK+18], using vector-valued parity labels in F₂ʳ to create many hidden classes, each too small to contain a qualifying induced expander.