Regular graphs whose subgraphs tend to be acyclic

Noga Alon, Eitan Bachmat

Research output: Contribution to journalArticle

2 Scopus citations

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 > n0(ε,δ) 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 languageEnglish (US)
Pages (from-to)324-337
Number of pages14
JournalRandom Structures and Algorithms
Volume29
Issue number3
DOIs
StatePublished - Oct 1 2006
Externally publishedYes

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