  We consider the problem of sequential matching in a stochastic block model
with several classes of nodes and generic compatibility constraints. When the
probabilities of connections do not scale with the size of the graph, we show
that under the NCOND condition, a simple max-weight type policy allows to
attain an asymptotically perfect matching while no sequential algorithm attain
perfect matching otherwise. The proof relies on a specific Markovian
representation of the dynamics associated with Lyapunov techniques.
