一类稀疏随机图的距离匹配数（英文）  

On Distance Matching Number in a Class of Sparse Random Graphs

作　　者：田方 TIAN Fang(School of Mathematics, Research Center of Computational Mathematics and Financial Big Data, Shanghai University of Finance and Economics, Shanghai, 200433, P. R. Chin)

机构地区：[1]上海财经大学数学学院、上海财经大学计算数学与金融大数据研究中心,上海200433

出　　处：《数学进展》2018年第2期175-181,共7页Advances in Mathematics（China）

基　　金：Foundation item： This work is supported by NSFC (Nos. 11101256, 11271243) and China Scholarship Council (No. 201706485019).

摘　　要：对于任意给定的正整数k,图G的距离匹配数um_k(G)是指任意两条边之间距离大于k的最大边数的集合.令G_(n,p)为经典Erds-Rényi随机图.Kang和Manggala刻画得到了当k≥2,边概率为p=c/n时稀疏Erds-Rényi随机图距离匹配数um_k(G_(n,p))的上界,其中c为足够大的常数.本文第一次利用二阶矩方法获得当k≥2时此类稀疏随机图距离匹配数的下界.For any positive integer k, the distance matching number, denoted by umk（G）, is the largest size of a collection of edges in G such that no two edges are within distance k. Let Gn,p stand for the classic Erdos-Renyi random graph. Kang and Manggala presented an upper bound of umk（Gn,p） for k ≥ 2 and p = c/n with the constant c sufficiently large. In this paper, we firstly consider the lower bound of urnk（Gn,p） = Ω（logn） for k≥2 by the second moment method in this class of sparse random graphs.

关 键 词：距离匹配数 Erdos—Renyi随机图 二阶矩方法 

分 类 号：O157.5[理学—数学]