Phase transition of degeneracy in minor-closed families
Phase transition of degeneracy in minor-closed families
复制标题
DOI：
10.1016/j.aam.2023.102489
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Chun-Hung Liu;F. Wei
中科院分区：
文献类型：
--
作者：
Chun-Hung Liu;F. Wei
给定一个无限族的图和单调性P， G和P的上阈值是一个“增长最快”的函数P: N→[0,1]，使得对于任意序列（gn） N∈N / G, lim N→∞(| V (gn)|=∞,lim N→∞(P (N))∈P)= 1，其中gn （P (N)）是gn的随机子图，使得每条边都以P (N)的概率保持独立。本文研究了h次自由图族的上门限和（r−1）简并的性质，并将其应用于一般次闭图族的上门限和可选可色的性质。即使是对所有对（r， H）的上阈值的常因子近似，由于其与极值图论中的一个主要开放问题的密切联系，预计也将是具有挑战性的。我们渐近地确定了一大类图（r， H）的(r−1)-退化（和r-可选）的阈值（分别到一个常数因子），包括所有最小度至少为r的图H和所有没有顶点覆盖大小不超过r的图H，并提供了其余（r， H）对的下界。
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).