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

International audienceWe 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 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 , 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