Start with a distribution $\mu$ on [n], and drop m balls into these n+1 slots independently and according to the distribution &mu. That is, we have iid random variables x 1 through x m distributed according to &mu. Assume that m is close to the same size as n.
I call a collection of tuples (a(i), b (i)), with all a(i), b(i) between 1 and m, a partial matching if no number is repeated, and for all i, x b(i) = x a(i) + 1.
My (purposefully vague) question is: Is there, with high probability, a partial matching that includes many of the balls?
Of course, for some distributions this obviously doesn't happen. I would be happy if somebody had a 'standard argument' for this type of question in nice cases, and maybe we could get some understanding of what makes it run (and so in what cases it doesn't).
Some side comments: