Karp-Sipser on random graphs with a fixed degree sequence

<p>Let Δ ≥ 3 be an integer. Given a fixed <em><strong>z</strong></em> ∈ ₊^Δ such that <em>z</em>_Δ > 0, we consider a graph <em>G</em>_{<strong>z</strong>} drawn uniformly at random from the collection of graphs with <em>z</em>_<em>i</em><em>n</em> vertices of degree <em>i</em> for <em>i</em> = 1,. . .,Δ. We study the performance of the Karp–Sipser algorithm when applied to <em>G</em>_{<strong>z</strong>}. If there is an index δ > 1 such that <em>z</em>₁ = . . . = <em>z</em>_δ−1 = 0 and δ<em>z</em>_δ,. . .,Δ<em>z</em>_Δ is a log-concave sequence of positive reals, then with high probability the Karp–Sipser algorithm succeeds in finding a matching with <em>n</em> ∥ <strong>z</strong> ∥ ₁/2 − <em>o</em>(<em>n</em>^1−ε) edges in <em>G</em>_{<strong>z</strong>}, where ε = ε (Δ, <strong>z</strong>) is a constant.</p>