On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three (Q2930057): Difference between revisions

This paper considers the random graph model \(G_{n,m}^{\delta\geq k}\) which is the classical Erdős-Rényi model, where \(m\) edges are chosen uniformly at random on a set of \(n\) vertices, conditional on having minimum degree at least \(k\). In this random graph, a 2-matching is sought after, which is a spanning subgraph of maximum degree at most 2. In other words, this is a spanning structure that consists of a union of paths and cycles. The regime where \(m = cn\) is considered. For any \(k\geq 3\), it has been shown that there exists a constant \(c_k\) such that if \(c\geq c_k\), the random graph \(G_{n,m}^{\delta\geq k}\) has \((k-1)/2\) disjoint Hamilton cycles (or Hamilton cycles and a perfect matching if \(k\) is odd). Such a collection is a special case of a 2-matching.NEWLINENEWLINENEWLINE The results of this paper imply that \(c_3\) is less than 10. The approach followed here is based on a tedious analysis of a greedy algorithm that produces a 2-matching and can be seen as a generalisation of the Karp-Sipser algorithm, that produces a perfect matching on a given graph. Moreover, it is shown that this algorithm produces (with high probability) a 2-matching with a logarithmic number of components. Furthermore, for these values of \(c\) it is shown that a Hamilton cycle can be found in time \(O(n^{1.5 + o(1)})\). The greedy algorithm is analysed on the random pairing model for graphs with a given degree sequence, which approximates the degree distribution of \(G_{n,cn}^{\delta \geq 3}\) (namely, it is follows a truncated Poisson distribution).