Contar el número de $(d_v,d_c)$ grafos bipartitos regulares

Question

Estoy tratando de contar el número de $(d_v,d_c)$ grafos bipartitos regulares. En concreto, dejemos que $n,m,d_v,d_c$ sean enteros positivos tales que $$n\times d_v=m\times d_c.$$ Entonces, ¿cuál es el número de grafos bipartitos $\mathcal{G}=(L\cup R, E)$ , donde $L$ es el conjunto de vértices de la izquierda, $R$ es el conjunto de vértices derechos con la propiedad de que cada vértice izquierdo tiene $d_v$ aristas incidentes en él, y cada vértice derecho tiene $d_c$ aristas que inciden en él (permitiendo aristas paralelas, es decir, puede haber más de una arista para un par de vértices dado)? ¿Se puede encontrar una expresión general para esto?

Este problema se puede reformular como un problema de bolas y contenedores de la siguiente manera: Tenemos un total de $nd_v$ bolas, de $n$ colores, con $d_v$ bolas de cada color. Cuál es el número de formas de colocar estas bolas en $m$ contenedores no idénticos para que cada contenedor tenga exactamente $d_c$ ¿pelotas? Permítanme denotar este número $\psi(n,d_v,d_c)$ Una rápida reflexión sobre esto me lleva a los siguientes límites: $$\frac{(nd_v)!}{\left(d_v! \right)^n(d_c!)^m}\leq\psi(n,d_v,d_c)\leq \frac{(nd_v)!}{\left(d_v! \right)^n}.$$ ¿Se puede hacer algo mejor?

Creo que debe haber algún trabajo que haya abordado este problema pero no he podido encontrar nada. Cualquier ayuda se agradecería.

Answer 1

No existe una fórmula exacta útil, excepto para las pequeñas $d_v$ o $d_c$ . Los mejores resultados asintóticos aparecen en este documento de Canfield y McKay para matrices densas y este documento de Greenhill y McKay para matrices dispersas. Hay una brecha sin resolver entre los dos rangos. El primer artículo tiene una conjetura que probablemente se mantiene para todos los valores de los parámetros.