The property of having a k ‐regular subgraph has a sharp threshold. Issue 4 (28th May 2012)

• Record Type: Journal Article
• Authors: Letzter, Shoham
• Is Part Of: Random structures & algorithms. Volume 42:Issue 4(2013)
• Page Start: 509
• Page End: 519
• Publication Date: 2012-05-28
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20434
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>In this paper it is proved that in the random graph model <italic>G</italic>(<italic>n</italic>, <italic>p</italic>), the property of containing a <italic>k</italic> ‐regular subgraph, has a sharp threshold for <italic>k</italic> ≥ 3. It is also shown how to use similar methods to prove, quite easily, the (known fact of) sharpness of having a non empty <italic>k</italic> ‐core for <italic>k</italic> ≥ 3. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 509–519, 2013</p> </abstract>