当前位置: 首页 > 科研学术 > 科研成果 > 正文

大数据理论研究中心——(刘鸿、王光辉、杨东雷)稀疏图中的immersion嵌入问题

【 发布日期:2022-10-14 】

给定图G和H, 我们称G包含H-immersion是指存在一个单射f : V (H) → V (G) 使得对于H中的任意一条边uv,G中都包含一条路P(uv)连接f(u)和f(v),并且所有这样的路都是边不交的。这一概念最早由Nash-Williams于1965年提出,是图子式(minor)和拓扑子式(Topological minor or Subdivision)的一类推广且在近些年围绕immersion关系的极值问题受到广泛关注。我们知道一个图的点色数是最小的正整数k使得该图的所有顶点可以被划分为k个独立集。类比于著名的Hadwiger猜想:任意一个图都包含点色数大小的完全图作为minor,Lescure和Meyniel,Abu-Khzam和Langston,分别独立地提出了如下猜想:任意一个图都包含点色数大小的完全图作为immersion。关于该猜想目前最好的界是由Gauthier、Le和Wollan取得:任意点色数为3.54k+4的图都包含k大小的完全图作为immersion。

刘鸿(韩国IBS)、王光辉(山东大学)和杨东雷(山东大学)考虑平均度条件下的极值问题,证明了:对于任给的常数c > 0和整数s, t ≥ 2,存在常数d0使得任意一个不含Ks,t作为子图,且平均度至少为d0的图G中都包含(1-c)d(G)大小的完全图作为immersion,其中d(G)是图G的平均度。作为推论,上述Lescure和Meyniel等人的猜想对所有不含给定二部图的图类是渐近成立。

相关论文见: H. Liu, G. Wang, D. Yang, Clique immersion in graphs without a fixed bipartite graph, J. Combin. Theory Ser. B, 57 (2022) 346–365.