Combinaciones estables en campo medio

Consideremos el grafo bipartito completo en n+n vértices donde las aristas están equipadas con costos exponenciales i.i.d. Una combinación de los vértices es estable si no contiene ningún par de vértices donde la arista que los conecta es más barata que ambos costos de coincidencia. Existe una combinación estable única obtenida emparejando iterativamente los vértices con pequeños costos de arista. Mostramos que el costo total C₍, ₍ de esta coincidencia es del orden de n con varianza acotada, y que C₍, ₍ - n converge a una distribución de Gumbel. También mostramos que el costo típico de una arista en la coincidencia es del orden de 1/n, con una densidad explícita en esta escala, y analizamos el rango de una arista típica. Estos resultados son paralelos a los de Aldous para la coincidencia de costo mínimo en el mismo contexto. Luego consideramos la sensibilidad de la coincidencia y el costo de la coincidencia a perturbaciones de los costos de arista subyacentes. La coincidencia misma demuestra ser robusta en el sentido de que dos coincidencias basadas en costos de arista mayormente idénticos tendrán una superposición sustancial. Sin embargo, se demuestra que el costo de coincidencia es sensible al ruido, como resultado del hecho de que las aristas más caras serán reemplazadas con alta probabilidad después del muestreo. Nuestras pruebas también se aplican al grafo completo (unipartito) y los resultados en este caso son cualitativamente similares.