We say that a graph G=(V,E) on n vertices is a @b-expander for some constant @b>0 if every U@?V of cardinality |U|@?n2 satisfies |N"G(U)|>=@b|U| where N"G(U) denotes the neighborhood of U. In this work we explore the process of deleting vertices of a @b-expander independently at random with probability n^-^@a for some constant @a>0, and study the properties of the resulting graph. Our main result states that as n tends to infinity, the deletion process performed on a @b-expander graph of bounded degree will result with high probability in a graph composed of a giant component containing n-o(n) vertices that is in itself an expander graph, and constant size components. We proceed by applying the main result to expander graphs with a positive spectral gap. In the particular case of (n,d,@l)-graphs, that are such expanders, we compute the values of @a, under additional constraints on the graph, for which with high probability the resulting graph will stay connected, or will be composed of a giant component and isolated vertices. As a graph sampled from the uniform probability space of d-regular graphs with high probability is an expander and meets the additional constraints, this result strengthens a recent result due to Greenhill, Holt and Wormald about vertex percolation on random d-regular graphs. We conclude by showing that performing the above described deletion process on graphs that expand sub-linear sets by an unbounded expansion ratio, with high probability results in a connected expander graph.
The process of random deletion of vertices of a graph received rather limited attention, mainly in the context of faulty storage (see e.g. @cite_0 ), communication networks, and distributed computing. For instance, the main motivation of @cite_12 is the SWAN peer-to-peer @cite_7 network whose topology possess some properties of @math -regular graphs, and may have faulty nodes. Other works are mainly interested in connectivity and routing in the resulting graph after performing (possibly adversarial) vertex deletions on some prescribed graph topologies.
@cite_0 @cite_7 @cite_12
2048114999 2477953794 2058466367
In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may incur arbitrary failures, including alterations to data stored in them. Using an error correcting code (ECC), e.g., a Reed?Solomon code, one can take n pieces of a document, replace each piece with another piece of size larger by a factor of nn?2t+1 such that it is possible to recover the original set even when up to t of the larger pieces are altered. For t close to n 2 the space blowup factor of this scheme is close to n, and the overhead of an ECC such as the Reed?Solomon code degenerates to that of a trivial replication code. We show a technique to reduce this large space overhead for high values of t. Our scheme blows up each piece by a factor slightly larger than two using an erasure code which makes it possible to recover the original set using n 2?O(n d) of the pieces, where d?80 is a fixed constant. Then we attach to each piece O(d log n log d) additional bits to make it possible to identify a large enough set of unmodified pieces, with negligible error probability, assuming that at least half the pieces are unmodified and with low complexity. For values of t close to n 2 we achieve a large asymptotic space reduction over the best possible space blowup of any ECC in deterministic setting. Our approach makes use of a d-regular expander graph to compute the bits required for the identification of n 2?O(n d) good pieces. We investigate the following vertex percolation process. Starting with a random regular graph of constant degree, delete each vertex independently with probability p, where p=n^-^@a and @[email protected](n) is bounded away from 0. We show that a.a.s. the resulting graph has a connected component of size n-o(n) which is an expander, and all other components are trees of bounded size. Sharper results are obtained with extra conditions on @a. These results have an application to the cost of repairing a certain peer-to-peer network after random failures of nodes.