2015/07/15 by Antal A. Járai, Járai, Antal A.
Mathematics · #60K99 (Primary) #90C40 (Secondary) #91A60 #FOS: Mathematics #Optimization and Control (math.OC) #Probability (math.PR) #math.OC #math.PR #msc:60K99 #msc:90C40 #msc:91A60
paper · pdf · doi:10.48550/arxiv.1507.04169
28 pages, 2 eps figures. Some mistakes have been corrected, and the introduction has been re-written. Minor corrections throughout
arxiv created 2016/09/20 · arxiv updated 2016/09/21
We study the following game on a finite graph G = (V, E). At the start, each edge is assigned an integer ne ≥ 0, n = ∑e ∈ E ne. In round t, 1 ≤ t ≤ n, a uniformly random vertex v ∈ V is chosen and one of the edges f incident with v is selected by the player. The value assigned to f is then decreased by 1. The player wins, if the configuration (0, …, 0) is reached; in other words, the edge values never go negative. Our main result is that there is a phase transition: as n → ∞, the probability that the player wins approaches a constant cG > 0 when (ne/n : e ∈ E) converges to a point in the interior of a certain convex set RG, and goes to 0 exponentially when (ne/n : e ∈ E) is bounded away from RG. We also obtain upper bounds in the near-critical region, that is when (ne/n : e ∈ E) lies close to ∂ RG. We supply quantitative error bounds in our arguments.