Premium
On the Probability that a Random Subgraph Contains a Circuit
Author(s) -
Nelson Peter
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22095
Subject(s) - combinatorics , mathematics , random graph , induced subgraph isomorphism problem , graph factorization , discrete mathematics , simple graph , random regular graph , enhanced data rates for gsm evolution , graph , simple (philosophy) , line graph , graph power , computer science , voltage graph , 1 planar graph , telecommunications , philosophy , epistemology
Let μ > 2 and ε > 0 . We show that, if G is a sufficiently large simple graph of average degree at least μ, and H is a random spanning subgraph of G formed by including each edge independently with probability p ≥ 1 μ − 1 + ε , then H contains a cycle with probability at least 1 − ε .
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom