论文标题
随机图中的大型诱导匹配
Large induced matchings in random graphs
论文作者
论文摘要
给定一个大图$ h $，二项式随机图$ g（n，p）$是否包含$ h $的副本，作为诱发子图，概率很高？这个经典问题已针对各种图表进行了广泛的研究，可以回到Erdős和Bollobás的$ G（N，P）$的独立性数量的研究，以及1976年的Matula。在本文中，我们证明了$ C/N \ le p $ c $ c $ c $ c $ c $ c $ c $ c $ c $ c $ c $ c $ c $ c $ c $ c $ c $ c $ c $ c $ c $ c $ c（订单的匹配约为$ 2 \ log_q（np）$，其中$ q = \ frac {1} {1-p} $。
Given a large graph $H$, does the binomial random graph $G(n,p)$ contain a copy of $H$ as an induced subgraph with high probability? This classical question has been studied extensively for various graphs $H$, going back to the study of the independence number of $G(n,p)$ by Erdős and Bollobás, and Matula in 1976. In this paper we prove an asymptotically best possible result for induced matchings by showing that if $C/n\le p \le 0.99$ for some large constant $C$, then $G(n,p)$ contains an induced matching of order approximately $2\log_q(np)$, where $q= \frac{1}{1-p}$.
