The Dyck bound in the concave 1-dimensional random assignment model

We consider models of assignment for random N blue points and N red points on an interval of length 2N, in which the cost for connecting a blue point in x to a red point in y  is the concave function |x - y |p , for 0 < p  < 1. Contrarily to the convex case p  > 1, where the optimal matching is trivially determined, here the optimization is non-trivial. The purpose of this paper is to introduce a special configuration, that we call the Dyck matching, and to study its statistical properties. We compute exactly the average cost, in the asymptotic limit of large N, together with the first subleading correction. The scaling is remarkable: it is of order N for p ≤ 1/2, order N In N for p = 1/2, and N1/2+p for p ≤ 1/2, and it is universal for a wide class of models. We conjecture that the average cost of the Dyck matching has the same scaling in N as the cost of the optimal matching, and we produce numerical data in support of this conjecture. We hope to produce a proof of this claim in future work.