Large induced distance matchings in certain sparse random graphs (Q6993728)

Given a graph \(G\) and a distance \(k\), a set of edges \(M_k \subseteq E(G)\) is said to form a distance \(k\)-matching if no two members of \(M_k\) are at distance at most \(k\) in \(G\).\N\NThe authors study the asymptotics of distance matchings in random graphs and more specifically, in graphs sampled from \(\mathbb{G}(n,C/n)\), where \(C>0\) is some sufficiently large constant.\N\N\textit{R. J. Kang} and \textit{P. Manggala} [Discrete Appl. Math. 160, No. 16--17, 2435--2439 (2012; Zbl 1329.05111)] proved that given \(k \geq 2\) a graph \(G \sim \mathbb{G}(n,C/n)\) asymptotically almost surely has the property that distance \(k\)-matchings have size at most \(\left(1+o(1) \right)\frac{kn \log c}{2c^{k-1}}\). For \(k=2\), \textit{O. Cooley} et al. [SIAM J. Discrete Math. 35, No. 1, 267--280 (2021; Zbl 1459.05297)] proved that this bound is, in fact, tight. Here, the authors venture further and establish that \(G \sim \mathbb{G}(n,C/n)\) asymptotically almost surely has the property that distance \(k\)-matchings have size at least \(\left(1+o(1) \right)\frac{kn \log c}{4c^{k-1}}\), whenever \(k \geq 3\).