Número de Dedekind

Los retículos distributivos libres de funciones booleanas monótonas sobre 0, 1, 2 y 3 argumentos.

En combinatoria, los números de Dedekind son una sucesión entera de rápido crecimiento cuyo nombre se dio póstumamente en honor a Richard Dedekind, quien las definió por primera vez en 1897.​ El número de Dedekind M(n) corresponde, equivalentemente, a lo siguiente:

• El número de funciones booleanas monótonas de n variables.
• El número de anticadenas de subconjuntos de un conjunto de n elementos.
• El número de elementos en un retículo distributivo libre con n generadores.
• El número de juegos simples irredundantes definibles sobre n jugadores.
• El número de hipergrafos minimales completos, definibles sobre un conjunto base de cardinalidad n.
• El número de familias de Sperner sobre un conjunto de n elementos.

Encontrar una expresión matemática de forma cerrada para M(n) se conoce como el Problema de Dedekind. Aunque existen aproximaciones asintóticas que estiman este número,​​​ y una expresión exacta en forma de sumatoria,​ el cómputo de M(n) sigue siendo ineficiente, y sus valores exactos sólo se conocen para valores n ≤ 9.​​​

Ejemplo

Para n = 2, existen seis funciones booleanas monótonas y seis anticadenas de subconjuntos del conjunto de dos elementos {x,y}:

• La función f(x,y) = falso, que ignora sus valores de entrada y siempre retorna falso, corresponde a la anticadena vacía Ø.
• La conjunción lógica f(x,y) = x ∧ y corresponde a la anticadena { {x,y} }, que contiene al conjunto {x,y}.
• La función f(x,y) = x, que ignora su segundo argumento y retorna el primero, corresponde a la anticadena { {x} } que contiene al conjunto {x}.
• La función f(x,y) = y, que ignora su primer argumento y retorna el segundo, corresponde a la anticadena { {y} } que contiene al conjunto {y}.
• La disyunción lógica f(x,y) = x ∨ y corresponde a la anticadena { {x}, {y} }, que contiene a los dos conjuntos {x} e {y}.
• La función f(x,y) = verdadero, que ignora sus valores de entrada y siempre retorna verdadero, corresponde a la anticadena {Ø} que contiene sólo al conjunto vacío.

Valores conocidos

Los valores exactos de los números de Dedekind se conocen para 0 ≤ n ≤ 9. La siguiente tabla muestra tales números, junto con el año y la publicación en que fueron calculados:

Gráfica de los números de Dedekind hasta n = 8, donde se aprecia el crecimiento exponencial de la sucesión.

n	Número M(n)	Año
0	2	1940​
1	3	1940​
2	6	1940​
3	20	1940​
4	168	1940​
5	7 581	1940​
6	7 828 354 $\approx 7.83\times 10^{6}$	1946​
7	2 414 682 040 998 $\approx 2.41\times 10^{12}$	1965​ y 1976​
8	56 130 437 228 687 557 907 788 $\approx 5.61\times 10^{22}$	1991​
9	286 386 577 668 298 411 128 469 151 667 598 498 812 366 $\approx 2.86\times 10^{41}$	2023​​
(sucesión A000372 en OEIS)

Si n es un número par, entonces M(n) también debería serlo.​ El cálculo de M(5) = 7581 fue el contraejemplo que desaprobó una conjetura realizada por Garrett Birkhoff que decía que M(n) es siempre divisible por (2n - 1)(2n - 2).​

Fórmula con sumatoria

Andrzej Kisielewicz en 1988 demostró la siguiente fórmula para los números de Dedekind:​

$M(n)=\sum _{k=1}^{2^{2^{n}}}\prod _{j=1}^{2^{n}-1}\prod _{i=0}^{j-1}\left(1-b_{i}^{k}b_{k}^{k}\prod _{m=0}^{\log _{2}i}(1-b_{m}^{i}+b_{m}^{i}b_{m}^{j})\right),$

donde

$b_{i}^{k}=\left\lfloor {\frac {k}{2^{i}}}\right\rfloor -2\left\lfloor {\frac {k}{2^{i+1}}}\right\rfloor .$

Sin embargo, esta fórmula no es útil para el cómputo de los valores de M(n) para n grandes, debido al gran número de términos en la sumatoria.

Asíntotas

El logaritmo de los números de Dedekind puede ser estimado exactamente mediante las cotas

${n \choose \lfloor n/2\rfloor }\leq \log _{2}M(n)\leq {n \choose \lfloor n/2\rfloor }\left(1+O\left({\frac {\log n}{n}}\right)\right).$

La inecuación de la izquierda cuenta el número de anticadenas en que cada conjunto tiene exactamente $\lfloor n/2\rfloor$ elementos, y la inecuación derecha fue demostrada por Kleitman y Markowsky.​

A. D. Korshunov encontró en 1981 una estimación aún mejor:​

$M(n)=(1+o(1))2^{n \choose \lfloor n/2\rfloor }\exp a(n)$

para n par, y

$M(n)=(1+o(1))2^{n \choose \lfloor n/2\rfloor }\exp(b(n)+c(n))$

para n impar, donde

$a(n)={n \choose n/2-1}(2^{-n/2}+n^{2}2^{-n-5}-n2^{-n-4}),$

$b(n)={n \choose (n-3)/2}(2^{-(n+3)/2}-n^{2}2^{-n-6}-n2^{-n+3}),$

y

$c(n)={n \choose (n-1)/2}(2^{-(n+1)/2}+n^{2}2^{-n-4}).$

La principal idea detrás de estas estimaciones, es que en la mayoría de las anticadenas, todos los conjuntos tienen tamaños muy cercanos a n/2.​ Para n = 2, 4, 6 y 8, la fórmula de Korshunov provee una estimación imprecisa por un factor de 9.8%, 10.2%, 4.1%, y -3.3%, respectivamente.​

Referencias

• Datos: Q5249753