Phase Transition of Degeneracy in Minor-Closed Families

Abstract

Given an infinite family $\mathcal{G}$ of graphs and a monotone property $\mathcal{P}$, an (upper) threshold for $\mathcal{G}$ and $\mathcal{P}$ is a "fastest growing" function $p:\mathbb{N}\to [0,1]$ such that ${\lim }_{n\to \infty }\mathrm{Pr}(G_n(p(n))\in \mathcal{P})=1$ for any sequence $(G_n{)}_{n\in \mathbb{N}}$ over $\mathcal{G}$ with ${\lim }_{n\to \infty }|V(G_n)|=\infty$, 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 for the graph property of being $(r-1)$-degenerate, which is one fundamental graph property with many applications. Even a constant factor approximation for the upper threshold for all pairs $(r,H)$ is expected to be very difficult 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 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)$. The results generalize to arbitrary proper minor-closed families and the properties of being $r$-colorable, being $r$-choosable, or containing an $r$-regular subgraph, respectively.

References in corpus (4)

• Percolation on finite graphs and isoperimetric inequalities
• A lower bound on the average degree forcing a minor
• On the extremal function for graph minors
• Extremal functions for sparse minors

Cited by in corpus (1)

• Defective coloring is perfect for minors