论文标题
在某些稀疏的随机图中，诱导距离匹配很大
Large induced distance matchings in certain sparse random graphs
论文作者
论文摘要
对于固定的整数$ k \ geqslant 2 $，让$ g \ in \ mathcal {g}（n，p）$成为一个简单的连接图，上面是$ n \ rightArrow \ rightarrow \ infty $ temtices，具有预期的$ d = np $ d = np $ d = np $ d = np $ d \ d \ d \ geqslant c $ d \ geqslant c $和$ d^$ d^$ d^$ npands for Affore for loffage。我们表明，任何最大边缘$ m $ in $ g $的最大收集的渐近大小，因此$ m $中的两个边缘在距离$ k $之内，称为距离$ k $ -matching，在$ \ frac {（k-1）n \ log d}之间d} {2d^{k-1}} $。我们还设计了一种随机贪婪算法，以生成一个大距离$ k $，以$ g $匹配，并具有渐近尺寸$ \ frac {kn \ log d} {4d^{k-1}} $。我们的结果部分将结果概括为与CASE的最大距离$ K $匹配的大小，$ K = 2 $或$ D = C $，对于某些大型常数$ C $。
For a fixed integer $k\geqslant 2$, let $G\in \mathcal{G}(n,p)$ be a simple connected graph on $n\rightarrow\infty$ vertices with the expected degree $d=np$ satisfying $d\geqslant c$ and $d^{k-1}= o(n)$ for some large enough constant $c$. We show that the asymptotical size of any maximal collection of edges $M$ in $G$ such that no two edges in $M$ are within distance $k$, which is called a distance $k$-matching, is between $ \frac{(k-1)n\log d}{4d^{k-1}}$ and $ \frac{k n \log d}{2d^{k-1}}$. We also design a randomized greedy algorithm to generate one large distance $k$-matching in $G$ with asymptotical size $ \frac{kn\log d}{4d^{k-1}}$. Our results partially generalize the results on the size of the largest distance $k$-matchings from the case $k=2$ or $d=c$ for some large constant $c$.
