Phase transition of degeneracy in minor-closed families

Given an infinite family G of graphs and a monotone property P, an (upper) threshold for G and P is a “fastest growing” function p:N→[0,1] such that lim_n→∞⁡Pr⁡(G_n(p(n))∈P)=1 for any sequence (G_n)_n∈N over G with lim_n→∞⁡|V(G_n)|=∞, where G_n(p(n)) is the random subgraph of G_n such that each edge remains independently with probability p(n). In this paper we study the upper threshold for the family of H-minor free graphs and the property of being (r−1)-degenerate and apply it to study the thresholds for general minor-closed families and the properties for being r-choosable and r-colorable. Even a constant factor approximation for the upper threshold for all pairs (r,H) is expected to be challenging by its close connection to a major open question in extremal graph theory. We determine asymptotically the thresholds (up to a constant factor) for being (r−1)-degenerate (and r-choosable, respectively) for a large class of pairs (r,H), including all graphs H of minimum degree at least r and all graphs H with no vertex-cover of size at most r, and provide lower bounds for the rest of the pairs of (r,H).