file.pdf (351.41 kB)

# 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*

_{i}

*n*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*

_{1}= . . . =

*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**∥

_{1}/2 −

*o*(

*n*

^{1−ε}) edges in

*G*

_{z}, where ε = ε (Δ,

**z**) is a constant.