### Abstract

Motivated by a problem that arises in the study of mirrored storage systems, we describe, for any fixed ε, δ > 0, and any integer d ≥ 2, explicit or randomized constructions of d-regular graphs on n > n_{0}(ε,δ) vertices in which a random subgraph obtained by retaining each edge, randomly and independently, with probability ρ = 1-ε/d-1, is acyclic with probability at least 1 - δ. On the other hand we show that for any d-regular graph G on n > n1(ε, δ) vertices, a random subgraph of G obtained by retaining each edge, randomly and independently, with probability ρ = 1+ε/d-1, does contain a cycle with probability at least 1 - δ. The proofs combine probabilistic and combinatorial arguments, with number theoretic techniques.

Original language | English (US) |
---|---|

Pages (from-to) | 324-337 |

Number of pages | 14 |

Journal | Random Structures and Algorithms |

Volume | 29 |

Issue number | 3 |

DOIs | |

State | Published - Oct 1 2006 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Regular graphs whose subgraphs tend to be acyclic'. Together they form a unique fingerprint.

## Cite this

*Random Structures and Algorithms*,

*29*(3), 324-337. https://doi.org/10.1002/rsa.20107