tag:blogger.com,1999:blog-8890204.post4538962142678962503..comments2024-09-18T05:51:03.956-04:00Comments on My Biased Coin: Paper updatesMichael Mitzenmacherhttp://www.blogger.com/profile/06738274256402616703noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-8890204.post-56701008429757472682010-01-31T11:40:13.183-05:002010-01-31T11:40:13.183-05:00I think the compelling thing about these processes...I think the compelling thing about these processes is that they appear to have a discontinuous phase transition which has yet to be well understood. (The same appears true for the standard Achlioptas process, but these variations seems potentially "easier", so there's hope we may understand these local variations first.) The preprint has more details.Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-64273257936437705442010-01-30T18:21:22.350-05:002010-01-30T18:21:22.350-05:00I discussed these kinds of Achlioptas process vari...I discussed these kinds of Achlioptas process variations with Po-Shen Loh back in 2008. <br /><br />According to my notes, the most natural variation is to pick a k-star u.a.r. and get to keep an edge. (I wrote, "The advantage of this model is that it is 'clear' what the optimal strategy for avoiding the growth of a giant component ... should be: add the edge that connects to the smallest component.") <br /><br />The next variation is to pick a random triangle, and get to keep two of the three edges. <br /><br />The third variant in my notes, which seems to specialize the first, is to pick choose one of two edges that share one vertex, i.e., a uniformly random path P_2. This seems to be what you consider. <br /><br />Finally, a last variation is to pick some subset of the edges of a random graph H. (And there is some sort of quantum version, too.) <br /><br />As far as I could tell, the arguments didn't look sufficiently different from [Krivelevich, Loh, Sudakov 07] for any of these alternatives to be compelling, but I just thought I would mention them.Anonymousnoreply@blogger.com