## 28 Feb 2003:

Is Edge-Expansion Robust to Random Faults?

Amitabh Bagchi

Consider the situation where nodes of a graph *G* become faulty
independently with probability *p* giving the graph
*G*_{p}. The "critical
probability" *p*^{*} for a graph is defined as that value
of *p* for which
there is no linear sized component remaining in the graph
*G*_{p*} with high
probability. We call a graph parameter ρ(*G*) "robust" if
ρ(*G*_{p*-o(p*)}) = θ(ρ(*G*)) i.e. if the value of ρ is preserved upto a
constant factor till the point where the graph itself falls apart.

We consider the robustness of a graph parameter important to the study
of the routing properties of a network: the edge expansion. We prove a
general theorem from which the robustness of edge expansion on a mesh
can be deduced.