Maximum induced matchings of random cubic graphs (Q1612292)

An algorithm to find large induced matchings in cubic graphs is described. It is an algorithm that has been shown to return an induced matching of order at least \(3n/20 + O(1)\) for a cubic graph of order \(n\) and that there are infinitely many such graphs for which only this bound is achieved. The algorithm is applied to random cubic graphs, and it is shown that the order of the induced matching \(M\) returned almost surely satisfies \(.270413n \leq |M|\leq .282069n\). The lower bound in the expected size was proved by numerically solving differential equations, and the upper bound was verified using direct expectation arguments.