The Kőnig graph process. Issue 4 (9th October 2020)

• Record Type: Journal Article
• Authors: Kamčev, Nina; Krivelevich, Michael; Morrison, Natasha; Sudakov, Benny
• Is Part Of: Random structures & algorithms. Volume 57:Issue 4(2020)
• Page Start: 1272
• Page End: 1302
• Publication Date: 2020-10-09
• Subjects: matching -- perfect matching -- random graph -- random process -- vertex cover; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20969
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : Say that a graph G has property 𝒦 if the size of its maximum matching is equal to the order of a minimal vertex cover. We study the following process. Set N : = n 2 and let e 1, e 2, … e N be a uniformly random ordering of the edges of K n, with n an even integer. Let G 0 be the empty graph on n vertices. For m ≥ 0, Gm + 1 is obtained from Gm by adding the edge e m + 1 exactly if Gm ∪ { e m + 1 } has property 𝒦 . We analyze the behavior of this process, focusing mainly on two questions: What can be said about the structure of GN and for which m will Gm contain a perfect matching?