Karp-Sipser on random graphs with a fixed degree sequence

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