ICS Theory Group

ICS 269, Winter 2002: Theory Seminar

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 Gp. 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 Gp* with high probability. We call a graph parameter ρ(G) "robust" if ρ(Gp*-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.