Número de Dedekind

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.^[1]​ 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.

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

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,^[2]​^[3]​^[4]​ y una expresión exacta en forma de sumatoria,^[5]​ el cómputo de M(n) sigue siendo ineficiente, y sus valores exactos sólo se conocen para valores n ≤ 8.^[6]​

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 ≤ 8. 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 conocidos, donde se aprecia el crecimiento exponencial de la sucesión.

n	Número M(n)	Año
0	2	1940^[1]​
1	3	1940^[1]​
2	6	1940^[1]​
3	20	1940^[1]​
4	168	1940^[1]​
5	7581	1940^[7]​
6	7828354	1946^[8]​
7	2414682040998	1965^[9]​ y 1976^[10]​
8	56130437228687557907788	1991^[6]​
(sucesión A000372 en OEIS)

Si n es un número par, entonces M(n) también debería serlo.^[11]​ 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).^[7]​

Fórmula con sumatoria

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

${\displaystyle 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

${\displaystyle 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

${\displaystyle {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 ${\displaystyle \lfloor n/2\rfloor }$  elementos, y la inecuación derecha fue demostrada por Kleitman y Markowsky.^[2]​

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

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

para n par, y

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

para n impar, donde

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

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

y

${\displaystyle 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.^[13]​ 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.^[14]​

Referencias

1. Dedekind, Richard (1897), Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler 2, Gesammelte Werke, pp. 103-148 ..
2. Kleitman, D.; Markowsky, G. (1975), «On Dedekind's problem: the number of isotone Boolean functions. II», Transactions of the American Mathematical Society 213: 373-390, MR0382107 ..
3. Korshunov, A. D. (1981), «The number of monotone Boolean functions», Problemy Kibernet. 38: 5-108, MR0640855 ..
4. Kahn, Jeff (2002), «Entropy, independent sets and antichains: a new approach to Dedekind's problem», Proceedings of the American Mathematical Society 130 (2): 371-378, doi:10.1090/S0002-9939-01-06058-0, MR1862115 ..
5. Kisielewicz, Andrzej (1988), «A solution of Dedekind's problem on the number of isotone Boolean functions», Journal für die Reine und Angewandte Mathematik 386: 139-144, doi:10.1515/crll.1988.386.139, MR936995 ..
6. Wiedemann, Doug (1991), «A computation of the eighth Dedekind number», Order 8 (1): 5-6, doi:10.1007/BF00385808, MR1129608 ..
7. Church, Randolph (1940), «Numerical analysis of certain free distributive structures», Duke Mathematical Journal 6: 732-734, MR0002842 ..
8. Ward, Morgan (1946), «Note on the order of free distributive lattices», Bulletin of the American Mathematical Society 52: 423 ..
9. Church, Randolph (1965), «Enumeration by rank of the free distributive lattice with 7 generators», Notices of the American Mathematical Society 11: 724 .. Citado por Wiedemann, 1991.
10. Berman, Joel; Köhler, Peter (1976), «Cardinalities of finite distributive lattices», Mitt. Math. Sem. Giessen 121: 103-124, MR0485609 ..
11. Yamamoto, Koichi (1953), «Note on the order of free distributive lattices», Science Reports of the Kanazawa University 2 (1): 5-6, MR0070608 ..
12. Korshunov, A. D. (1981), «The number of monotone Boolean functions», Problemy Kibernet. 38: 5-108, MR0640855 ..
13. Zaguia, Nejib (1993), «Isotone maps: enumeration and structure», en Sauer, N. W.; Woodrow, R. E.; Sands, B., eds., Finite and Infinite Combinatorics in Sets and Logic (Proc. NATO Advanced Study Inst., Banff, Alberta, Canada, May 4, 1991), Kluwer Academic Publishers, pp. 421-430, MR1261220 ..
14. Brown, K. S., , archivado desde el original el 18 de diciembre de 2010, consultado el 3 de octubre de 2010 ..

•   Datos: Q5249753