Eitan Bachmat

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₀(ε,δ) 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.